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 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.

Wilco
    

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