[PATCH v2] Improve performance of strstr

[Wilco Dijkstra]

Hi Rich,

> On Fri, Apr 12, 2019 at 04:49:11PM +0000, Wilco Dijkstra wrote:
>> Hi Szabolcs,
>> 
>> > please cc those who previously had objections against
>> > the patch and ask if they sustain their objections
>> > and if so what changes or demonstrations are needed
>> > to move this forward.
>> 
>> I haven't seen any constructive objections nor received any reply
>> when I asked for actual evidence of a claimed regression [1].
>
> I have already explained to you the cases which are going to perform
> pathologically bad with your vaguely optimized version of the naive
> O(nm) strstr. I don't have your specific hardware to run benchmarks,
> but the order of magnitude here is so large that a big-O argument
> suffices. If the proposed size limit were something like 24 or 32
> rather than 256 that might not necessarily be the case.

The O notation means O (256 N) is equivalent to O (N), ie. linear
performance in the worst case. And that is what matters for large inputs.

The average runtime of my algorithm is actually sublinear. So in that
sense Two-Way performs pathologically bad.

> I vaguely recall doing some testing on a glibc x86_64 box that showed
> the magnitude of the problem; I can try to dig that up or do it again
> if you really want to see it.

Yes, without a reproducible example I can't see what your issue is. You
can't make it go quadratic because it simply isn't.

Wilco