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

["bugdal at aerifal dot cx" <sourceware-bugzilla at sourceware dot org>]

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.