Re: [PATCH v2] Improve performance of strstr

[Rich Felker <dalias@libc.org>]

On Mon, Apr 15, 2019 at 10:24:15AM +0000, Wilco Dijkstra wrote:
> Hi Rich,
> 
> > On Fri, Apr 12, 2019 at 04:49:11PM +0000, Wilco Dijkstra wrote:
> >> Hi Szabolcs,
> >> 
> >> > please cc those who previously had objections against
> >> > the patch and ask if they sustain their objections
> >> > and if so what changes or demonstrations are needed
> >> > to move this forward.
> >> 
> >> I haven't seen any constructive objections nor received any reply
> >> when I asked for actual evidence of a claimed regression [1].
> >
> > I have already explained to you the cases which are going to perform
> > pathologically bad with your vaguely optimized version of the naive
> > O(nm) strstr. I don't have your specific hardware to run benchmarks,
> > but the order of magnitude here is so large that a big-O argument
> > suffices. If the proposed size limit were something like 24 or 32
> > rather than 256 that might not necessarily be the case.
> 
> 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.

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

> > I vaguely recall doing some testing on a glibc x86_64 box that showed
> > the magnitude of the problem; I can try to dig that up or do it again
> > if you really want to see it.
> 
> 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.

Rich