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

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

[eblake at redhat dot com]

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.

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

[drepper.fsp at gmail dot com]

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

Ulrich Drepper <drepper.fsp at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |SUSPENDED
   Last reconfirmed|                            |2010.10.07 03:20:01
     Ever Confirmed|0                           |1

--- Comment #1 from Ulrich Drepper <drepper.fsp at gmail dot com> 2010-10-07 03:20:01 UTC ---
I don't like distinguishing based on the length of the needles.  But I might
consider it as an interim solution.

Regardless, this is something for somebody who cares about these cases to write
a patch for.  In real life this really isn't important.  Change the status when
you come up with a patch.

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

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

[hjl.tools at gmail dot com]

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

H.J. Lu <hjl.tools at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hjl.tools at gmail dot com

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

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

[ppluzhnikov at google dot com]

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

Paul Pluzhnikov <ppluzhnikov at google dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ppluzhnikov at google dot
                   |                            |com

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

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

[bugdal at aerifal dot cx]

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.

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

[carlos_odonell at mentor dot com]

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

Carlos O'Donell <carlos_odonell at mentor dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |carlos_odonell at mentor
                   |                            |dot com, liubov.dmitrieva
                   |                            |at gmail dot com, neleai at
                   |                            |seznam dot cz
         AssignedTo|drepper.fsp at gmail dot    |unassigned at sourceware
                   |com                         |dot org
   Target Milestone|---                         |2.17

--- Comment #3 from Carlos O'Donell <carlos_odonell at mentor dot com> 2012-06-28 13:46:25 UTC ---
We want this fixed in 2.17.

We expect that Maxim[1] or Ondrej's[2] patches will fix this.

[1] http://sourceware.org/ml/libc-alpha/2012-05/msg01228.html

[2] http://sourceware.org/ml/libc-alpha/2012-06/msg00027.html

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

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

[maxim.kuvyrkov at gmail dot com]

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

Maxim Kuvyrkov <maxim.kuvyrkov at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |maxim.kuvyrkov at gmail dot
                   |                            |com

--- Comment #4 from Maxim Kuvyrkov <maxim.kuvyrkov at gmail dot com> 2012-06-28 22:29:51 UTC ---
As things stand, my patches ([1] quoted above) won't address the O(n^2) -> O(n)
problem for SSE4 machines -- they fix BZ #11607 instead.

Ondrej's patches, on the other hand, are supposed to fix the O(n^2) problem for
x86, but they haven't been posted yet.

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

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

[eblake at redhat dot com]

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

