[PATCH] Use Quicksearch in strstr

[Ondřej Bílka]

On Mon, Oct 29, 2018 at 03:55:36PM +0000, Wilco Dijkstra wrote:
> This patch significantly improves performance of strstr by using Sunday's
> Quick-Search algorithm.  Due to its simplicity it has the best average
> performance of string matching algorithms on almost all inputs.  It uses a
> bad-character shift table to skip past mismatches.
> 
> The needle length is limited to 254 - combined with a hashed shift table
> this reduces the shift table memory 16 to 32 times, lowering preprocessing
> overhead and minimizing cache effects.  The needle limit also implies
> worst-case performance remains linear.
> 
> Small 1-4 byte needles use special case code which is typically faster.
> Very long needles continue to use the linear-time Two-Way algorithm.
> 
> The performance gain using the improved bench-strstr on Cortex-A72 is 2.1x.
> Due to the low overhead the gain is larger on small haystacks: haystacks of 64
> chars are ~3 times faster for needles of 5-16 chars.
>
Real benefit is fixing idiocy of calculating needle size before calling
strchr, code after that tries to make as this make cold path faster.

Better would be to call strchr again and if it still doesn't match for third time then
code after that shouldn't matter as long as its linear.
If you capture inputs of actual applications you will find what are bottlenecks.

That "benchmark" is complete garbage. In practice running time is
dominated by branch misprediction etc. But "benchmark" calls function
many times on same input leading to no branch misprediction. 

You couldn't do much with needle as inputs are really small,
precomputation is just too slow. Even strlen of needle would be
bottleneck.
Also strcmp when you take branch misprediction into account is too slow,
I tried lot of things for that comparison and nothing could beat doing
it byte-by-byte unrolled 4 times or so.

As for real inputs record someing with this
http://kam.mff.cuni.cz/~ondra/dryrun.tar.bz2
make
LD_PRELOAD=./dryrun_strstr.so bash
do something, exit bash
./summary_strstr

which prints statistic like this to see real data.

average size 21.28 needle size  6.67 comparisons  23.00 digraphs  0.22 trigraphs  0.00
calls     1907 succeed  61.4% latencies   0.0   0.0
s1    aligned to 4 bytes  81.9% aligned to 8 bytes  81.6% aligned to 16 bytes  31.7%
s2    aligned to 4 bytes  67.0% aligned to 8 bytes   8.0% aligned to 16 bytes   7.9%
needle found in n bytes: n <= 0:   7.9% n <= 1:   7.9% n <= 2:  11.9% n <= 3:  19.7%  n <= 4:  19.7% n <= 8:  19.7% n <= 16:  65.3% n <= 32: 81.1% n <= 64:  96.8%
needle size: n <= 0:   7.9% n <= 1:   7.9% n <= 2:   7.9% n <= 3:   7.9% n <= 4:  37.8% n <= 8:  96.9% n <= 16:  96.9% n <= 32: 100.0% n <= 64: 100.0%

For arm and anything with assembly strchr you would gain more by similar trick as I did for x64, 
for hot path its easy modification of strchr where you instead of one
character check first two characters where convient(function leaky_digraph), sometimes you check
only first one rather than trying to include character with unsuitable
alignment. Note that unaligned loads by one character more could be
faster than trying to shift vectors.

logic is following:
strstr(s,n) {
if (!n[0]) return s;
if (!n[1]) return strchr (s, n); // corner case, one-char needles are rare
   s = leaky_digraph(s, n[0], n[1]);
   if (!s)
     return NULL;
   for (i = 1; n[i] && s[i] == n[i]; i++);
   if (!n[i]) return s;
   return strstr_two_way(s,n);
}

Improvements after that are mostly QoI.
For bigger haystacks trick is to do code above in loop and find constants a,b,c,d s.t.
time(two_way) > a*(haystack-haystack_start)+b and c * characters_compared + d * leaky_digraph_calls > time(leaky_digraph_loop)
and add to loop chec to switch to two_way when
a*(haystack-haystack_start)+b < c * characters_compared + d * leaky_digraph_calls

One could optimize code more by iterating mask instead of calling
leaky_digraph again but thats to decrease constants in case where digraphs are quite
frequent.