Hacker News Reader

Comment by boredprograming | Hacker News Reader

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

View on HN

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

That's awesome!

This post by the author is a great introduction to the techniques used in ripgrep https://blog.burntsushi.net/ripgrep/

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

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.

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

Yeah, we've had this conversation before. :-) I look forward to seeing what you come up with!

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/

(I should really add a link to that in the README.)

Reply on news.ycombinator.com