[PATCH] Optimize strstr, strcasestr and memmem

[Ondřej Bílka]

I included also maxim patch to my benchmarks. 

I also implemented a two-way algorithm using ssse3. It almost always beats Maxims
implementation by factor 3, on and on i7 glibc one by factor 2.

Performance per character is here.
http://kam.mff.cuni.cz/~ondra/benchmark_string/i7/strstr/html/strstr_r.html

Small haystacks can be tuned more, for example we could still defer
critical factorization to later phase.

On Mon, May 21, 2012 at 03:16:21PM -0400, Carlos O'Donell wrote:
> On Mon, May 21, 2012 at 2:33 PM, Maxim Kuvyrkov <maxim@codesourcery.com> wrote:
> >> The biggest problem I have with reviewing *any* of this code is that
> >> performance is relative to benchmarks.
> >
> > While the other portion of this thread is being hijacked by discussion of GLIBC benchmarking, let's return to the patch that started this thread.
> 
> It was hijacking with a purpose.
> 
> > This patch is an algorithmic improvement, which makes strstr and company do less work by piggy backing the task of detecting EOL with the matching procedure. Â As is, EOL is detected by a dedicated call to memchr, which is extremely expensive.
> >
> > The only non-algorithmic improvement in the patch is the conversion of array[index] addressing to pointers. Â Replacing two variables and, potentially, an add instruction ("array", "index" and "array+index") with one variable ("pointer_array") is a fairly uncontroversial micro-optimization.
> >
> > Any reason for the review to not proceed?
> 
> No reason.
> 
> Cheers,
> Carlos.

-- 

Traffic jam on the Information Superhighway.