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 Thu, Apr 18, 2019 at 01:51:14PM +0000, Wilco Dijkstra wrote:
> Hi Szabolcs,
>
> > in this case a large slowdown is not a real vulnerability.
>
> Absolutely, performance varies quite dramatically with different inputs. That
> is true for all algorithms even they are "real-time". Caches and branch
> predictors are not going away.
>
> > 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.
> needle size of 256). A simple memcmp at every character is significantly
> faster than Two-way on the first bad needle, and about the same performance
> on the second.
Then fix whatever bug made two-way slow on that case. It should not be
slow there.
> Also when reducing the size of the needle to 31 from 255 on my algorithm,
> there is only a 73% speedup for its worst case (bad needle 2). So reducing the
> cutoff doesn't really help the worst case since we're clearly not quadratic..
I don't follow. You mean two-way is only 73% faster on that needle?
That does not match previous findings, unless you've changed the
needle vs the 40x one nsz found (I didn't read the test case source in
depth but saw that it does not comment what the test cases it's
generating are).
Rich