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


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.

Wilco


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