This is the mail archive of the
mailing list for the glibc project.
Re: [PATCH v2] Improve performance of strstr
On Tue, Apr 16, 2019 at 11:49:43PM +0000, Wilco Dijkstra wrote:
> Hi Rich,
> > 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.
> No that was incorrectly comparing a fast case with a slow case. You can
> easily show 1000x difference between fast and slow cases, but what we're
> interested in is how the slow cases compare.
No, the 40x was comparing the same input -- that is, there's an input
for which your patch makes it 40x slower.
You can find some inputs which are mildly slow for the current two-way
implementation (likely due to a mix of fundamental reasons and
implementation flaws), and normalized for size (a poor normalization
but whatever), searching for them takes significantly more than 1/40
the time that your code takes on its worst-case. This is really not a
meaningful comparison. What's meaningful is that some operations
become 40x slower for no good reason except your irrational refusal to
improve the implementation of the good algorithm rather than reverting
to something backwards.