Testing 2.16 release candidate with gnulib - quadratic behaviour detected in SSE42 strstr?

[Carlos O'Donell]

On 6/28/2012 7:21 AM, Eric Blake wrote:
>> Yes, if an strstr implementation takes more than 4 minutes to search for
>> a 100000 byte long string in a 2000000 byte long string, it's quadratic
>> behaviour.
> 
> Known bug:
> http://sourceware.org/bugzilla/show_bug.cgi?id=12100

Eric,

Thanks!

I've updated the issue and added the relevant people to the CC.

I've set the target milestone 2.17 so we can get this fixed in 
the next release.
 
>>
>> The O(n) worst-case algorithm with O(1) intermediate storage was introduced
>> in string/strstr.c in 2008. But sysdeps/x86_64/multiarch/strstr.c was added
>> in 2009; it looks like it intends to use Knuth-Morris-Pratt only on small
>> substrings (the original Knuth-Morris-Pratt is O(n) worst-case and uses
>> O(n) intermediate storage) and therefore is O(n²).
> 
> And an attempt has been started at fixing it:
> http://sourceware.org/ml/libc-alpha/2012-06/msg00124.html

Right, and that should get reviewed for and checked in for 2.17,
and backported if there are distribution maintainers that would
like that for 2.15 or 2.16.
 
Cheers,
Carlos.
-- 
Carlos O'Donell
Mentor Graphics / CodeSourcery
carlos_odonell@mentor.com
carlos@codesourcery.com
+1 (613) 963 1026