[Bug libc/15884] New: Big performance regression in strcoll

[Bug libc/15884] New: Big performance regression in strcoll

[neleai at seznam dot cz]

http://sourceware.org/bugzilla/show_bug.cgi?id=15884

            Bug ID: 15884
           Summary: Big performance regression in strcoll
           Product: glibc
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P2
         Component: libc
          Assignee: unassigned at sourceware dot org
          Reporter: neleai at seznam dot cz
                CC: drepper.fsp at gmail dot com

Hi, 
After looking to strcoll code I noticed glaring performance problems. 
Consider following program:

#include <locale.h>
#include <string.h>
#include <stdlib.h>
int foo(char *a,char *b){
  return strcoll(a,b);
}

int main(){
  setlocale(LC_ALL, "en_US.UTF8");
  int i,f=0;
  char *a=malloc(1000000);
  char *b=malloc(1000000);
  memset(a,32,N); a[N]=0;
  memset(b,33,N); a[N]=0;

  for (i=0;i<1000000;i++)
        f+=foo(a,b);
  return f;
}

As a and b differ in first character we should get O(1) performance, yet I got:

ondra@neklekam:~$ gcc -DN=1 strcoll.c ; time ./a.out

real    0m0.078s
user    0m0.077s
sys    0m0.000s
ondra@neklekam:~$ gcc -DN=10 strcoll.c ; time ./a.out

real    0m0.283s
user    0m0.283s
sys    0m0.000s
ondra@neklekam:~$ gcc -DN=100 strcoll.c ; time ./a.out

real    0m2.016s
user    0m2.013s
sys    0m0.003s

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/15884] Big performance regression in strcoll

[siddhesh at redhat dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=15884

Siddhesh Poyarekar <siddhesh at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |siddhesh at redhat dot com

--- Comment #1 from Siddhesh Poyarekar <siddhesh at redhat dot com> ---
This is not a regression since I can see the same performance characteristics
on 2.15:

[22:40][sid@Devel tmp ]$ rpm -q glibc
glibc-2.15-59.fc17.x86_64
glibc-2.15-59.fc17.i686
[22:40][sid@Devel tmp ]$ gcc -DN=1 fo.c && time ./a.out

real    0m0.098s
user    0m0.098s
sys     0m0.000s
[22:40][sid@Devel tmp ]$ gcc -DN=10 fo.c && time ./a.out

real    0m0.377s
user    0m0.375s
sys     0m0.002s
[22:40][sid@Devel tmp ]$ gcc -DN=100 fo.c && time ./a.out

real    0m2.765s
user    0m2.759s
sys     0m0.002s

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/15884] Big performance regression in strcoll

[siddhesh at redhat dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=15884

Siddhesh Poyarekar <siddhesh at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |INVALID

--- Comment #2 from Siddhesh Poyarekar <siddhesh at redhat dot com> ---
Also, the test case is invalid.  It compares a space with an exclamation point,
both of which are ignored as collation sequences due to which the algorithm
actually goes through all the passes for the string before it compares them on
a binary level.  Replace 32 and 33 with 'a' and 'b' and you'll see the
difference.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/15884] Big performance problem in strcoll

[neleai at seznam dot cz]

http://sourceware.org/bugzilla/show_bug.cgi?id=15884

Ondrej Bilka <neleai at seznam dot cz> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|INVALID                     |---
            Summary|Big performance regression  |Big performance problem in
                   |in strcoll                  |strcoll

--- Comment #3 from Ondrej Bilka <neleai at seznam dot cz> ---
I thougth that originaly a comparison was done character-by-character without
useless allocation, after looking through history I was mistaken. Changing
regression->problem.

> Also, the test case is invalid.  It compares a space with an exclamation  
> point, both of which are ignored as collation sequences due to which the 
> algorithm actually goes through all the passes for the string before it 
> compares them on a binary level.  Replace 32 and 33 with 'a' and 'b' and 
> you'll see the difference.

it is still there, just smaller multiplicative factor hidden it into loop
overhead for smaller lengths. When changed to a/b time becomes:

ondra@neklekam:~$ gcc -DN=1 strcoll.c ; time ./a.out

real    0m0.040s
user    0m0.037s
sys    0m0.000s

ondra@neklekam:~$ gcc -DN=10 strcoll.c ; time ./a.out

real    0m0.039s
user    0m0.037s
sys    0m0.003s
ondra@neklekam:~$ gcc -DN=100 strcoll.c ; time ./a.out

real    0m0.044s
user    0m0.043s
sys    0m0.007s
ondra@neklekam:~$ gcc -DN=1000 strcoll.c ; time ./a.out

real    0m0.115s
user    0m0.113s
sys    0m0.000s
ondra@neklekam:~$ gcc -DN=10000 strcoll.c ; time ./a.out

