[Patch v2] [BZ 15884] strcoll: improve performance by removing the cache
Stefan Liebler
stli@linux.vnet.ibm.com
Wed Oct 22 15:13:00 GMT 2014
Hi Leonhard,
great job.
If I run make xcheck on s390x, I get a failure in
string/tst-strcoll-overflow testcase. See tst-strcoll-overflow.out:
0
Expected signal 'Alarm clock' from child, got none
I measured the execution time of this testcase between 35...60s
which is smaller than the defined timeout of 300s.
Can you change the behaviour of the testcase that it is passing
if it was timed out or if it returns successfully without timeout.
Bye
Stefan
On 10/14/2014 03:11 PM, Leonhard Holz wrote:
> 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 bench-strcoll.c with test data in
> benchtests-strcoll.tar.gz. 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.
>
> The output of the benchmark is:
>
> "strcoll": {
> "": {
> "locale": "en_US.UTF-8",
> "duration": 7.41506e+09,
> "iterations": 16,
> "mean": 4.63441e+08
> },
> "vi_VN.UTF-8": {
> "duration": 7.4185e+07,
> "iterations": 16,
> "mean": 4.63656e+06
> },
> "en_US.UTF-8": {
> "duration": 7.59759e+07,
> "iterations": 16,
> "mean": 4.7485e+06
> },
> "ar_SA.UTF-8": {
> "duration": 7.61479e+07,
> "iterations": 16,
> "mean": 4.75924e+06
> },
> "zh_CN.UTF-8": {
> "duration": 1.37535e+07,
> "iterations": 16,
> "mean": 859594
> },
> "cs_CZ.UTF-8": {
> "duration": 7.90032e+07,
> "iterations": 16,
> "mean": 4.9377e+06
> },
> "en_GB.UTF-8": {
> "duration": 7.4454e+07,
> "iterations": 16,
> "mean": 4.65338e+06
> },
> "da_DK.UTF-8": {
> "duration": 7.265e+07,
> "iterations": 16,
> "mean": 4.54062e+06
> },
> "pl_PL.UTF-8": {
> "duration": 7.28964e+07,
> "iterations": 16,
> "mean": 4.55602e+06
> },
> "fr_FR.UTF-8": {
> "duration": 7.99239e+07,
> "iterations": 16,
> "mean": 4.99524e+06
> },
> "pt_PT.UTF-8": {
> "duration": 7.78347e+07,
> "iterations": 16,
> "mean": 4.86467e+06
> },
> "el_GR.UTF-8": {
> "duration": 1.0959e+08,
> "iterations": 16,
> "mean": 6.84937e+06
> },
> "ru_RU.UTF-8": {
> "duration": 9.39324e+07,
> "iterations": 16,
> "mean": 5.87077e+06
> },
> "iw_IL.UTF-8": {
> "duration": 8.8769e+07,
> "iterations": 16,
> "mean": 5.54806e+06
> },
> "es_ES.UTF-8": {
> "duration": 8.0782e+07,
> "iterations": 16,
> "mean": 5.04888e+06
> },
> "hi_IN.UTF-8": {
> "duration": 3.66962e+09,
> "iterations": 16,
> "mean": 2.29351e+08
> },
> "sv_SE.UTF-8": {
> "duration": 7.41934e+07,
> "iterations": 16,
> "mean": 4.63709e+06
> },
> "hu_HU.UTF-8": {
> "duration": 9.04538e+07,
> "iterations": 16,
> "mean": 5.65336e+06
> },
> "tr_TR.UTF-8": {
> "duration": 7.25579e+07,
> "iterations": 16,
> "mean": 4.53487e+06
> },
> "is_IS.UTF-8": {
> "duration": 6.83783e+07,
> "iterations": 16,
> "mean": 4.27364e+06
> },
> "it_IT.UTF-8": {
> "duration": 7.50307e+07,
> "iterations": 16,
> "mean": 4.68942e+06
> },
> "sr_RS.UTF-8": {
> "duration": 8.14996e+07,
> "iterations": 16,
> "mean": 5.09373e+06
> },
> "ja_JP.UTF-8": {
> "duration": 1.5325e+07,
> "iterations": 16,
> "mean": 957814
> }
> }
>
> That is compared to the previous version:
>
> glibc files -33.77%
> vi_VN.UTF-8 -34.12%
> en_US.UTF-8 -42.42%
> ar_SA.UTF-8 -27.49%
> zh_CN.UTF-8 +07.90%
> cs_CZ.UTF-8 -29.67%
> en_GB.UTF-8 -28.50%
> da_DK.UTF-8 -36.57%
> pl_PL.UTF-8 -39.31%
> fr_FR.UTF-8 -28.57%
> pt_PT.UTF-8 -22.82%
> el_GR.UTF-8 -26.77%
> ru_RU.UTF-8 -35.81%
> iw_IL.UTF-8 -35.34%
> es_ES.UTF-8 -34.46%
> hi_IN.UTF-8 -00.38%
> sv_SE.UTF-8 -36.99%
> hu_HU.UTF-8 -16.35%
> tr_TR.UTF-8 -27.80%
> is_IS.UTF-8 -33.24%
> it_IT.UTF-8 -24.39%
> sr_RS.UTF-8 -37.55%
> ja_JP.UTF-8 +02.84%
>
> Best,
> Leonhard
>
>
> 2014-10-14 Leonhard Holz <leonhard.holz@web.de>
>
> [BZ #15884]
> * string/strcoll_l.c (STRCOLL): Remove weight and rules cache.
> * benchtests/bench-strcoll.c: New benchmark.
> * benchtests/Makefile (bench-string): Use it.
> * benchtests/strcoll-inputs/lorem_ipsum_ar_SA New file.
> * benchtests/strcoll-inputs/lorem_ipsum_cs_CZ Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_da_DK Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_el_GR Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_en_GB Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_en_US Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_es_ES Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_fr_FR Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_hi_IN Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_hu_HU Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_is_IS Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_it_IT Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_iw_IL Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_ja_JP Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_pl_PL Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_pt_PT Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_ru_RU Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_sr_RS Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_sv_SE Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_tr_TR Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_vi_VN Likewise.
> * benchtests/strcoll-inputs/lorem_ipsum_zh_CN Likewise.
> * localedata/Makefile (LOCALES): Generate needed locales.
>
More information about the Libc-alpha
mailing list