9 ms·

Interesting algorithm. I can see how this could be advantageous for moderate length patterns up to 64 bytes. But for short registered sized patterns (4 or 8 b

Interesting algorithm. I can see how this could be advantageous for moderate length patterns up to 64 bytes. But for short registered sized patterns (4 or 8 bytes), I am somewhat skeptical of any significant advantage over a very tight, brute force register based loop comparing multi-byte chunks.

jo3_l 5d ago
(OP here.) You're correct that for short patterns there's little advantage over the brute-force algorithm, and in fact the brute-force algorithm should actually be faster in many cases. Indeed the per-iteration comparison against the pattern in the brute-force algorithm is essentially a memcmp, which is vectorized and runs very fast on modern hardware. Consequently all mainstream programming languages that I know of just use the brute-force algorithm as a fallback when the pattern is short, as opposed to something more complicated like bitap. I tried to be fairly careful to not overstate the performance benefits in the original post for this reason.
- jqpabc123 5d ago
  Ok, so why not use a fast memcmp on the first 4-8 chars of the pattern to identify any potential match and once found, work from there to verify if a full match exists? This is essentially what I have have been doing for years and it is very simple. I'm sure it is not always the fastest but it's not too shabby either in the real world.
  - MattPalmer1086 5d ago
    Probably very effective for shorter patterns. Two reasons to use more complex algorithms for longer patterns: 1. Linearity - the naive approach is quadratic on worst case data (imagine searching for 100 0's in a text of 0's). 2. Sublinearity - sublinear search algorithms skip over text that cannot match. They typically have the somewhat counter-intuitive property that they get much faster the longer the pattern is. So long patterns will be faster using a sub linear search algorithm.
    - jqpabc123 4d ago
      Yes but longer patterns are kind of an outlier. Most of the everyday searching and parsing that I end up doing involves relatively short patterns. Maybe I am an outlier :-)

jo3_l 5d ago

(OP here.) You're correct that for short patterns there's little advantage over the brute-force algorithm, and in fact the brute-force algorithm should actually be faster in many cases. Indeed the per-iteration comparison against the pattern in the brute-force algorithm is essentially a memcmp, which is vectorized and runs very fast on modern hardware. Consequently all mainstream programming languages that I know of just use the brute-force algorithm as a fallback when the pattern is short, as opposed to something more complicated like bitap. I tried to be fairly careful to not overstate the performance benefits in the original post for this reason.

jqpabc123 5d ago
Ok, so why not use a fast memcmp on the first 4-8 chars of the pattern to identify any potential match and once found, work from there to verify if a full match exists? This is essentially what I have have been doing for years and it is very simple. I'm sure it is not always the fastest but it's not too shabby either in the real world.
- MattPalmer1086 5d ago
  Probably very effective for shorter patterns. Two reasons to use more complex algorithms for longer patterns: 1. Linearity - the naive approach is quadratic on worst case data (imagine searching for 100 0's in a text of 0's). 2. Sublinearity - sublinear search algorithms skip over text that cannot match. They typically have the somewhat counter-intuitive property that they get much faster the longer the pattern is. So long patterns will be faster using a sub linear search algorithm.
  - jqpabc123 4d ago
    Yes but longer patterns are kind of an outlier. Most of the everyday searching and parsing that I end up doing involves relatively short patterns. Maybe I am an outlier :-)