Re: Testing 2.16 release candidate with gnulib - quadratic behaviourdetected in SSE42 strstr?

[Eric Blake <eblake at redhat dot com>]

On 06/28/2012 05:19 AM, Bruno Haible wrote:
> Hi Carlos,
> 
>> (d) strstr
>>
>> This is the one that worries me.
>>
>> configure:121073: checking whether strstr works in linear time
>> configure:121161: gcc -lm -Wl,-rpath=/scratch/carloso/build4-lucid-cs/install//lib64:/scratch/carloso/build4-lucid-cs/install//usr/lib64 -Wl,--dynamic-linker=/scratch/carloso/build4-lucid-cs/install//lib64/ld-linux-x86-64.so.2 -std=gnu99 -o conftest -g -O2 -nostdinc -I/usr/local/tools/gcc-4.3.3/lib/gcc/x86_64-unknown-linux-gnu/4.3.2/include-fixed -I/scratch/carloso/build4-lucid-cs/install//usr/include -I/usr/local/tools/gcc-4.3.3/lib/gcc/x86_64-unknown-linux-gnu/4.3.2/include -Wall  conftest.c  >&5
>> configure:121165: $? = 0
>> configure:121171: ./conftest
>> configure:121175: $? = 142
>> configure: program exited with status 142

> 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

> 
> 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

-- 
Eric Blake   eblake@redhat.com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

Attachment: signature.asc
Description: OpenPGP digital signature