3 ms·

How does ripgrep compare to Hyperscan? I always wanted to wrap that library in a grep utility and never got around to it

killercup 5y ago
Ripgrep includes one of the most prominent algorithms from Hyperscan internally for some expressions. Longer story: Ripgrep uses Rust's regex library, which uses the Aho-Corasick library. That does not just provide the algorithm it is named after, but also "packed" ones using SIMD, including a Rust rewrite of the [Teddy algorithm][1] from the Hyperscan project. [1]: https://github.com/BurntSushi/aho-corasick/tree/4499d7fdb41c6279ea1367bccf3daca9cb06c36c/src/packed/teddy https://github.com/BurntSushi/aho-corasick/tree/4499d7fdb41c...
- boredprograming 5y ago
  That's awesome!
- kevincox 5y ago
  This post by the author is a great introduction to the techniques used in ripgrep https://blog.burntsushi.net/ripgrep/ https://blog.burntsushi.net/ripgrep/
burntsushi 5y ago
ripgrep's internals are generic over the regex engine, so not only is it possible to plug Hyperscan into ripgrep, but someone has already done it: https://sr.ht/~pierrenn/ripgrep/ https://sr.ht/~pierrenn/ripgrep/ (I should really add a link to that in the README.)
glangdale 5y ago
Ripgrep uses one of Hyperscan's string search algorithms. In general, Hyperscan isn't wonderfully suited for a "grep use case", as it's not focused on quick compile times. It was built for cases where the regex sets (and it's usually sets, sometimes large sets) are known in advance and where it's worth doing "heroics" to optimize scanning of these sets on a precompiled bytecode. It's not a direct comparison with Rust's regex crate or with ripgrep, but this article shows the comparison with re2. Notice that on average it takes 140K worth of scanning to "catch up" with RE2::Set with 10 patterns - the situation would be even more marked with 1 pattern. https://www.hyperscan.io/2017/06/20/regex-set-scanning-hyperscan-re2set/ https://www.hyperscan.io/2017/06/20/regex-set-scanning-hyper... Personally, I'm dissatisfied with the approach to regex scanning in Hyperscan (too heavyweight at construction and too complex) but not much more pleased by the Rust regex crate or RE2 (frankly, the whole compile-a-giant-DFA-as-you-go isn't that great either). I feel on the verge of taking another crack at the problem. Lord knows the world needs another regex library...
- burntsushi 5y ago
  I personally still really like the lazy DFA approach. Especially for the single-pattern use case. In particular, it handles the case of large Unicode character classes quite well by avoiding the construction of huge DFAs unless the input actually calls for it. With that said, I have longed for simple ways of composing regexes better. I've definitely fallen short of that, and I think it's causing me to miss a whole host of optimizations. I hope to devote some head space to that in the next year or so.
  - glangdale 5y ago
    I'm OK with laziness, but lazy != "lazy DFA". I can't help but think people keep building RE2-style DFA constructions because they don't know how to run NFAs efficiently. The idea that your automata has to keep allocating memory is pretty weird, especially in MT land. What I'm thinking about lately is sticking a lot closer to the original regular expression parse tree when implementing things. Yes, that leaves performance on the table relative to Hyperscan, but I suspect the compile time could be extremely good. Also, it would be better suited to stuff like capturing and back-references. Like I said, I suspect I'll be building "Ultimate Engine the Third" sometime in the not-too-distant future (Hyperscan's internal name was "Ultimate Engine the Second", an Iain M. Banks reference).
    - burntsushi 5y ago
      Yeah, we've had this conversation before. :-) I look forward to seeing what you come up with!

killercup 5y ago

Ripgrep includes one of the most prominent algorithms from Hyperscan internally for some expressions. Longer story: Ripgrep uses Rust's regex library, which uses the Aho-Corasick library. That does not just provide the algorithm it is named after, but also "packed" ones using SIMD, including a Rust rewrite of the [Teddy algorithm][1] from the Hyperscan project. [1]: https://github.com/BurntSushi/aho-corasick/tree/4499d7fdb41c6279ea1367bccf3daca9cb06c36c/src/packed/teddy https://github.com/BurntSushi/aho-corasick/tree/4499d7fdb41c...

boredprograming 5y ago
That's awesome!
kevincox 5y ago
This post by the author is a great introduction to the techniques used in ripgrep https://blog.burntsushi.net/ripgrep/ https://blog.burntsushi.net/ripgrep/

burntsushi 5y ago

ripgrep's internals are generic over the regex engine, so not only is it possible to plug Hyperscan into ripgrep, but someone has already done it: https://sr.ht/~pierrenn/ripgrep/ https://sr.ht/~pierrenn/ripgrep/ (I should really add a link to that in the README.)

glangdale 5y ago

Ripgrep uses one of Hyperscan's string search algorithms. In general, Hyperscan isn't wonderfully suited for a "grep use case", as it's not focused on quick compile times. It was built for cases where the regex sets (and it's usually sets, sometimes large sets) are known in advance and where it's worth doing "heroics" to optimize scanning of these sets on a precompiled bytecode. It's not a direct comparison with Rust's regex crate or with ripgrep, but this article shows the comparison with re2. Notice that on average it takes 140K worth of scanning to "catch up" with RE2::Set with 10 patterns - the situation would be even more marked with 1 pattern. https://www.hyperscan.io/2017/06/20/regex-set-scanning-hyperscan-re2set/ https://www.hyperscan.io/2017/06/20/regex-set-scanning-hyper... Personally, I'm dissatisfied with the approach to regex scanning in Hyperscan (too heavyweight at construction and too complex) but not much more pleased by the Rust regex crate or RE2 (frankly, the whole compile-a-giant-DFA-as-you-go isn't that great either). I feel on the verge of taking another crack at the problem. Lord knows the world needs another regex library...

burntsushi 5y ago
I personally still really like the lazy DFA approach. Especially for the single-pattern use case. In particular, it handles the case of large Unicode character classes quite well by avoiding the construction of huge DFAs unless the input actually calls for it. With that said, I have longed for simple ways of composing regexes better. I've definitely fallen short of that, and I think it's causing me to miss a whole host of optimizations. I hope to devote some head space to that in the next year or so.
- glangdale 5y ago
  I'm OK with laziness, but lazy != "lazy DFA". I can't help but think people keep building RE2-style DFA constructions because they don't know how to run NFAs efficiently. The idea that your automata has to keep allocating memory is pretty weird, especially in MT land. What I'm thinking about lately is sticking a lot closer to the original regular expression parse tree when implementing things. Yes, that leaves performance on the table relative to Hyperscan, but I suspect the compile time could be extremely good. Also, it would be better suited to stuff like capturing and back-references. Like I said, I suspect I'll be building "Ultimate Engine the Third" sometime in the not-too-distant future (Hyperscan's internal name was "Ultimate Engine the Second", an Iain M. Banks reference).
  - burntsushi 5y ago
    Yeah, we've had this conversation before. :-) I look forward to seeing what you come up with!