This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH v2] Improve performance of strstr
On 18/04/2019 16:20, Rich Felker wrote:
> On Thu, Apr 18, 2019 at 01:51:14PM +0000, Wilco Dijkstra wrote:
>>> i think even doing memcmp at every byte position is not a
>>> denial of service concern if the needle is <= 256 bytes.
>>> (maybe we should use a lower limit? <= 64?)
>>
>> It couldn't be since its worst case isn't actually much worse (~2.2 times for
>
> The worst is 40x, and it's going to be much much worse on archs
> without big vectors.
40x happens on an input where twoway is fast and new algo is slow,
there are examples the other way around.
if we compare the worst known case of twoway to worst known case
of new algo then the slow down is < 2x according to
https://sourceware.org/ml/libc-alpha/2019-04/msg00404.html
(bad needle 1 is bad for twoway, bad needle 2 is bad for new algo)