Re: Fastest String Search Algorithm.

[Amit Choudhary <amitchoudhary0523@gmail.com>]

On Wed, Jun 9, 2021 at 4:02 PM Wilco Dijkstra <Wilco.Dijkstra@arm.com>
wrote:

> Hi Amit,
>
> > If my algorithm is beating strstr() for long search patterns then I think
> > that my algorithm should be included in glibc for long search patterns.
>
> I tried it in bench-strstr.c, strstr is often 10 times faster on many
> inputs.
> I only noticed a case with a 32KB needle and 64KB text where it beats
> strstr by
> a factor 3. On complex needles it behaves like basic_strstr (ie. quadratic
> time)


I included my algorithm in bench-strstr.c and ran the tests myself. I could
not find strstr-inputs file so I printed the haystack and needle.

I found out many things which I think are not correct:

1. In pass cases (positive cases where needle is part of haystack), the
needle is either located at the beginning of the haystack or at the end of
the haystack. To mimic real world scenario, the needle should be at the
middle of the haystack.

2. The large text is mostly repetition of two small paragraphs. This again
is not a real world scenario.

3. Some tests for 256 byte needles have haystack and needle as a
combination of characters 'a' and 'b'. No real world text has been used.

4. Tests for 1 KB / 4 KB / 8 KB / 28 KB needles also have  haystack and
needle as a combination of characters 'a' and 'b'. No real world text has
been used.

So, in my opinion strstr() has never been tested extensively for real world
text. I think this is a very big shortcoming.

Regards,
Amit