[Bug libc/5514] memmem is O(n^2), but should be O(n)

["eblake at redhat dot com" <sourceware-bugzilla at sourceware dot org>]

http://sourceware.org/bugzilla/show_bug.cgi?id=5514

--- Comment #17 from Eric Blake <eblake at redhat dot com> 2010-10-06 15:52:16 UTC ---
(In reply to comment #16)
> The assembly implementation is only for SSE4_2, and is correct.

No, it isn't.  The assembly implementation re-introduced the quadratic behavior
that existed pre-glibc 2.9, rather than keeping the linear behavior of the C
implementation (but only applies to strstr() and strcasestr(), and not
memmem()).

What REALLY needs to happen is a hybrid approach that uses assembly for short
needles, but C for long needles, since the cost of factoring the needle is
proportionately worse for short needles, and assembly can probably perform
brute force searching on short needles more efficiently than C code.  Quadratic
scaling of brute force doesn't matter if you cap the maximum needle length
where you use brute force.

Also, the (non-quadratic) SSE4.2 assembly approach needs to be extended to
cover memmem().

> 
> The straight C version is the one that's broken (AFAICT).

The fix for the C code has been posted to
 http://sourceware.org/bugzilla/show_bug.cgi?id=12092

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.