[PATCH] Improve strstr performance of short needles

[Wilco Dijkstra]

Hi Gabriel,

>> I ran some tests on a powerpc64le machine and I noticed that, as the
>> haystack becomes larger, the search for a needle that is *not* in the
>> haystack, became slower with this change.
>
> That seems odd, particularly since the Two-Way algorithm is pretty slow
> for small needles (large preprocessing overhead and small skips).

I looked at bench-strstr again. There are cases where Two-Way wins by
10-15% when the string is found but for short strings the linear loop wins.
On average I can't see any performance difference.

However when iterating through 16K needles randomly chosen from natural
text I get the following speedups for different haystack and needle sizes:

    H64  H256 H4096
N2: 64%  73%  46%
N3: 74%  66%  37%
N4: 94%  92%  66%

As you can see the speedup is larger for small needles since the preprocessing
overhead of the Two-Way algorithm is significant. This is completely hidden by
the GLIBC test due to using just 1 needle.

Wilco