This is the mail archive of the libc-alpha@sourceware.org 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] Optimize strstr, strcasestr and memmem


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.


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