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

["cvs-commit at gcc dot gnu.org" <sourceware-bugzilla at sourceware dot org>]

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

--- Comment #12 from cvs-commit at gcc dot gnu.org <cvs-commit at gcc dot gnu.org> ---
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".

The branch, master has been updated
       via  584b18eb4df61ccd447db2dfe8c8a7901f8c8598 (commit)
      from  8a5c7897dd1c52ca74b06aaf5a3bacf0919c97aa (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=584b18eb4df61ccd447db2dfe8c8a7901f8c8598

commit 584b18eb4df61ccd447db2dfe8c8a7901f8c8598
Author: OndÅej BÃlka <neleai@seznam.cz>
Date:   Sat Dec 14 19:33:56 2013 +0100

    Add strstr with unaligned loads. Fixes bug 12100.

    A sse42 version of strstr used pcmpistr instruction which is quite
    ineffective. A faster way is look for pairs of characters which is uses
    sse2, is faster than pcmpistr and for real strings a pairs we look for
    are relatively rare.

    For linear time complexity we use buy or rent technique which switches
    to two-way algorithm when superlinear behaviour is detected.

-----------------------------------------------------------------------

Summary of changes:
 ChangeLog                                        |   14 +
 NEWS                                             |   24 +-
 sysdeps/x86_64/multiarch/Makefile                |    9 +-
 sysdeps/x86_64/multiarch/ifunc-impl-list.c       |    4 +-
 sysdeps/x86_64/multiarch/strcasestr-c.c          |   19 -
 sysdeps/x86_64/multiarch/strcasestr-nonascii.c   |   50 ---
 sysdeps/x86_64/multiarch/strcasestr.c            |   18 +-
 sysdeps/x86_64/multiarch/strstr-c.c              |   47 ---
 sysdeps/x86_64/multiarch/strstr-sse2-unaligned.S |  374 +++++++++++++++++++++
 sysdeps/x86_64/multiarch/strstr.c                |  388 ++--------------------
 10 files changed, 441 insertions(+), 506 deletions(-)
 delete mode 100644 sysdeps/x86_64/multiarch/strcasestr-c.c
 delete mode 100644 sysdeps/x86_64/multiarch/strcasestr-nonascii.c
 delete mode 100644 sysdeps/x86_64/multiarch/strstr-c.c
 create mode 100644 sysdeps/x86_64/multiarch/strstr-sse2-unaligned.S

-- 
You are receiving this mail because:
You are on the CC list for the bug.