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, 18 May 2012 03:10:45 +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
Rich Felker <bugdal at aerifal dot cx> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|SUSPENDED |NEW
CC| |bugdal at aerifal dot cx
--- Comment #2 from Rich Felker <bugdal at aerifal dot cx> 2012-05-18 03:10:45 UTC ---
If this bug still exists, it's valid, and should be fixed simply by removing
the SSE4 "optimization".
It's also worth noting, since Drepper mentioned the ugliness of special-casing,
that the special-casing of "short" (<32 byte) needles in the current two-way
code simply hurts performance. It's intended to avoid the 1-2 kb memset-zero at
startup, but even with this startup overhead cost, performance is still better
with the "long needle" variant of the code. I did a lot of performance testing
developing musl's strstr, and concluded that the optimal algorithm for
very-short needles (<=4 bytes) is rolling perfect hash in a machine word, and
that for longer needles, twoway with the bad character table always wins. I
also avoided the 1-2 kb memset by keeping a 256-bit table of which entries in
the 1-2 kb table are valid. This eliminates the startup overhead at the expense
of a few cycles in the inner loop.
--
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.