This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: Testing 2.16 release candidate with gnulib - quadratic behaviourdetected in SSE42 strstr?
- From: Carlos O'Donell <carlos_odonell at mentor dot com>
- To: Eric Blake <eblake at redhat dot com>
- Cc: Bruno Haible <bruno at clisp dot org>, libc-alpha <libc-alpha at sourceware dot org>
- Date: Thu, 28 Jun 2012 09:50:20 -0400
- Subject: Re: Testing 2.16 release candidate with gnulib - quadratic behaviourdetected in SSE42 strstr?
- References: <4FEBDA04.6010709@mentor.com> <1369274.lP780jBnqt@linuix> <4FEC3E20.2060703@redhat.com>
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