This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH v2] Improve performance of strstr
On Tue, Apr 16, 2019 at 10:52:28PM +0000, Wilco Dijkstra wrote:
> Hi Szabolcs,
>
> > this is a good case for twoway, so we need a twoway worst case too
> > for a real comparision: comparing the worst for new vs worst for
> > twoway i've seen so far, new is
>
> Yes absolutely, it's easy to get 1000 times difference between fast and
> slow cases, but that's not interesting at all. The goal is to make the average
> case fast - even if it makes uncommon cases slower.
>
> > 4.5x slower on Cortex-A72
> > 2.7x slower on Cortex-A57
>
> That shows how much it varies even on 2 similar micro architectures.
> Note these results are using the optimized Two-Way implementation - the
> original implementation was more than twice as slow before I optimized it.
> So it's possible the worst cases are faster now than in GLIBC 2.26.
>
> > but there is no guarantee that my inputs are near the real worst
> > cases, it's hard to tell (and clearly uarch matters too).
>
> We could generate lots of cases to try finding a minimum, but the search space is
> impossibly large. And the worst cases depend a lot on microarchitecture so they
> will be different on different CPUs.
>
> Ultimately the 3 key questions are:
>
> 1. Is it linear time even on huge inputs?
> 2. Is it faster than Two-way in the average case?
> 3. Is it within a small factor even in the worst case?
>
> The first 2 were never in doubt, and your result proves 3 as well.
His result was up to 40x slower, which refutes #3.
Rich