6 ms·

I occasionally find myself wanting to search a data stream using a large-ish set (a few tens or hundreds of thousands) of regexes. This is very slow with a back

I occasionally find myself wanting to search a data stream using a large-ish set (a few tens or hundreds of thousands) of regexes. This is very slow with a backtracking engine like PCRE, but ought to be pretty fast with a DFA-based engine like re2. So far, I have been unsuccessful in finding a grep replacement that can read patterns from a file, and which also uses a DFA engine. Does one exist? From the table, it looks like ripgrep might be suitable. Is it?

burntsushi 5y ago
Precisely speaking, no, I don't know of any grep tools that use a DFA engine. However, both ripgrep and GNU grep use a hybrid NFA/DFA engine (also known as a "lazy DFA") for some subset of regexes. I'm not too familiar with all of GNU grep's strategies, but for ripgrep, it will fall back to an NFA engine. (And I don't mean Friedl's bastardization of the term "NFA engine.") For ripgrep, see the --dfa-size-limit flag to try to let it use the hybrid NFA/DFA engine for bigger regexes. Whether it helps or not depends on your situation. Now, this will do much better than a backtracking engine, but if you get up into the tens of thousands or hundreds of thousands of regexes, it's going to get pretty painful. Finite automata just doesn't scale that well. At that point, you really start wanting a more specialized solution. Probably the best answer to that that I know of is Hyperscan. And you're in luck; someone maintains a fork of ripgrep with support for Hyperscan: https://sr.ht/~pierrenn/ripgrep/ https://sr.ht/~pierrenn/ripgrep/ (A special case is tens of thousands of literal patterns. ripgrep will notice that and should use Aho-Corasick. It doesn't help so much with search time since it's just a NFA or a DFA like with regexes, but the machine itself is constructed much more quickly.)
- gnfargbl 5y ago
  What an incredibly helpful reply. Thank you! It sounds like either plain ripgrep, or ripgrep+hyperscan, is pretty much exactly what I'm looking for. Next time I have this problem, I'll certainly be reaching for it.
