Fastest String Search Algorithm.

Wilco Dijkstra Wilco.Dijkstra@arm.com
Mon Jun 7 16:04:42 GMT 2021


Hi Amit,

>> Anyway, the generic strstr in a recent GLIBC is over 1000 times faster on this test.
>
> So, does this mean that gcc may not be having latest GLIBC.

GLIBC is part of your system, not GCC. Use ldd --version to get the GLIBC version
your system has. If it is old you could upgrade or build a newer GLIBC yourself.

> Can you please let me know what are modern string algorithms and where can
> I find them so that I can compare my algorithm with them.

The generic GLIBC strstr implementation I pointed you at is the one you need to beat
to prove your algorithm is better. It's the fastest known generic strstr implementation
and beats every algorithm in SMART on most inputs.

If you build your own GLIBC, you can run the strstr benchmark (glibc/benchtests/bench-
strstr.c). You can even add your algorithm in the comparison (search for "basic_strstr" -
you'll find it's easy to add).

Cheers,
Wilco


More information about the Libc-alpha mailing list