--- Comment #5 from Eric Blake <eblake at redhat dot com> 2012-06-28 22:41:29 UTC ---
(In reply to comment #3)
> We want this fixed in 2.17.
> 
> We expect that Maxim[1] or Ondrej's[2] patches will fix this.
> 
> [1] http://sourceware.org/ml/libc-alpha/2012-05/msg01228.html
> 
> [2] http://sourceware.org/ml/libc-alpha/2012-06/msg00027.html

Note that [2] was just a summary of Ondrej's benchmarking; searching for an
actual patch of his turns up this link:

http://sourceware.org/ml/libc-help/2011-11/msg00011.html

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

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

[neleai at seznam dot cz]

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

--- Comment #6 from Ondrej Bilka <neleai at seznam dot cz> 2012-06-28 23:54:40 UTC ---
I will submit a patch after freeze ends. I made several performance
improvements from what I suggested.
On Thu, Jun 28, 2012 at 10:41:29PM +0000, eblake at redhat dot com wrote:
> http://sourceware.org/bugzilla/show_bug.cgi?id=12100
> 
> --- Comment #5 from Eric Blake <eblake at redhat dot com> 2012-06-28 22:41:29 UTC ---
> (In reply to comment #3)
> > We want this fixed in 2.17.
> > 
> > We expect that Maxim[1] or Ondrej's[2] patches will fix this.
> > 
> > [1] http://sourceware.org/ml/libc-alpha/2012-05/msg01228.html
> > 
> > [2] http://sourceware.org/ml/libc-alpha/2012-06/msg00027.html
> 
> Note that [2] was just a summary of Ondrej's benchmarking; searching for an
> actual patch of his turns up this link:
> 
> http://sourceware.org/ml/libc-help/2011-11/msg00011.html
> 
> -- 
> 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.

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

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

[eblake at redhat dot com]

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

--- Comment #7 from Eric Blake <eblake at redhat dot com> 2012-06-29 00:01:42 UTC ---
(In reply to comment #6)
> I will submit a patch after freeze ends. I made several performance
> improvements from what I suggested.

Can you please submit the patch now, so we can at least look at it, even if it
is not polished?  I know last month the list said we might wait until after
2.17 to review it, but...

> > (In reply to comment #3)
> > > We want this fixed in 2.17.

...this statement makes me believe that people are starting to realize the
severity of the regression, and want it fixed sooner.

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

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

[bugdal at aerifal dot cx]

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.

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

[liubov.dmitrieva at gmail dot com]

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

--- Comment #9 from Liubov Dmitrieva <liubov.dmitrieva at gmail dot com> 2012-06-29 12:57:25 UTC ---
SSE42 strstr is quadratic at worst but still better in general cases than
current 2way algo.

If new Ondrej's SSE algorithm or current 2way version with applied path [1]
will be better for real life cases then SSE42 strstr should be eliminated.

But I agree with Ulrich that for strstr long needles is not important in real
life. People use memmem instead.

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

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

[bugdal at aerifal dot cx]

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

--- Comment #10 from Rich Felker <bugdal at aerifal dot cx> 2012-06-29 13:06:46 UTC ---
"People will use memmem instead" is definitely false, for two reasons.

1. memmem is not part of the C language; it's a GNU function. Portable code
will not be using it at all.

2. If the input data is a C string, using memmem requires first calling strlen
on both the needle and haystack. If the haystack is very large but the needle
is expected to be found near the beginning, this increases runtime by a huge
margin.

As usual, Drepper was wrong. A quadratic implementation of strstr is just
pathologically bad and is subject to DoS in real-world cases (think of a
webserver doing text search on user-generated content (perhaps a forum) on
behalf of clients; a single client's requests, without any DDoS network, can
easily overwhelm the machine with a few carefully crafted needles and
haystacks).

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

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

[liubov.dmitrieva at gmail dot com]

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

--- Comment #11 from Liubov Dmitrieva <liubov.dmitrieva at gmail dot com> 2012-06-29 15:34:07 UTC ---
Ok,

This patch removes quadratic SSE42 strstr for x86_64 and for x86_32

http://sourceware.org/ml/libc-alpha/2012-06/msg00788.html

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

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

[carlos at systemhalted dot org]

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

Carlos O'Donell <carlos at systemhalted dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|carlos_odonell at mentor    |carlos at systemhalted dot
                   |dot com                     |org

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

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

[hannes at stressinduktion dot org]

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

Hannes Frederic Sowa <hannes at stressinduktion dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hannes at stressinduktion
                   |                            |dot org

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

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

[cvs-commit at gcc dot gnu.org]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="UTF-8", Size: 6194 bytes --]

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.
>From glibc-bugs-return-20479-listarch-glibc-bugs=sources.redhat.com@sourceware.org Mon Dec 16 01:31:19 2013
Return-Path: <glibc-bugs-return-20479-listarch-glibc-bugs=sources.redhat.com@sourceware.org>
Delivered-To: listarch-glibc-bugs@sources.redhat.com
Received: (qmail 19539 invoked by alias); 16 Dec 2013 01:31:19 -0000
Mailing-List: contact glibc-bugs-help@sourceware.org; run by ezmlm
Precedence: bulk
List-Id: <glibc-bugs.sourceware.org>
List-Subscribe: <mailto:glibc-bugs-subscribe@sourceware.org>
List-Post: <mailto:glibc-bugs@sourceware.org>
List-Help: <mailto:glibc-bugs-help@sourceware.org>, <http://sourceware.org/lists.html#faqs>
Sender: glibc-bugs-owner@sourceware.org
Delivered-To: mailing list glibc-bugs@sourceware.org
Received: (qmail 19068 invoked by uid 55); 16 Dec 2013 01:31:12 -0000
From: "cvs-commit at gcc dot gnu.org" <sourceware-bugzilla@sourceware.org>
To: glibc-bugs@sourceware.org
Subject: [Bug build/14120] build process creates autom4te.cache directory in source dir
Date: Mon, 16 Dec 2013 01:31:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: glibc
X-Bugzilla-Component: build
X-Bugzilla-Version: unspecified
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: cvs-commit at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P2
X-Bugzilla-Assigned-To: allan at archlinux dot org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-14120-131-YH9rmMYzKS@http.sourceware.org/bugzilla/>
In-Reply-To: <bug-14120-131@http.sourceware.org/bugzilla/>
References: <bug-14120-131@http.sourceware.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://sourceware.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2013-12/txt/msg00125.txt.bz2
Content-length: 1661

http://sourceware.org/bugzilla/show_bug.cgi?id\x14120

--- Comment #11 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  8894bad34cc9c11e89ee2594f2d75893edb1d96c (commit)
      from  73616a74274223356c99dda66234f54932bb8c16 (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ˆ94bad34cc9c11e89ee2594f2d75893edb1d96c

commit 8894bad34cc9c11e89ee2594f2d75893edb1d96c
Author: Allan McRae <allan@archlinux.org>
Date:   Mon Dec 16 11:25:04 2013 +1000

    Add --enable-maintainer-mode configure option

    Autoconf is tested for and run if needed only when --enable-maintainer-mode
    is used on configure.  This results in the autom4te.cache directory only
    being written in the source directory during configure if automatic
    autoconf usage is requested.

    Fixes BZ #14120.

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

Summary of changes:
 ChangeLog    |    5 +++++
 configure    |   46 ++++++++++++++++++++++++++++++----------------
 configure.ac |   40 ++++++++++++++++++++++++----------------
 3 files changed, 59 insertions(+), 32 deletions(-)

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

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

[allan at archlinux dot org]

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

Allan McRae <allan at archlinux dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |allan at archlinux dot org
         Resolution|---                         |FIXED

--- Comment #13 from Allan McRae <allan at archlinux dot org> ---
SSE4.2 routines have been replaced.

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

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

[siddhesh at redhat dot com]

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

Siddhesh Poyarekar <siddhesh at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |marczakk at poczta dot onet.pl

--- Comment #14 from Siddhesh Poyarekar <siddhesh at redhat dot com> ---
*** Bug 16502 has been marked as a duplicate of this bug. ***

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

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

[jackie.rosen at hushmail dot com]

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

Jackie Rosen <jackie.rosen at hushmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jackie.rosen at hushmail dot com

--- Comment #16 from Jackie Rosen <jackie.rosen at hushmail dot com> ---
*** Bug 260998 has been marked as a duplicate of this bug. ***
Seen from the domain http://volichat.com
Page where seen: http://volichat.com/adult-chat-rooms
Marked for reference. Resolved as fixed @bugzilla.

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

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

[schwab at sourceware dot org]

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

Andreas Schwab <schwab at sourceware dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|jackie.rosen at hushmail dot com   |

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

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

[fweimer at redhat dot com]

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

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
              Flags|                            |security-

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

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

[cvs-commit at gcc dot gnu.org]

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

--- Comment #17 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  daa4db69fc5b8de46755c3da8a068d36ca8ad8c3 (commit)
      from  772e741ba5afede4892078102a620e30aeac0c87 (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=daa4db69fc5b8de46755c3da8a068d36ca8ad8c3

commit daa4db69fc5b8de46755c3da8a068d36ca8ad8c3
Author: H.J. Lu <hjl.tools@gmail.com>
Date:   Thu Aug 20 12:47:20 2015 -0700

    Remove the unused IFUNC files

    sysdeps/i386/i686/multiarch/strcasestr-c.c became unused after

    commit 1818483b15d22016b0eae41d37ee91cc87b37510
    Author: Andreas Schwab <schwab@suse.de>
    Date:   Wed Dec 18 11:53:27 2013 +1000

        Remove use of SSE4.2 functions for strstr on i686

    which contains

    -sysdep_routines += strcspn-c strpbrk-c strspn-c strstr-c strcasestr-c
    +sysdep_routines += strcspn-c strpbrk-c strspn-c

    sysdeps/x86_64/multiarch/strcasestr.c became useless after

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

    which changes sysdeps/x86_64/multiarch/strcasestr.c to

    libc_ifunc (__strcasestr, __strcasestr_sse2);

    This patch removes these file.

        * i386/i686/multiarch/strcasestr-c.c: Removed.
        * x86_64/multiarch/strcasestr.c: Likewise.
        * x86_64/multiarch/ifunc-impl-list.c (__libc_ifunc_impl_list):
        Remove strcasestr.

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

Summary of changes:
 sysdeps/i386/i686/multiarch/strcasestr-c.c |    4 ----
 sysdeps/x86_64/multiarch/ifunc-impl-list.c |    4 ----
 sysdeps/x86_64/multiarch/strcasestr.c      |   13 -------------
 3 files changed, 0 insertions(+), 21 deletions(-)
 delete mode 100644 sysdeps/i386/i686/multiarch/strcasestr-c.c
 delete mode 100644 sysdeps/x86_64/multiarch/strcasestr.c

-- 
You are receiving this mail because:
You are on the CC list for the bug.
>From glibc-bugs-return-29332-listarch-glibc-bugs=sources.redhat.com@sourceware.org Fri Aug 21 09:35:46 2015
Return-Path: <glibc-bugs-return-29332-listarch-glibc-bugs=sources.redhat.com@sourceware.org>
Delivered-To: listarch-glibc-bugs@sources.redhat.com
Received: (qmail 28635 invoked by alias); 21 Aug 2015 09:35:45 -0000
Mailing-List: contact glibc-bugs-help@sourceware.org; run by ezmlm
Precedence: bulk
List-Id: <glibc-bugs.sourceware.org>
List-Subscribe: <mailto:glibc-bugs-subscribe@sourceware.org>
List-Post: <mailto:glibc-bugs@sourceware.org>
List-Help: <mailto:glibc-bugs-help@sourceware.org>, <http://sourceware.org/lists.html#faqs>
Sender: glibc-bugs-owner@sourceware.org
Delivered-To: mailing list glibc-bugs@sourceware.org
Received: (qmail 28573 invoked by uid 48); 21 Aug 2015 09:35:40 -0000
From: "bluebat at member dot fsf.org" <sourceware-bugzilla@sourceware.org>
To: glibc-bugs@sourceware.org
Subject: [Bug localedata/16905] New collation for hanzi
Date: Fri, 21 Aug 2015 09:35:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: glibc
X-Bugzilla-Component: localedata
X-Bugzilla-Version: unspecified
X-Bugzilla-Keywords:
X-Bugzilla-Severity: enhancement
X-Bugzilla-Who: bluebat at member dot fsf.org
X-Bugzilla-Status: NEW
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P2
X-Bugzilla-Assigned-To: unassigned at sourceware dot org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags: security-
X-Bugzilla-Changed-Fields:
Message-ID: <bug-16905-131-PN5eVkBU2s@http.sourceware.org/bugzilla/>
In-Reply-To: <bug-16905-131@http.sourceware.org/bugzilla/>
References: <bug-16905-131@http.sourceware.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://sourceware.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-08/txt/msg00372.txt.bz2
Content-length: 334

https://sourceware.org/bugzilla/show_bug.cgi?id\x16905

--- Comment #4 from Wei-Lun Chao <bluebat at member dot fsf.org> ---
http://data.gov.tw/node/5961
Upstream license changed to "CC Attribution 4.0 international" compatible:
http://data.gov.tw/license

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