This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH v4] Improve performance of strstr
- From: Szabolcs Nagy <Szabolcs dot Nagy at arm dot com>
- To: Wilco Dijkstra <Wilco dot Dijkstra at arm dot com>, "libc-alpha at sourceware dot org" <libc-alpha at sourceware dot org>, Zack Weinberg <zackw at panix dot com>, Adhemerval Zanella <adhemerval dot zanella at linaro dot org>
- Cc: nd <nd at arm dot com>
- Date: Tue, 11 Jun 2019 09:16:06 +0000
- Subject: Re: [PATCH v4] Improve performance of strstr
- References: <VI1PR0801MB2127491FFC8DB60747AC0D06833E0@VI1PR0801MB2127.eurprd08.prod.outlook.com> <VI1PR0801MB2127F191C16D4322D29B7A5683310@VI1PR0801MB2127.eurprd08.prod.outlook.com> <VI1PR0801MB21271AC640825A58CACF22FC83020@VI1PR0801MB2127.eurprd08.prod.outlook.com> <61619399-4e50-c91f-8b88-1f76094959e7@arm.com> <VI1PR0801MB2127FA526D78386EF09DE17283130@VI1PR0801MB2127.eurprd08.prod.outlook.com>
On 10/06/2019 18:57, Wilco Dijkstra wrote:
> Hi Szabolcs,
>
>> i reviewed the patch.
>
> Thanks! Here is the updated version, with comments improved. I'll
> make the corresponding changes to memmem too.
>
> Wilco
>
> v3: Remove some unused defines. Increase filter size to 8 bytes.
> v4: Improve comments after review.
>
> 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).
>
> OK for commit?
>
> ChangeLog:
> 2019-06-10 Wilco Dijkstra <wdijkstr@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.
>
Reviewed-by: Szabolcs Nagy <szabolcs.nagy@arm.com>
(i think you should wait a day in case there are
further comments on this latest version, otherwise
it's ready to commit.)