4 ms·

Ripgrep implements many regex engines and select the best performant for a given regex Here's an overview of them https://docs.rs/regex-automata/latest/regex_

Ripgrep implements many regex engines and select the best performant for a given regex Here's an overview of them https://docs.rs/regex-automata/latest/regex_automata/#available-regex-engines https://docs.rs/regex-automata/latest/regex_automata/#availa...

masklinn 3y ago
One that seems to be missing from the list is Spencer’s, which I know of from being postgres’ (and tcl’s) and infamously supports backreferences while being quite resilient to the usual backtracking NFA issues.
- burntsushi 3y ago
  It's not really "missing" because it's not intended to be an exhaustive list of all possible approaches. :-) It is merely a list of the regex engines currently in use in the regex crate. It's essentially the same as RE2. But with the addition of a full DFA and a public versioned API for each of the internal engines. See: https://blog.burntsushi.net/regex-internals/ https://blog.burntsushi.net/regex-internals/ The regex crate follows the RE2 tradition of not supporting features that aren't known how to implement efficiently.
zackoverflow 3y ago
Does anyone have any insight on why the PikeVM implementation is slower (it's based on the VM approach described here https://swtch.com/~rsc/regexp/regexp2.html https://swtch.com/~rsc/regexp/regexp2.html) I feel like compiling regex to bytecode and executing it should be faster than dealing with big graph like structures with NFAs/DFAs Also, V8's regex engines are very fast because they get JIT compiled to machine code, so wouldn't bytecode just be one step higher in abstraction, and have worse but similar performance?
- burntsushi 3y ago
  Before getting to your actual question, it might help to look at a regex benchmark that compares engines (perhaps JITs are not the fastest in all cases!): https://github.com/BurntSushi/rebar https://github.com/BurntSushi/rebar In particular, the `regex-lite` engine is strictly just the PikeVM without any frills. No prefilters or literal optimizations. No other engines. Just the PikeVM. As to your question, the PikeVM is, essentially, an NFA simulation. The PikeVM just refers to the layering of capture state on top of the NFA simulation. But you can peel back the capture state and you're still left with a slow NFA simulation. I mention this because you seem to compare the PikeVM with "big graph structures with NFAs/DFAs." But the PikeVM is using a big NFA graph structure. At a very high level, the time complexity of a Thompson NFA simulation and a DFA hints strongly at the answer to your question: searching with a Thompson NFA has worst case O(m*n) time while a DFA has worst case O(n) time, where m is proportional to the size of the regex and n is proportional to the size of the haystack. That is, for each character of the haystack, the Thompson NFA is potentially doing up to `m` amount of work. And indeed, in practice, it really does need to do some work for each character. A Thompson NFA simulation needs to keep track of every state it is simultaneously in at any given point. And in order to compute the transition function, you need to compute it for every state you're in. The epsilon transitions that are added as part of the Thompson NFA construction (and are, crucially, what make building a Thompson NFA so fast) exacerbate this. So what happens is that you wind up chasing epsilon transitions over and over for each character. A DFA pre-computes these epsilon closures during powerset construction. Of course, that takes worst case O(2^m) time, which is why real DFAs aren't really used in general purpose engines. Instead, lazy DFAs are used. As for things like V8, they are backtrackers. They don't need to keep track of every state they're simultaneously in because they don't mind taking a very long time to complete some searches. But in practice, this can make them much faster for some inputs. Feel free to ask more questions. I'll stop here.

masklinn 3y ago

One that seems to be missing from the list is Spencer’s, which I know of from being postgres’ (and tcl’s) and infamously supports backreferences while being quite resilient to the usual backtracking NFA issues.

burntsushi 3y ago
It's not really "missing" because it's not intended to be an exhaustive list of all possible approaches. :-) It is merely a list of the regex engines currently in use in the regex crate. It's essentially the same as RE2. But with the addition of a full DFA and a public versioned API for each of the internal engines. See: https://blog.burntsushi.net/regex-internals/ https://blog.burntsushi.net/regex-internals/ The regex crate follows the RE2 tradition of not supporting features that aren't known how to implement efficiently.

zackoverflow 3y ago

Does anyone have any insight on why the PikeVM implementation is slower (it's based on the VM approach described here https://swtch.com/~rsc/regexp/regexp2.html https://swtch.com/~rsc/regexp/regexp2.html) I feel like compiling regex to bytecode and executing it should be faster than dealing with big graph like structures with NFAs/DFAs Also, V8's regex engines are very fast because they get JIT compiled to machine code, so wouldn't bytecode just be one step higher in abstraction, and have worse but similar performance?

burntsushi 3y ago
Before getting to your actual question, it might help to look at a regex benchmark that compares engines (perhaps JITs are not the fastest in all cases!): https://github.com/BurntSushi/rebar https://github.com/BurntSushi/rebar In particular, the `regex-lite` engine is strictly just the PikeVM without any frills. No prefilters or literal optimizations. No other engines. Just the PikeVM. As to your question, the PikeVM is, essentially, an NFA simulation. The PikeVM just refers to the layering of capture state on top of the NFA simulation. But you can peel back the capture state and you're still left with a slow NFA simulation. I mention this because you seem to compare the PikeVM with "big graph structures with NFAs/DFAs." But the PikeVM is using a big NFA graph structure. At a very high level, the time complexity of a Thompson NFA simulation and a DFA hints strongly at the answer to your question: searching with a Thompson NFA has worst case O(m*n) time while a DFA has worst case O(n) time, where m is proportional to the size of the regex and n is proportional to the size of the haystack. That is, for each character of the haystack, the Thompson NFA is potentially doing up to `m` amount of work. And indeed, in practice, it really does need to do some work for each character. A Thompson NFA simulation needs to keep track of every state it is simultaneously in at any given point. And in order to compute the transition function, you need to compute it for every state you're in. The epsilon transitions that are added as part of the Thompson NFA construction (and are, crucially, what make building a Thompson NFA so fast) exacerbate this. So what happens is that you wind up chasing epsilon transitions over and over for each character. A DFA pre-computes these epsilon closures during powerset construction. Of course, that takes worst case O(2^m) time, which is why real DFAs aren't really used in general purpose engines. Instead, lazy DFAs are used. As for things like V8, they are backtrackers. They don't need to keep track of every state they're simultaneously in because they don't mind taking a very long time to complete some searches. But in practice, this can make them much faster for some inputs. Feel free to ask more questions. I'll stop here.