[Patch] [BZ 15884] strcoll: improve performance by removing the cache

[Leonhard Holz <leonhard dot holz at web dot de>]

Hello everybody,

this is a path that should solve bug 15884. It complains about the 
performance of strcoll(). It was found out that the runtime of strcoll() 
is actually bound to strlen which is needed for calculating the size of 
a cache that was installed to improve the comparison performance.

The idea for this patch was that the cache is only useful in rare cases 
(strings of same length and same first-level-chars) and that it would be 
better to avoid memory allocation at all. To prove this I wrote a 
performance test that is found in benchtests-strcoll.tar.bz2. Also 
modifications in benchtests/Makefile and localedata/Makefile are 
necessary to make it work.

After removing the cache the strcoll method showed the predicted 
behavior (getting slightly faster) in all but the test case for hindi 
word sorting. This was due the hindi text having much more equal words 
than the other ones. For equal strings the performance was worse since 
all comparison levels were run through and from the second level on the 
cache improved the comparison performance of the original version.

Therefore I added a bytewise test via strcmp iff the first level 
comparison found that both strings did match because in this case it is 
very likely that equal strings are compared. This solved the problem 
with the hindi test case and improved the performance of the others.

Another improvement was achieved by inlineing both static subroutines.

The performance measurements on my machine are:

glibc_files.txt                     en_US.UTF-8	-61.67%
lorem_ipsum_vietnamese.txt          vi_VN.UTF-8	-55.29%
lorem_ipsum_latin.txt               en_US.UTF-8	-59.30%
lorem_ipsum_arabic.txt              ar_SA.UTF-8	-48.18%
lorem_ipsum_l33tspeak.txt           en_US.UTF-8	-57.86%
lorem_ipsum_chinese.txt             zh_CN.UTF-8	-17.21%
lorem_ipsum_czech.txt               cs_CZ.UTF-8	-47.28%
lorem_ipsum_old_english.txt         en_GB.UTF-8	-47.08%
lorem_ipsum_danish.txt              da_DK.UTF-8	-56.21%
lorem_ipsum_polish.txt              pl_PL.UTF-8	-54.80%
lorem_ipsum_french.txt              fr_FR.UTF-8	-45.35%
lorem_ipsum_portugese.txt           pt_PT.UTF-8	-46.27%
lorem_ipsum_greek.txt               el_GR.UTF-8	-40.77%
lorem_ipsum_russian.txt             ru_RU.UTF-8	-49.30%
lorem_ipsum_hebrew.txt              iw_IL.UTF-8	-50.76%
lorem_ipsum_spain.txt               es_ES.UTF-8	-50.51%
lorem_ipsum_hindi.txt               hi_IN.UTF-8	+00.90%
lorem_ipsum_swedish.txt             sv_SE.UTF-8	-56.53%
lorem_ipsum_hungarian.txt           hu_HU.UTF-8	-34.95%
lorem_ipsum_turkish.txt             tr_TR.UTF-8	-50.20%
lorem_ipsum_icelandic.txt           is_IS.UTF-8	-54.63%
lorem_ipsum_italian.txt             it_IT.UTF-8	-46.44%
lorem_ipsum_yugoslavian.txt         sr_RS.UTF-8	-54.81%
lorem_ipsum_japanese.txt            ja_JP.UTF-8	+25.56%

Best,
Leonhard

Attachment: benchtests_Makefile.diff
Description: Text document

Attachment: benchtests-strcoll.tar.bz2
Description: Binary data

Attachment: localedata_Makefile.diff
Description: Text document

Attachment: string_strcoll_l.c.diff
Description: Text document