Re: [PATCH] Use Quicksearch in strstr

[Wilco Dijkstra <Wilco dot Dijkstra at arm dot com>]

Rich Felker wrote:
> On Wed, Nov 07, 2018 at 04:01:51PM +0000, Wilco Dijkstra wrote:
>> Not a chance. You do realize I am measuring this stuff for real rather than
>> just making up random numbers? Worst-case performance of both algorithms
>> is very similar for needles up to 256. It's not possible to get 10x difference, let
>> alone 100x.
>
> I'm not either, but we are measuring different implementations,
> particularly of the underlying memcmp. But a better memcmp is not
> going to make it 100x faster. Maybe 10x at best, leaving a 10x
> difference still. And not all archs have a ridiculously fast memcmp.

A slow memcmp is obviously not an issue with the algorithm or implementation.
And it's something that can be easily fixed. It might even be feasible to mitigate
for a slow memcmp, for example splitting the memcmp into several smaller ones.

> Indeed, just re-testing on a glibc box, "quicksearch" takes 33 whole
> microseconds to search (and not find) a{90}ba in (ba{89}){9}. Two-way
> can do the same in 3 microseconds on this box, although glibc's (2.24
> from Debian) included two-way on this box is much slower and takes 12.
> So that's a 10x difference at 92 bytes (limitation of the measurement
> code from a third party I was using). At 256 bytes I'd expect more
> like a 25x difference.

Well using that input with a slow byte-by-byte memcmp, Quicksearch is less than 4
times as slow as Two-way on it's worst case. The same input of size 254 is 9.3 times
slower. But even this worst-worst case is not particularly slow and easily fixable
by not using a stupid memcmp. Or you could limit the needle size to something smaller
for such a target.

> Nobody has replied to my branch of this thread about limiting shift in
> the case of memory. I'm pretty confident it's right now so maybe I
> should just submit a patch. But it's frustrating that there is more
> interest in discussing bad algorithms than in improving the
> implementation of a good one.

I replied and benchmarked it - it's correct but doesn't make a significant difference. 
While some further tweaks are possible, I don't believe that Two-way could ever
be competitive with any of the modern algorithms - it needs to be at least 2-3
times faster, but you just can't speedup the matching process due to the way it
needs to be done in order to stay linear.

However if you feel strongly that you can write a faster version (or even a different
algorithm), then just go ahead. This implementation (and similar ones in gnulib, newlib,
musl, bsd etc) is quite ancient, the many hacks and badly integrated bad-char table
hasn't done it any good.

>> Citation needed. You clearly haven't ever tried Quicksearch. It beats Two-way 
>> in every single case on real inputs. The length of the needle matters only for the
>> worst case, and by limiting the needle size, you avoid quadratic behaviour.
>
> See above. I have tried it and it performs abysmally.

No. All you showed is that performance is bad if you use a slow byte-by-byte 
memcmp on a slow microarchitecture. That certainly doesn't prove anything
about Quicksearch.

>> Limiting the needle size to avoid quadratic behaviour is perfectly fine for GLIBC
>> since the goal is to avoid denial of service via specially crafted inputs.
>> 
>> It's impossible for strstr to always have identical performance on all possible
>> inputs - practically every algorithm has fast and slow cases. Rabin-Karp is
>> perhaps an exception given a good hash function. It's also 10x faster than
>> Two-way slow cases, so it's a candidate to replace Two-way.
>
> It's also quadratic, so it's not a candidate, unless you cap the
> length for which it's used very low.

Only if you manage to break the hash function. RK is actually more interesting for
really large needles given performance is practically independent of the size of the
needle. It not only handles the worst cases of other algorithms much faster but has
near identical performance for any input.

Wilco