Re: [PATCH v2] Improve performance of strstr

[Wilco Dijkstra <Wilco.Dijkstra@arm.com>]

Hi Rich,

>> The O notation means O (256 N) is equivalent to O (N), ie. linear
>> performance in the worst case. And that is what matters for large inputs.
>
> I know what big O notation means. My point is that 256 is a
> sufficiently large number that, for practical purposes, the presence
> or absence of the M factor (whose value can be up to 256) in O(N) vs
> O(MN) is more significant than any small constant factors.

No, you can't gloss over one constant factor but emphasise another.
The constant factor is much smaller in my algorithm and actually gets
better (relatively) when you encounter bad cases. As a result worst
cases perform about the same even with needles of 256 characters.

>> The average runtime of my algorithm is actually sublinear. So in that
>> sense Two-Way performs pathologically bad.
>
> For strstr, it's never sublinear because it operates on
> null-terminated strings (but the linear term can have a very small
> constant because of fast incremental strnlen-like operation, if you
> want). 

strstr requires strnlen of course but the main algorithm is still sublinear.
As a result performance improves with larger needles and the relative
amount of time spent in strnlen increases. Asymptotically it ends up
as fast as strnlen.

> For memmem, of course it can be sublinear. The widely used
> variant of twoway (used in both glibc and musl) does the jump table
> that makes it sublinear (or for strstr, smaller linear-term
> coefficient) already. If you're this unaware of what the current code
> is doing, you shouldn't be trying to replace it with something naive
> but rather trying to understand it and if/how it can be improved.

Well if you've actually seen the existing code, you'd know that it does
not use a skip table for all common cases. And when it uses one, it
actually slows down the worst case by an order of magnitude.
As a result Two-Way performs absolutely abysmally both in common
cases as well as worst cases. It's almost as if people designed it to be
as bad as possible!

Eg. normalised performance from GLIBC bench-strstr test:

                                          basic_strstr    twoway_strstr   strstr(new)
Length 65536/ 16, alignment  1/11, found: 3.07            1.0             11.0

Yes, twoway_strstr is 3 times SLOWER than a trivial quadratic loop...

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

Wilco