2 ms·
They make look like nothing happened in optimal strstr algorithms in the last decades. In the libc's not, indeed. They are still in the stoneage of string searc
by rurban 6y ago
They make look like nothing happened in optimal strstr algorithms in the last decades.
In the libc's not, indeed. They are still in the stoneage of string search.
But the fastest is currently EPSM, by S. Faro and O. M. Kulekci. See https://smart-tool.github.io/smart/ https://smart-tool.github.io/smart/
"Exact Packed String Matching" optimized for SIMD SSE4.2/AVX (x86_64 and aarch64). It performs stable and best on all sizes.
The site I linked to compares 199 fast string search algorithms, with the usual ones (BM, KMP, BMH) being pretty slow. EPSM outperforms all the others being mentioned here on these platforms. It's also the latest.
- MattPalmer1086 6y agoIt is a great site, I've discovered many interesting algorithms on it. And benchmarked them with their tool, along with some of my own. And yes, EPSM outperforms the others by a mile. If you are comfortable with your search performance being bound to particular CPU architectures, and that may be entirely reasonable, then you can't beat that approach.