| Summary: | strstr function very slow. | ||
|---|---|---|---|
| Product: | glibc | Reporter: | Xavier Oswald <xoswald> |
| Component: | libc | Assignee: | Maxim Kuvyrkov <maxim.kuvyrkov> |
| Status: | RESOLVED FIXED | ||
| Severity: | normal | CC: | carlos_odonell, eblake, glibc-bugs, maxim.kuvyrkov |
| Priority: | P2 | Flags: | fweimer:
security-
|
| Version: | 2.10 | ||
| Target Milestone: | --- | ||
| Host: | Target: | ||
| Build: | Last reconfirmed: | ||
| Attachments: |
Source code
Data file |
||
|
Description
Xavier Oswald
2010-05-17 09:27:05 UTC
Created attachment 4798 [details]
Source code
Created attachment 4799 [details]
Data file
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 [1] fix performance regression for small needles -- which is what the testcase for this bug exercises. Ondrej's patches [2] appear to further improve performance for x86. [1] http://sourceware.org/ml/libc-alpha/2012-05/msg01228.html [2] http://sourceware.org/ml/libc-alpha/2012-06/msg00027.html (In reply to comment #5) > We expect this to be fixed in 2.17. > > Maxim's patches [1] fix performance regression for small needles -- which is > what the testcase for this bug exercises. Ondrej's patches [2] appear to > further improve performance for x86. > > [1] http://sourceware.org/ml/libc-alpha/2012-05/msg01228.html > [2] http://sourceware.org/ml/libc-alpha/2012-06/msg00027.html Note that [2] was just a summary of Ondrej's benchmarking; searching for an actual patch of his turns up this link: http://sourceware.org/ml/libc-help/2011-11/msg00011.html Maxim, I thought this had already been checked in and fixed? Hm, I thought I marked this FIXED. Apparently, I didn't. Thanks Carlos. |