This is the mail archive of the mailing list for the glibc project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Use Quicksearch in strstr

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...


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]