This is the mail archive of the
mailing list for the glibc project.
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
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 <email@example.com> 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.
> 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.
Suspicious pointer corrupted virtual machine