summary refs log tree commit diff
path: root/hurd/lookup-at.c
diff options
context:
space:
mode:
authorWilco Dijkstra <wdijkstr@arm.com>2019-06-12 11:38:52 +0100
committerWilco Dijkstra <wdijkstr@arm.com>2019-06-12 11:38:52 +0100
commit5e0a7ecb6629461b28adc1a5aabcc0ede122f201 (patch)
tree8dc29750e4e9405f670fd362daa47cbc2731700e /hurd/lookup-at.c
parent80b2bfb5350442ef1a781b0ee9dd44d61bd88f8a (diff)
downloadglibc-5e0a7ecb6629461b28adc1a5aabcc0ede122f201.tar.gz
glibc-5e0a7ecb6629461b28adc1a5aabcc0ede122f201.tar.xz
glibc-5e0a7ecb6629461b28adc1a5aabcc0ede122f201.zip
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.
Diffstat (limited to 'hurd/lookup-at.c')
0 files changed, 0 insertions, 0 deletions