Re: [PATCH] Use memmem algorithm for strstr

Hi Eric,

> Is the new code faster than strstr[34] on short needles, or should you
> be keeping those versions around?

Well it depends. For really short haystacks they can be faster, but not for
long ones. However even if it were faster to use special code for short
needles, there is a misprediction cost from having to choose between the
various cases, so it tends to be faster overall to let the main algorithm deal
with them. I'm thinking of reducing inititalization overhead for small needles
by using a smaller hash table. Alternatively, the space-optimized version is
actually faster for very small haystacks.

> Calling strlen (ne) can be wasteful for someone that calls
> strstr("short", "super_long.....") - such callers will always get an
> answer of NULL, but the question is how much dead work did we do in the
> meantime.  My original Two-Way implementation tried hard to not compute
> the bounds of EITHER needle or haystack in isolation, but rather made a
> first pass through both simultaneously to detect early exit
> opportunities long before an unbounded strlen() on a disproportionately
> long counterpart.  Thus, I think this code should be using strnlen (ne,
> 256) before deciding to switch to Two-Way, rather than an unbounded length.

I don't believe we should optimize for such an uncommon case. That loop
caused a significant slowdown so I removed it a while back:
http://www.sourceware.org/ml/libc-alpha/2018-07/msg00636.html

Using strnlen is less bad than a byte-oriented loop, however it's still slower than
strlen, so it is better to just get the needle length and not worry about rare
corner cases.

> +  /* Use Two-Way algorithm for very long needles.  */
> +  if (__builtin_expect (ne_len > 256, 0))
> +    return two_way_long_needle (hs, hs_len, ne, ne_len);

> Is hs_len accurate (or even ne_len, if you take my suggestion to use
> strnlen() in its compuatation)?  Or do you first need to (re-)compute
> accurate lengths?

ne_len must be accurate for Two-way to work. hs_len doesn't since it always
checks AVAILABLE first to ensure there is enough data left.

> +      if (__builtin_expect (hs > end, 0))
> +     {
> +       end += strnlen (end + m1 + 1, 2048);

> Why hard-coded 2048 here, vs. ne_len|512 above?

Using ne_len | 512 ensures we can early-exit if haystack is smaller than needle
(not sure whether Two-way will work in that case, but that's an invariant I kept).

We don't want to waste time reading ahead too much since it's likely there will
be an early match. However once we've paid the startup overhead and finished
with the initial data without finding a match, the overhead of reading ahead
larger blocks is much lower (and reading more reduces the overhead of strnlen).

Btw badly implemented readahead kills the efficiency of all known Two-way
implementations in GLIBC, gnulib, MUSL, newlib etc. I don't get why Two-way is
in such widespread use, it's the worst and slowest algorithm for typical inputs...

Cheers,
Wilco