Sourceware Bugzilla – Bug 11607
strstr function very slow.
Last modified: 2012-09-04 20:02:10 UTC
I think tere are a huge regression for the strstr function between version 2.7
In our code we use the 'strstr' function a lot and became to the fact that
strstr is having a strange behaviour.
I attach 2 file so you can test it.
$gcc test-strstr.c -o test
$time test 10000
Some results (User Time):
Ubuntu 8.04 : 10s (glibc 2.7)
Ubuntu 9.04 : 1m20s (glibc 2.10)
Ubuntu 10.04 : 1m20s (glibc 2.10)
Debian lenny : 8s (glibc 2.7)
Debian Squeeze : 1m10s (glibc 2.10)
The results are the same on AMD64 and i386 architectures.
Created attachment 4798 [details]
Created attachment 4799 [details]
in test-strstr.c, just try to match a string a the end of the file test-strstr.txt
I tested with a needle > 16 and < 16, it doesn't change anything.
In glibc 2.7, the strstr() implementation has worst-case quadratic complexity of
O(m*n) (m the length of the haystack, n the length of the string); and gnulib
introduced a test case that demonstrated this quadratic complexity could be used
as a denial of service attack on any program that searches for a large needle
within a large string. With glibc 2.10, the strstr() has a guaranteed linear
complexity of O(m+n), but that reduced algorithmic complexity comes with a
larger startup cost of factoring the needle, where the shorter the needle is,
the larger proportion of the overall strstr() is spent on that factoring.
Furthermore, the glibc 2.7 implementation has had years of tweaking to be
cache-line friendly and tuned for various architectures, while my 2.10
implementation is relatively new, and probably still has some room for
improvements (at any rate, I know that when I wrote it, I was catering to large
needles and large haystacks, and was focused on the algorithmic improvement,
rather than the cache-line effects of small needles).
With appropriate benchmarking, it may be worth altering the implementation to be
a hybrid, where short-enough needles are handled with the older brute force
implementation - even if it is quadratic, less startup cost might be better for
short needles even if it results in more comparisons against the haystack for
some of those needles.
Furthermore, strstr() has a lousy interface when compared with regex searching.
That is, if you repeatedly search for the same needle, the use of re_compile()
is spent only once, while you can reuse that compiled needle across multiple
re_search() calls. But with strstr(), the cost of factoring the needle is spent
on every call. Perhaps we should consider exposing some new interfaces that
separate the strstr() factorization startup code from the body that uses the
factored needle for the actual search.
We expect this to be fixed in 2.17.
Maxim's patches  fix performance regression for small needles -- which is what the testcase for this bug exercises. Ondrej's patches  appear to further improve performance for x86.
(In reply to comment #5)
> We expect this to be fixed in 2.17.
> Maxim's patches  fix performance regression for small needles -- which is
> what the testcase for this bug exercises. Ondrej's patches  appear to
> further improve performance for x86.
>  http://sourceware.org/ml/libc-alpha/2012-05/msg01228.html
>  http://sourceware.org/ml/libc-alpha/2012-06/msg00027.html
Note that  was just a summary of Ondrej's benchmarking; searching for an actual patch of his turns up this link:
I thought this had already been checked in and fixed?
Hm, I thought I marked this FIXED. Apparently, I didn't. Thanks Carlos.