- vlovich123 5y ago
  Out of curiosity, what prevents the hyperscan support from being mainlined?
  - burntsushi 5y ago
    Too much of a weighty dependency and too much of a niche IMO. For example, the last time I tried to build Hyperscan, I failed and gave up after 15 minutes of trying.
    - vlovich123 5y ago
      I would have thought you just need to include the rust-hyperscan crate[1] which would take care of that for you (but that crate probably didn't exist when you looked at it). I don't have a sense on the impact it has on overall binary size. [1] https://crates.io/crates/hyperscan https://crates.io/crates/hyperscan
      - burntsushi 5y ago
        I don't think the existence of a crate or not really impacts anything I said. More to the point, it would put a reliance on someone else to maintain a crate for critical functionality in ripgrep. (And if that fell through, I would invariably need to pick up that burden. Removing functionality is a lot harder than adding it.) It makes a lot more sense to me for something like Hyperscan to be maintained out of tree. I did work with the patch author a bit, and in particular, made some changes to ripgrep to make maintaining such a fork easier: https://github.com/BurntSushi/ripgrep/issues/1488 https://github.com/BurntSushi/ripgrep/issues/1488 Bottom line is, a lot of people think that adding a dependency has nearly zero cost. But it doesn't. Not by a long shot.
jemfinch 5y ago
I've written this code (in C++) for an employer. RE2 scaled fine to hundreds of thousands of regexes. You'll want to use RE2::Set, which compiles multiple regexes into a single DFA, and probably the "Filter" functionality (whose name I don't precisely remember and am too lazy to look up) which uses an Aho-Corasick tree to subset the potential matches. One thing you'll have to watch out for is RE2's maximum DFA size; if compilation of your RE2::Set fails, just split your set of regexes in half and compile again. You could probably do some fun optimizations by grouping the regexes which depend on the same literals into their own sets, but I never needed to.
- burntsushi 5y ago
  This is basically what ripgrep will do for you automatically. (ripgrep uses Rust's regex engine, which is a descendant of RE2.) But when you get up into hundreds of thousands of regexes, the NFA (and the resulting DFA) get really big. And things generally don't scale that well. Here's a good example: http://web.archive.org/web/20210302010420/https://01.org/hyperscan/blogs/jpviiret/2017/regex-set-scanning-hyperscan-and-re2set http://web.archive.org/web/20210302010420/https://01.org/hyp... The problem is that for a big enough NFA, you'll wind up spending most of your search doing powerset construction to build the DFA. > One thing you'll have to watch out for is RE2's maximum DFA size You can configure this in ripgrep with the --dfa-size-limit flag. (See also --regex-size-limit.)

burntsushi 5y ago

Precisely speaking, no, I don't know of any grep tools that use a DFA engine. However, both ripgrep and GNU grep use a hybrid NFA/DFA engine (also known as a "lazy DFA") for some subset of regexes. I'm not too familiar with all of GNU grep's strategies, but for ripgrep, it will fall back to an NFA engine. (And I don't mean Friedl's bastardization of the term "NFA engine.") For ripgrep, see the --dfa-size-limit flag to try to let it use the hybrid NFA/DFA engine for bigger regexes. Whether it helps or not depends on your situation. Now, this will do much better than a backtracking engine, but if you get up into the tens of thousands or hundreds of thousands of regexes, it's going to get pretty painful. Finite automata just doesn't scale that well. At that point, you really start wanting a more specialized solution. Probably the best answer to that that I know of is Hyperscan. And you're in luck; someone maintains a fork of ripgrep with support for Hyperscan: https://sr.ht/~pierrenn/ripgrep/ https://sr.ht/~pierrenn/ripgrep/ (A special case is tens of thousands of literal patterns. ripgrep will notice that and should use Aho-Corasick. It doesn't help so much with search time since it's just a NFA or a DFA like with regexes, but the machine itself is constructed much more quickly.)

gnfargbl 5y ago
What an incredibly helpful reply. Thank you! It sounds like either plain ripgrep, or ripgrep+hyperscan, is pretty much exactly what I'm looking for. Next time I have this problem, I'll certainly be reaching for it.
vlovich123 5y ago
Out of curiosity, what prevents the hyperscan support from being mainlined?
- burntsushi 5y ago
  Too much of a weighty dependency and too much of a niche IMO. For example, the last time I tried to build Hyperscan, I failed and gave up after 15 minutes of trying.
  - vlovich123 5y ago
    I would have thought you just need to include the rust-hyperscan crate[1] which would take care of that for you (but that crate probably didn't exist when you looked at it). I don't have a sense on the impact it has on overall binary size. [1] https://crates.io/crates/hyperscan https://crates.io/crates/hyperscan
    - burntsushi 5y ago
      I don't think the existence of a crate or not really impacts anything I said. More to the point, it would put a reliance on someone else to maintain a crate for critical functionality in ripgrep. (And if that fell through, I would invariably need to pick up that burden. Removing functionality is a lot harder than adding it.) It makes a lot more sense to me for something like Hyperscan to be maintained out of tree. I did work with the patch author a bit, and in particular, made some changes to ripgrep to make maintaining such a fork easier: https://github.com/BurntSushi/ripgrep/issues/1488 https://github.com/BurntSushi/ripgrep/issues/1488 Bottom line is, a lot of people think that adding a dependency has nearly zero cost. But it doesn't. Not by a long shot.

jemfinch 5y ago

I've written this code (in C++) for an employer. RE2 scaled fine to hundreds of thousands of regexes. You'll want to use RE2::Set, which compiles multiple regexes into a single DFA, and probably the "Filter" functionality (whose name I don't precisely remember and am too lazy to look up) which uses an Aho-Corasick tree to subset the potential matches. One thing you'll have to watch out for is RE2's maximum DFA size; if compilation of your RE2::Set fails, just split your set of regexes in half and compile again. You could probably do some fun optimizations by grouping the regexes which depend on the same literals into their own sets, but I never needed to.

burntsushi 5y ago
This is basically what ripgrep will do for you automatically. (ripgrep uses Rust's regex engine, which is a descendant of RE2.) But when you get up into hundreds of thousands of regexes, the NFA (and the resulting DFA) get really big. And things generally don't scale that well. Here's a good example: http://web.archive.org/web/20210302010420/https://01.org/hyperscan/blogs/jpviiret/2017/regex-set-scanning-hyperscan-and-re2set http://web.archive.org/web/20210302010420/https://01.org/hyp... The problem is that for a big enough NFA, you'll wind up spending most of your search doing powerset construction to build the DFA. > One thing you'll have to watch out for is RE2's maximum DFA size You can configure this in ripgrep with the --dfa-size-limit flag. (See also --regex-size-limit.)