on short strings that request captures, don't run the DFA

[BurntSushi]

Currently, if a caller requests captures, then we always run the DFA to determine the extent of the match and then we run either the Pike VM or the bounded backtracker on only the extent of the match to fill in the capture locations. This works well when searching long strings because the DFA can save the NFA engines from doing a lot of work. But on short strings, the DFA probably doesn't pay for itself, so we should just run one of the NFA engines if the string is short enough. (More precisely, in cases where the match is roughly the same length as the entire string, then the DFA isn't helping us at all since the NFA engine will still run the length of the match. But, obviously, this case isn't possible to know up front, so we use "short strings" as a likely predictor of that case.)

There should be some experimentation to determine where this boundary lies, so that we can invent a heuristic for when the string is "short enough."

[arielb1]

If a regex is "anchored" (starting with a ^ and ending with a $ in non-multiline mode), then there is never a point in determining the extent of the match. Anchored regexes are quite a common use-case when regexes are used for parsing/validation.

[BurntSushi]

@arielb1 That's a good observation! We should add that to the heuristic as well.

One possible downside I just thought of: the DFA is still useful in the non-match scenario, since it can detect a match failure much more quickly than the NFA engines can.

[BurntSushi]

For anyone interested in working on this, the relevant code is in the core implementation of the read_captures_at method:

regex/src/exec.rs

Line 513 in d813518

fn read_captures_at(

In particular, right now, it will always run the DFA engine if the DFA engine was selected by the compiler. The optimization in question here would be to add a conditional in the DFA case that checks if a string is below a certain length, and if it is, just skip directly to running the NFA.

To pick the right length, I'd suggest writing a micro benchmark that:

1. Uses a regex with several capture groups.
2. Searches strings of varying lengths.

You may find it useful to construct the regex and the search text such that the regex matches the entire text. In particular, there are cases where running the DFA and the NFA is actually faster because the DFA can determine "not a match" more quickly than the NFA can.

An alternative/additional implementation path is to take @arielb1's advice and check if the regex is completely anchored. You can do that using self.nfa.is_anchored_start and self.nfa.is_anchored_end.