Item14066: Performance issue sorting list based on NFKD.

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).

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

Commenting is disabled while not logged in