Re: [PATCH v2] Improve performance of strstr

[Zack Weinberg <zackw at panix dot com>]

On Mon, Apr 15, 2019 at 2:02 PM Wilco Dijkstra <Wilco.Dijkstra@arm.com> wrote:
> Hi Rich,
...
> >> Yes, without a reproducible example I can't see what your issue is. You
> >> can't make it go quadratic because it simply isn't.
> >
> > Obviously it's not unbounded because you have a (very large) bound on
> > the size, 256. I can make it do a 256-byte strcmp for nearly every
> > byte of the input haystack. Maybe because of vectorization on some
> > targets that's only 16x slower than the current code rather than 256x
> > slower, but it's still a lot slower.
>
> No you can't. It's impossible to make it do a full 256 byte memcmp every
> character. And bad cases are not bad because of the time spent comparing
> strings - they are bad because of mispredicted branches. So it's not possible
> to compare bad cases without benchmarking actual examples on modern
> CPUs.

This discussion has been going in circles for quite some time now.

Wilco, Rich, I think it would help a lot if you could BOTH write down
some example needle and haystack pairs that you believe will
demonstrate significantly improved performance with your preferred
algorithm, and/or pathologically slow performance with your
dispreferred algorithm.  Even without specific numbers, that will give
everyone something concrete to argue over, at least.

zw