This is the mail archive of the
glibc-bugs@sourceware.org
mailing list for the glibc project.
[Bug libc/12100] QoI regression: strstr() slowed from O(n) to O(n^2) on SSE4 machines
- From: "bugdal at aerifal dot cx" <sourceware-bugzilla at sourceware dot org>
- To: glibc-bugs at sources dot redhat dot com
- Date: Fri, 29 Jun 2012 00:09:10 +0000
- Subject: [Bug libc/12100] QoI regression: strstr() slowed from O(n) to O(n^2) on SSE4 machines
- Auto-submitted: auto-generated
- References: <bug-12100-131@http.sourceware.org/bugzilla/>
http://sourceware.org/bugzilla/show_bug.cgi?id=12100
--- Comment #8 from Rich Felker <bugdal at aerifal dot cx> 2012-06-29 00:09:10 UTC ---
The regression should be fixed immediately by disabling the new SSE code
entirely and simply using the fast C implementation until someone can produce
SSE code without the O(n^2) pathology. In reality, SSE will not help you for
long needles (where 2way algo excels, and even approaches O(n/m) in most
real-world cases) so the SSE code should probably only be invoked when the
needle is sufficiently short.
As for the benchmarks, they seem to be from when the SSE code was first
introduced, and serve as propaganda showing how fast it is in best-case
situations. This is a rather useless benchmark. A real benchmark of strstr will
test things like searching for {a}^n in {{a}^{n-1}b}^n{a}^n as well as more
complicated periodicity cases that stress-test needle factorization. Testing
the best-case is never a valid benchmark; you have to test worst-case.
--
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.