Hacker News Reader

Comment by raphaelj | Hacker News Reader

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/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.

View on HN

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

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.

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.

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).

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

Reply on news.ycombinator.com