4 ms·

It does not. ripgrep does not use Boyer-Moore in most searches. In particular, the advice in the OP is generally out of date. The "secret" sauce to ripgrep's s

It does not. ripgrep does not use Boyer-Moore in most searches. In particular, the advice in the OP is generally out of date. The "secret" sauce to ripgrep's speed in simple literal searches is a simple heuristic: choose the rarest byte in the needle and feed that to memchr. (The "heuristic" is that you can't actually know the optimal choice, but it turns out that a guess works pretty well most of time since most things you search have a similar frequency distribution.) The SSSE3 optimizations come from Hyperscan, and are only applicable when searching a small number of small patterns. e.g., `Holmes|Watson|Moriarty|Adler`. In other words, for common searches (which are short strings), it is much better to spend more time in a vectorized routine than to try to skip bytes.

blattimwind 8y ago
> In other words, for common searches (which are short strings), it is much better to spend more time in a vectorized routine than to try to skip bytes. Complexity analysis of substring search focuses on the number of comparisons – at least those I saw –, much like sorting, and of course that's not an accurate model at all.
taeric 8y ago
This makes sense. Surprises me, but makes sense. I typically search for the largest string I can nowadays. Though, I suspect even those are not large enough to tip the needle, since I'm usually just talking about a uuid.
ComplexSystems 8y ago
Interesting. Could this perform even faster if you (for large files) took a random sample of bytes before doing the search, to get the best distribution? Or just update the distribution as the search progresses.
- burntsushi 8y ago
  It's probably more terrible than its worth, and you'd need to figure out how to take the sample in a way that doesn't kill performance. It would be an interesting experiment, but the usual heuristic is just to give up on fast skipping if it's ineffective.
adrianratnapala 8y ago
>... but it turns out that a guess works pretty well most of time since most things you search have a similar frequency distribution.) This kind of thing is an pattern unless the benefit over Boyer-Moore huge. A small performance gain in the common-case is not worth the pain of introducing pathological cases that only bite you once you are deeply committed. Presumably this is not too bad for ripgrep itself, as long as it falls back to something sensible when the assumption fails.
- TheCoelacanth 8y ago
  What pathological case are you referring to? The worst case I can think of is a completely random haystack in which case it is approximately equivalent to a naive search. Even Boyer-Moore is not superior to a naive search in literally every case, e.g. short needle or large alphabet.
- burntsushi 8y ago
  This is wrong. Boyer-Moore does the same thing. It just always selects the last byte to feed into memchr. If that byte happens to be rare, then it works great. But if it happens to be common, then it gets into the weeds pretty quickly. My suggested heuristic does the same thing, but increases the chances that it selects a rare byte. And yes, the performance difference can be very large. Here's an example on a ~9.3GB file: $ time rg --no-mmap 'Sherlock ' OpenSubtitles2016.raw.en | wc -l 6698 real 3.006 user 1.658 sys 1.345 maxmem 8 MB faults 0 $ time grep 'Sherlock ' OpenSubtitles2016.raw.en | wc -l 6698 real 9.023 user 7.921 sys 1.092 maxmem 8 MB faults 0 Notice that the pattern is `Sherlock `. The last byte is an ASCII space character, which is incredibly common. Boyer-Moore blindly picks this as the skip byte, but ripgrep uses a simple pre-computed frequency table to select a better byte as the skip byte. > Presumably this is not too bad for ripgrep itself, as long as it falls back to something sensible when the assumption fails. It does. That's why I said, "ripgrep does not use Boyer-Moore in most searches."

blattimwind 8y ago

> In other words, for common searches (which are short strings), it is much better to spend more time in a vectorized routine than to try to skip bytes. Complexity analysis of substring search focuses on the number of comparisons – at least those I saw –, much like sorting, and of course that's not an accurate model at all.

taeric 8y ago

This makes sense. Surprises me, but makes sense. I typically search for the largest string I can nowadays. Though, I suspect even those are not large enough to tip the needle, since I'm usually just talking about a uuid.

ComplexSystems 8y ago

Interesting. Could this perform even faster if you (for large files) took a random sample of bytes before doing the search, to get the best distribution? Or just update the distribution as the search progresses.

burntsushi 8y ago
It's probably more terrible than its worth, and you'd need to figure out how to take the sample in a way that doesn't kill performance. It would be an interesting experiment, but the usual heuristic is just to give up on fast skipping if it's ineffective.

adrianratnapala 8y ago

>... but it turns out that a guess works pretty well most of time since most things you search have a similar frequency distribution.) This kind of thing is an pattern unless the benefit over Boyer-Moore huge. A small performance gain in the common-case is not worth the pain of introducing pathological cases that only bite you once you are deeply committed. Presumably this is not too bad for ripgrep itself, as long as it falls back to something sensible when the assumption fails.

TheCoelacanth 8y ago
What pathological case are you referring to? The worst case I can think of is a completely random haystack in which case it is approximately equivalent to a naive search. Even Boyer-Moore is not superior to a naive search in literally every case, e.g. short needle or large alphabet.
burntsushi 8y ago
This is wrong. Boyer-Moore does the same thing. It just always selects the last byte to feed into memchr. If that byte happens to be rare, then it works great. But if it happens to be common, then it gets into the weeds pretty quickly. My suggested heuristic does the same thing, but increases the chances that it selects a rare byte. And yes, the performance difference can be very large. Here's an example on a ~9.3GB file: $ time rg --no-mmap 'Sherlock ' OpenSubtitles2016.raw.en | wc -l 6698 real 3.006 user 1.658 sys 1.345 maxmem 8 MB faults 0 $ time grep 'Sherlock ' OpenSubtitles2016.raw.en | wc -l 6698 real 9.023 user 7.921 sys 1.092 maxmem 8 MB faults 0 Notice that the pattern is `Sherlock `. The last byte is an ASCII space character, which is incredibly common. Boyer-Moore blindly picks this as the skip byte, but ripgrep uses a simple pre-computed frequency table to select a better byte as the skip byte. > Presumably this is not too bad for ripgrep itself, as long as it falls back to something sensible when the assumption fails. It does. That's why I said, "ripgrep does not use Boyer-Moore in most searches."