You are here: Foswiki>Tasks Web>Item14066 (31 Jan 2018, MichaelDaum)Edit Attach

Item14066: Performance issue sorting list based on NFKD.

Priority: Urgent
Current State: Closed
Released In: 2.1.3
Target Release: patch
Applies To: Engine
Component: Performance, I18N
Branches: master Release02x01 Item14033 Item13897 Item14380 Item14537
Reported By: MichaelDaum
Waiting For:
Last Change By: MichaelDaum
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) );


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: r18 - 31 Jan 2018, MichaelDaum - This page was cached on 17 Feb 2018 - 22:37.

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