3 ms·

I few years ago, I wrote another substring search algorithm that is outperforming this one on a modern computer: https://github.com/RaphaelJ/fast_strstr/tree/ma

I few years ago, I wrote another substring search algorithm that is outperforming this one on a modern computer: https://github.com/RaphaelJ/fast_strstr/tree/master/benchmark/algorithms https://github.com/RaphaelJ/fast_strstr/tree/master/benchmar... While the algorithm is time linear (Boyer-Moore is sub linear), it ends up being significantly faster on textual content as the per character operations are significantly simplier.

vanderZwan 5y ago
Speaking of modern computers, have you compared it to these SIMD string find algorithms by Wojciech Muła? They're a bit more recent: http://0x80.pl/articles/simd-strfind.html http://0x80.pl/articles/simd-strfind.html
lofi_lory 5y ago
BM taught me that cleverness doesn't pay for fast, similar iterations. Performance is all about cache misses. I hated that lesson.
- lofi_lory 5y ago
  Also that thinking about string matching problems isn't good for my mental health. I had horrible nightmares on the road to my O(m) good suffix rule. Very hard not to go a little mad over iterating countless ideas and string matching scenarios in your head... on the train, on the pot, laying in bed trying to sleep. Btw. digital tablet with pen input is gold thinking about algorithms, as you get modifying your scenarios in place endlessly and copy and paste over paper + pencil.
- linsomniac 5y ago
  Same. I implemented it, IIRC, on my Amiga 2000 and compared it to the Manx C library builtin. Which wiped the floor with my BM implementation. I don't remember the exact numbers, but it was so much faster that I didn't even bother trying to optimize mine, I just threw up my hands. It may have been on an HP9000s2xx machine instead of Amiga. Taught me that hand optimized assembly can beat clever algorithms.
lifthrasiir 5y ago
I should note that this algorithm is not for untrusted inputs because one can relatively easily fabricate inputs that trigger the worst case (this is even possible when the attacker can control only the haystack or only the needle). The two-way algorithm, used by glibc and many others, is linear at the worst and cache-friendly enough. Maybe Rabin-Karp is fast enough for short needles even at the worst case; a hybrid algorithm might be interesting (like, two-way algorithm has two variants for long needles and short needles; RK can replace the latter).

vanderZwan 5y ago

Speaking of modern computers, have you compared it to these SIMD string find algorithms by Wojciech Muła? They're a bit more recent: http://0x80.pl/articles/simd-strfind.html http://0x80.pl/articles/simd-strfind.html

lofi_lory 5y ago

BM taught me that cleverness doesn't pay for fast, similar iterations. Performance is all about cache misses. I hated that lesson.

lofi_lory 5y ago
Also that thinking about string matching problems isn't good for my mental health. I had horrible nightmares on the road to my O(m) good suffix rule. Very hard not to go a little mad over iterating countless ideas and string matching scenarios in your head... on the train, on the pot, laying in bed trying to sleep. Btw. digital tablet with pen input is gold thinking about algorithms, as you get modifying your scenarios in place endlessly and copy and paste over paper + pencil.
linsomniac 5y ago
Same. I implemented it, IIRC, on my Amiga 2000 and compared it to the Manx C library builtin. Which wiped the floor with my BM implementation. I don't remember the exact numbers, but it was so much faster that I didn't even bother trying to optimize mine, I just threw up my hands. It may have been on an HP9000s2xx machine instead of Amiga. Taught me that hand optimized assembly can beat clever algorithms.

lifthrasiir 5y ago

I should note that this algorithm is not for untrusted inputs because one can relatively easily fabricate inputs that trigger the worst case (this is even possible when the attacker can control only the haystack or only the needle). The two-way algorithm, used by glibc and many others, is linear at the worst and cache-friendly enough. Maybe Rabin-Karp is fast enough for short needles even at the worst case; a hybrid algorithm might be interesting (like, two-way algorithm has two variants for long needles and short needles; RK can replace the latter).