3 ms·
A benchmark of all good string-search algos is here: https://rurban.github.io/smart/results/best20/ https://rurban.github.io/smart/results/best20/ The ones par
by rurban 2y ago
A benchmark of all good string-search algos is here:
https://rurban.github.io/smart/results/best20/ https://rurban.github.io/smart/results/best20/
The ones parent picked are not amongst the best at all.
I added a ticket to add your HashChain algos to be tested also.
Preliminary testing shows indeed excellent numbers for hc2-hc4. Comes close to musl
- MattPalmer1086 2y agoAmazing, thanks. The sample code is already written to integrate with smart (I have also contributed to the smart tool!). You may want to add the linear version of HashChain too (in the same GitHub repo).
- MattPalmer1086 2y agoLooks like musl is using pointer arithmetic? Can speed up most of the algorithms in smart by using that. It's faster than using array indexing generally. I didn't do that in the sample code for HashChain simply because it would be an unfair comparison with the others.
- MattPalmer1086 2y agoThe musl timings are actually incorrect, because it resets the timer on each iteration of the main loop used to count matches. So you only record the time to make the last match, not the total time. I've raised an issue on the GitHub for smart.
- rurban 2y agoOh, oh, thanks!
- MattPalmer1086 2y agoI was surprised that an algorithm from 1991 was the fastest! My first rule of benchmarking is to be suspicious of surprises!
- rurban 2y agoYes, I updated the benchmarks of the best string search algos.