Re: strstr is linear test fails on my machine with glibc 2.13

[Eric Blake]

On 07/19/2011 09:30 AM, Reuben Thomas wrote:
> I was interested to see this test fail, and digging inside, see
> comments assert that glibc>  2.12 should be OK. Looks therefore as if
> something's wrong. I'm using the glibc 2.13 shipped with Ubuntu natty
> on an x86_64 system. The test exits with status 142, i.e. 128 + 14,
> i.e. the 5-second alarm has fired. I have a 2.5GHz i5 Sandy Bridge
> CPU.

Known glibc bug when using glibc 2.11 or newer on an SSE4.2-enabled chip:
http://sourceware.org/bugzilla/show_bug.cgi?id=12100

> memmem is on the other hand diagnosed as linear on my system.

Yep - because memmem isn't "optimized" for small strings.

The _real_ fix would be to write a patch that uses hueristics - SSE4.2 
for short needles and linear algorithm for long needles (the SSE4.2 
optimizations are indeed faster for short needles, but scale 
quadratically; for large needles, using SSE4.2 doesn't provide quite the 
speedups).  But it takes time to write not only the patch, but also the 
timing programs that will definitively prove that we are not pessimizing 
speed over a large set of inputs (short vs. long needles, repetitive vs. 
unique needles, SSE4.2 vs. older chip, ...).

--
Eric Blake   address@hidden    +1-801-349-2682
Libvirt virtualization library http://libvirt.org