Re: [PATCH] Use Quicksearch in strstr

[Rich Felker <dalias at libc dot org>]

On Tue, Oct 30, 2018 at 05:32:12PM +0000, Wilco Dijkstra wrote:
> Alexander Monakov wrote:
> > How does the worst case change look like (I think it's searching for "a{251}ba"
> > in "aaa...aaa" if memcmp works left-to-right)?  Does it make sense to move
> > needle length cutoff further below 254?

This "quicksearch" is fundamentally a bad algorithm. If it looks fast
in some cases, it's just a matter of getting lucky, and most likely
due to bad tuning or missed optimizations in the implementation of the
algorithm you're comparing it against. It's fundamentally a naive
O(nm) search that will be this bad in all cases except where the
bad-character table happens to let you advance a lot.

> To be fair you have to compare the worst case of one algorithm vs the worst
> case of another since they are different... Two-way is slow on searching for
> ba{254}b in a long sequence of ba{253}ba{253}. Two-way is only about 3 times
> faster on this case despite having a theoretical factor of 256/2 advantage.

Do you have a basis for calling this "slow"? It should be roughly one
comparison per byte. "Only 3x faster" doesn't sound slow to me.

> I don't think there is any gain slowing down common cases in order to
> reduce the worst-case difference (assuming that is feasibe).

This argument gets made about strstr every couple years, and every
time it's wrong. It's not that "common cases" (as a general class) are
faster with any naive algorithm. Only very specific cases will ever be
faster. Most common cases are roughly the same speed as with a good
algorithm, and some common cases, plus a lot more uncommon ones, are
catastrophically slower with a bad algorithm.

To my knowledge there is no good test for a case that won't become
catastrophically slower with a bad algorithm. If there is, I would be
very surprised if the same test doesn't naturally translate into an
optimized setup for two-way.

> > +      do
> > +     {
> > +       hs--;
> 
> > Doesn't this move hs out of bounds and thus invoke undefined behavior?
> 
> That's a theoretical issue given *(a+(i-1)), *((a-1)+i) and *((a+i)-1) behave
> identically.

Calling blatant undefined behavior "a theoretical issue" is not
something we should be doing in 2018.

Rich