This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]