This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] Use Quicksearch in strstr
Hi,
Rich Felker wrote:
> 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.
This won't help at all. The character matching loops don't show up in profiles.
Almost all time is spent in finding the first character, ie. strchr (short needles)
and the Horsepool loop (long needles). Using Quicksearch to find a prefix of
the suffix string should be faster.
Wilco