commit 91372f000197deb148fbd6d6b5a8d93327119c3e
Author: Wilco Dijkstra <wdijkstr@arm.com>
Date:   Wed Jun 12 11:42:34 2019 +0100

    Improve performance of memmem
   
    This patch significantly improves performance of memmem using a novel
    modified Horspool algorithm.  Needles up to size 256 use a bad-character
    table indexed by hashed pairs of characters to quickly skip past mismatches.
    Long needles use a self-adapting filtering step to avoid comparing the whole
    needle repeatedly.
   
    By limiting the needle length to 256, the shift table only requires 8 bits
    per entry, lowering preprocessing overhead and minimizing cache effects.
    This limit also implies worst-case performance is linear.
   
    Small needles up to size 2 use a dedicated linear search.  Very long needles
    use the Two-Way algorithm (to avoid increasing stack size or slowing down
    the common case, inlining is disabled).
   
    The performance gain is 6.6 times on English text on AArch64 using random
    needles with average size 8.
   
    Tested against GLIBC testsuite and randomized tests.
   
    Reviewed-by: Szabolcs Nagy <szabolcs.nagy@arm.com>
   
        * string/memmem.c (__memmem): Rewrite to improve performance.
   
    (cherry picked from commit 680942b0167715e123d934b609060cd382f8e39f)

commit 1ad15e008cca9a7189c26d756d20d07acf4855df
Author: Wilco Dijkstra <wdijkstr@arm.com>
Date:   Wed Jun 12 11:38:52 2019 +0100

    Improve performance of strstr
   
    This patch significantly improves performance of strstr using a novel
    modified Horspool algorithm.  Needles up to size 256 use a bad-character
    table indexed by hashed pairs of characters to quickly skip past mismatches.
    Long needles use a self-adapting filtering step to avoid comparing the whole
    needle repeatedly.
   
    By limiting the needle length to 256, the shift table only requires 8 bits
    per entry, lowering preprocessing overhead and minimizing cache effects.
    This limit also implies worst-case performance is linear.
   
    Small needles up to size 3 use a dedicated linear search.  Very long needles
    use the Two-Way algorithm.
   
    The performance gain using the improved bench-strstr on Cortex-A72 is 5.8
    times basic_strstr and 3.7 times twoway_strstr.
   
    Tested against GLIBC testsuite, randomized tests and the GNULIB strstr test
    (https://git.savannah.gnu.org/cgit/gnulib.git/tree/tests/test-strstr.c).
   
    Reviewed-by: Szabolcs Nagy <szabolcs.nagy@arm.com>
   
        * string/str-two-way.h (two_way_short_needle): Add inline to avoid
        warning.
        (two_way_long_needle): Block inlining.
        * string/strstr.c (strstr2): Add new function.
        (strstr3): Likewise.
        (STRSTR): Completely rewrite strstr to improve performance.
   
    (cherry picked from commit 5e0a7ecb6629461b28adc1a5aabcc0ede122f201)