cross
Foswiki.org is now running Foswiki 2.1.3 Beta 1. Please open a task for any issues.
You are here: Foswiki>Tasks Web>Item14066 (22 Dec 2016, GeorgeClark)Edit Attach

Item14066: Performance issue sorting list based on NFKD.

pencil
Priority: Urgent
Current State: Waiting for Release
Released In: 2.1.3
Target Release: patch
Applies To: Engine
Component: Performance, I18N
Branches: master Release02x01 Item14033 Item13897
Reported By: MichaelDaum
Waiting For:
Last Change By: GeorgeClark
Just ran Devel::NYTProfile on System.WebHome to see what eats the CPU and found one single codeline that stuck out most:

In Foswiki::Store::Rcs::Handler::getTopicNames() and elsewhere we use this pattern:

     my @topicList =
       map { /^(.*)\.txt$/; $1; }
       sort { NFKD($a) cmp NFKD($b) }    # unicode aware
       grep { !/$Foswiki::cfg{NameFilter}/ && /\.txt$/ }
        map( _decode($_), readdir($dh) );

Problem is that NFKD() is called on list items redundantly. Any non-trivial sort criterion - like the above one - that takes a considerable amount of performance will bring down performance exponentially based on the length of the list to be sorted (due to the sorting algorithm of perl).

Instead of recomputing NFKD() again and again, the sort criterion should be computed once and only once beforehand. Below code is performing much faster:

    my @topicList =
      map { $_->[0] }
      sort { $a->[1] cmp $b->[1] }
      map { [ $_, NFKD($_) ] }
      map { /^(.*)\.txt$/; $1; }
      grep { !/$Foswiki::cfg{NameFilter}/ && /\.txt$/ }
      map( _decode($_), readdir($dh) );

See http://perltraining.com.au/tips/2004-12-17.html

Just fixing Foswiki::Store::Rcs::Handler::getTopicNames() that way brought down rendering =System.WebHome on a client's site from 1.7s to 1s (...+- 200ms).

There are a lot of other places using sort { NFKD($a) cmp NFKD($b) }. These all need fixing.

Here are two flamegraphcs generated by CPAN:Devel::NYTProf before and after applying above patch to getTopicNames() on (skin=text, template=view, topic=System.WebTopicList).

FoswikiProfileSystemWebTopicList1.png FoswikiProfileSystemWebTopicList2.png

You can clearly see the stretch spent inside the Unicode::Normalize class being reduced to a minimum while the feature remains the same.

-- MichaelDaum - 09 May 2016

As discussed in release meeting, see CleanUpFoswikiLocales and CPAN:Unicode::Collate::Locale which provides a better and performant solution to the same problem.

-- JulianLevens - 30 May 2016 - 15:22

It would be nice to move these one-off sort fixes into a Foswiki::sort() utility. That will also simplify the conversion to Unicode::Collate::Locale

-- GeorgeClark - 30 May 2016
 
Topic revision: r15 - 22 Dec 2016, GeorgeClark - This page was cached on 22 Jan 2017 - 09:39.

The copyright of the content on this website is held by the contributing authors, except where stated elsewhere. See Copyright Statement. Creative Commons License