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

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

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

           Summary: QoI regression: strstr() slowed from O(n) to O(n^2) on
                    SSE4 machines
           Product: glibc
           Version: 2.11
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: libc
        AssignedTo: drepper.fsp@gmail.com
        ReportedBy: eblake@redhat.com


In glibc 2.9, strstr() was rewritten from a quadratic to a linear algorithm. 
However, in glibc 2.11, an SSE4 assembly version was added which speeds up
searches over short needles, but re-introduces the quadratic behavior of long
needles.

The best approach would be to bound the SSE4 brute-force assembly
implementation to a maximum needle length (perhaps 8 or 32 bytes), and defer to
the linear algorithm for long needles.  This has the benefits of avoiding the
startup overhead inherent in the linear algorithm (the overhead is
proportionately worse the shorter the needle is), while avoiding the quadratic
scaling for large needles (which are statistically less common, but all the
more important to avoid scaling effects).

-- 
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.