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] Optimize strstr, strcasestr and memmem

I expanded benchmark to cover more cases. I added graph creation. For
now I host it on my page

It additionaly tests a planted strings -it gets in file distribution of
prefixes so with distribution
50 0
40 1
10 8
will character be with probabilities 50% not in needle, 40% first in
needle, 10% member of sequence consisting of first 8 characters of

This distribution is one of extremes for my alg;orithm as 16-byte is 
matched with probability 40% due of last byte.

On Sun, May 20, 2012 at 09:57:13AM -0400, Carlos O'Donell wrote:
> On Sat, May 19, 2012 at 9:32 PM, OndÅej BÃlka <> wrote:
> >> > As a community we have no baseline benchmark numbers.
> >>
> >> Precisely - the very reason that I have not tried to further optimize
> >> anything in glibc beyond my twoway string, and the reason the SSE4
> >> quadratic pessimization even got in to glibc in the first place, is
> >> because we don't have a good benchmark.
> >
> > I wrote benchmark that measures mean instructions per character+-standard deviation for
> > random strings and matching aaaaaa with aaaab. I included strlen as lower bound on
> > speed.
> >
> > Instead two-way I try universal hashing. For needle<16 bruteforce is
> > sufficient, for larger I could improve it by computing hash qwordwise.
> Ondrej,
> Thank you for posting your benchmark.
> It is one piece of the larger requirements for glibc.
> Would you be willing to work with the community to integrate such a
> test into glibc?
> Would you be able to help maintain the micro-benchmarks?

Yes, I am willing.
> Cheers,
> Carlos.


Suspicious pointer corrupted virtual machine

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