3 ms·

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 "l

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.

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.