This is the mail archive of the libc-alpha@sourceware.org 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 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


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