real    0m0.737s
user    0m0.737s
sys    0m0.000s
ondra@neklekam:~$ gcc -DN=100000 strcoll.c ; time ./a.out

real    0m7.443s
user    0m7.443s
sys    0m0.000s

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/15884] Big performance problem in strcoll

[siddhesh at redhat dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=15884

--- Comment #4 from Siddhesh Poyarekar <siddhesh at redhat dot com> ---
Most of the time is spent in strlen:

samples  %        image name               symbol name
294712   97.3350  libc-2.15.so             __strlen_sse2
2650      0.8752  libc-2.15.so             strcoll_l
1646      0.5436  libc-2.15.so             _int_malloc

That is also unavoidable since the string length is necessary to allocate the
index and rules cache.  Without the index and rules cache, real lookups that
need more than a pass to run will be painfully slow as is evident in the
fallback code I've written to avoid caching if there isn't enough memory.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/15884] Big performance problem in strcoll

[neleai at seznam dot cz]

http://sourceware.org/bugzilla/show_bug.cgi?id=15884

--- Comment #5 from Ondrej Bilka <neleai at seznam dot cz> ---
On Sat, Aug 24, 2013 at 03:48:14AM +0000, siddhesh at redhat dot com wrote:
> http://sourceware.org/bugzilla/show_bug.cgi?id=15884
> 
> --- Comment #4 from Siddhesh Poyarekar <siddhesh at redhat dot com> ---
> Most of the time is spent in strlen:
> 
> samples  %        image name               symbol name
> 294712   97.3350  libc-2.15.so             __strlen_sse2
> 2650      0.8752  libc-2.15.so             strcoll_l
> 1646      0.5436  libc-2.15.so             _int_malloc
> 
> That is also unavoidable since the string length is necessary to allocate the
> index and rules cache.  Without the index and rules cache, real lookups that
> need more than a pass to run will be painfully slow as is evident in the
> fallback code I've written to avoid caching if there isn't enough memory.
> 
No, that is unavoidable for strings that need more than one pass ONLY.

Majority of calls end when first difference is found, no caching needed.

Also you do not need to know length for allocations. Use

newsize = size * 2;
newarray = realloc(array, size, newsize);

when you reach a boundary character.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/15884] Big performance problem in strcoll

[bugdal at aerifal dot cx]

http://sourceware.org/bugzilla/show_bug.cgi?id=15884

Rich Felker <bugdal at aerifal dot cx> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bugdal at aerifal dot cx

--- Comment #6 from Rich Felker <bugdal at aerifal dot cx> ---
I agree with Ondrej. In a sense, completing early is a special case, but it's a
sufficiently common one that it should be handled without calling strlen on the
input.

A similar situation (which is handled correctly if I'm not mistaken) is
strstr("x", huge_string). Despite the fact that the length of the needle needs
to be known for the efficient form of strstr, you can measure the length of the
haystack at the same time, and bail out as soon as the haystack is found to be
shorter than the needle.

Unless I'm mistaken, a similar approach could be used in strcoll: perform the
first-pass comparison at the same time the lengths are measured, and only
measure up to the shorter of the two lengths.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/15884] Big performance problem in strcoll

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=15884

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fweimer at redhat dot com
              Flags|                            |security-

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/15884] Big performance problem in strcoll

[cvs-commit at gcc dot gnu.org]

https://sourceware.org/bugzilla/show_bug.cgi?id=15884

--- Comment #7 from cvs-commit at gcc dot gnu.org <cvs-commit at gcc dot gnu.org> ---
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".

The branch, master has been updated
       via  0742aef6e52a935f9ccd69594831b56d807feef3 (commit)
      from  ee54ce44cb734f18fec4f6ccdfbe997d2574321e (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=0742aef6e52a935f9ccd69594831b56d807feef3

commit 0742aef6e52a935f9ccd69594831b56d807feef3
Author: Leonhard Holz <leonhard.holz@web.de>
Date:   Fri Oct 17 15:47:23 2014 +0530

    strcoll: improve performance by removing the cache (#15884)

    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.

    Performance comparison:

    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%

-----------------------------------------------------------------------

Summary of changes:
 ChangeLog          |   12 ++
 NEWS               |    2 +-
 string/strcoll_l.c |  344 ++++------------------------------------------------
 3 files changed, 39 insertions(+), 319 deletions(-)

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug libc/15884] Big performance problem in strcoll

[neleai at seznam dot cz]

https://sourceware.org/bugzilla/show_bug.cgi?id=15884

Ondrej Bilka <neleai at seznam dot cz> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #8 from Ondrej Bilka <neleai at seznam dot cz> ---
fixed.

-- 
You are receiving this mail because:
You are on the CC list for the bug.