This is the mail archive of the glibc-bugs@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[Bug libc/12100] QoI regression: strstr() slowed from O(n) to O(n^2) on SSE4 machines


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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]