6 ms·

I've actually found Boost's Boyer-Moore-Horspool to be faster than its Boyer-Moore.

• bjoli 6y ago
  For long needles it is, I agree. I am just too lazy to have a good heuristics between a naive search (which is surprisingly fast on modern hardware) and the horspool. With whatever implementations I have implemented have a sweet spot between naive and horspool wher BM is actually sliiightly faster. I think it is just that Horspool works better on modern hardware. BM isn't nearly as much of a gain over the naive search that it was 25 years ago. Edit: the max shift change I mentioned above can be done to Horspool as well!
  • dataflow 6y ago
    Oh I actually meant for (super) shorter needles. I'm not sure if this is a general statement or if it's just applicable to the Boost implementation though. And yeah I should really try out the max shift change, I came across it not too long ago but never got around to implementing it.
    • MattPalmer1086 6y ago
      I find Horspool is almost always faster than Boyer Moore. For very short needles though (e.g. less than 8) it is hard to beat the SHIFT OR algorithm. Even though it is not sublinear, looking at every position, it tracks matches using a bitmask. In practice this is very fast and has very good cache hits. It easily beats BM or Horspool by quite a margin. They rely for speed in skips, and you don't get great skips with a short needle.