]> git.ipfire.org Git - thirdparty/glibc.git/commit
Improve performance of memmem
authorWilco Dijkstra <wdijkstr@arm.com>
Wed, 12 Jun 2019 10:42:34 +0000 (11:42 +0100)
committerWilco Dijkstra <wdijkstr@arm.com>
Fri, 13 Sep 2019 15:41:34 +0000 (16:41 +0100)
commit612fba2fe9036732c5ee08f691c52365e5bd32c0
tree94759b9dba3a3dc3fa28ed6faad10315463d3fb8
parent796c5ee030deac07ed846d9531c1322d57c0a6c7
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)
ChangeLog
string/memmem.c