This is the mail archive of the
mailing list for the glibc project.
Re: [PATCH] Use Quicksearch in strstr
On Wed, Nov 07, 2018 at 02:28:45PM -0500, Rich Felker wrote:
> > >> Getting another 2-3x speedup after doubling performance is a huge factor..
> > >> The previous implementation was doing effectively nothing useful 75-85%
> > >> of the time...
> > >
> > > Then fix implementation bugs. Don't replace good algorithms with awful
> > > ones. For any given needle, it's definitely possible to make it such
> > > that,...
> > I already did that, remember? If you believe you can do better then post further
> > performance improvements.
> Nobody has replied to my branch of this thread about limiting shift in
> the case of memory. I'm pretty confident it's right now so maybe I
> should just submit a patch. But it's frustrating that there is more
> interest in discussing bad algorithms than in improving the
> implementation of a good one.
On further reading, it looks like the whole "performance problem" is
probably lack of a machine-optimized comparison loop for the two
(forward and backwards) comparisons in two-way. If we had "rep cmp"
functions for each direction (optimized to use specialized insns or
vector ops, possibly misaligned if allowed by the ISA, taking into
account that we know the needle length and a lower bound on the
haystack length so that there's no overread issue) returning the first
mismatching offset, I see no reason why there should be any cases that
perform worse than "quicksearch", and pretty much all cases should
speed up a lot vs the status quo.
Ideally the "rep cmp" functions should be inline containing inline asm
fragments so they can be inlined right into the loop without any call
overhead, but this probably only matters for short needles.