This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] Use Quicksearch in strstr
- From: Wilco Dijkstra <Wilco dot Dijkstra at arm dot com>
- To: Rich Felker <dalias at libc dot org>
- Cc: 'GNU C Library' <libc-alpha at sourceware dot org>, nd <nd at arm dot com>, Alexander Monakov <amonakov at ispras dot ru>
- Date: Tue, 6 Nov 2018 13:34:33 +0000
- Subject: Re: [PATCH] Use Quicksearch in strstr
- References: <DB5PR08MB1030E559B3818F52CA48A63583F30@DB5PR08MB1030.eurprd08.prod.outlook.com>,<20181029225421.GA21482@domone>,<DB5PR08MB1030CE58A51EDD8FE90D80DD83CD0@DB5PR08MB1030.eurprd08.prod.outlook.com>,<DB5PR08MB1030428E777D456220B6F09383CB0@DB5PR08MB1030.eurprd08.prod.outlook.com>
Rich Felker wrote:
> I think there may actually be a bug (just suboptimality) in the
> two-way implementation related to this case. It's a periodic needle
> that uses 'memory', and glibc has (abbreviated):
>
> if (memory && shift < period)
> shift = needle_len - period;
> I'm pretty sure this is a logic bug. Except for bytes that don't
> appear in the needle (for which shift==needle_len), shift < period is
> automatically true. The needle being periodic means that each byte
> which appears in it appears within the last 'period' positions of it.
>
> I suspect what was actually intended was:
>
> if (memory && shift < needle_len - period)
> shift = needle_len - period;
>
> which can be simplified to:
>
> if (shift < memory)
> shift = memory;
Those are all equivalent indeed, the last version gives ~2.5% speedup.
Interestingly this path is still twice as slow as the short needle code - it
used to be 3.5-4 times as slow before I optimized the slow AVAILABLE
macro. It's a shame performance of strstr has been held back so long
both by a slow algorithm and a slow implementation...
Wilco