Fastest String Search Algorithm.

[Siddhesh Poyarekar]

On 6/9/21 11:48 AM, Amit Choudhary via Libc-alpha wrote:
> Have you tried with long texts (60 KB or more) and long search patterns (28
> KB or more). My algorithm is faster than others for long search patterns.
> 
> strstr() is faster with 60 KB of text and 3.2 KB of search pattern.
> 
> But my algorithm is faster with 60 KB of text and 4.4 KB / 28 KB of search
> pattern.
> 
> Please test with long texts and long search patterns.

Maybe we need to first start with you contributing the tests you're 
using the evaluate the algorithm to benchtests.  Please see 
benchtests/README and go through the existing tests to understand how 
they work.  That should give a more structured way to discuss the new 
strstr algorithm.

Once the change is in, I'd recommend adding your strstr implementation 
as an ifunc (see sysdeps/x86_64/strstr.c and sysdeps/x86_64/strstr_* as 
examples) and use `make bench` to get a more comprehensive view of the 
performance characteristics of your function vs all other 
implementations for that architecture; there are more than one.  It is a 
lot easier to have a conversation about performance characteristics of 
the algorithm with that.

> I hope that people are not of the view that Indians can't invent or
> innovate.

No.  Please stick to technical discussions.  We are a pretty diverse set 
of contributors in the glibc project and over the course of your 
discussions (that have barely lasted 3 days; it has taken many people 
weeks or even months to get major changes included into glibc because of 
the very wide impact of such changes) you have received comments from 
people in at least 4 different countries, including India.

Siddhesh