This is the mail archive of the
mailing list for the glibc project.
Re: [PATCH v2] Improve performance of strstr
> 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.