implement one-pass NFA matcher

[BurntSushi]

It turns out that when a regex is deterministic, the NFA simulation can be implemented much more efficiently because it only needs to keep track of one set of capture groups (instead of a set of capture groups for every thread).

There are two components to adding this:

• Detecting whether a regex is deterministic or not. A regex is said to be deterministic if, at any point during the execution of a regex program, at most one thread can lead to a match state.
• Writing a specialized NFA simulation.

In terms of code, it would be nice if we could find a way to reuse code with the full NFA simulation.

This should be easier to implement than #66, and should boost the performance of a lot of regexes. (Of course, we should do both a one pass NFA and #66!)

[SeanRBurton]

Can you please elaborate on what exactly you mean by this, and perhaps point to some literature and/or examples?

[BurntSushi]

I'm not aware of any literature on this topic, and as far as I know, Russ Cox came up with it. He talks about it briefly here: https://swtch.com/~rsc/regexp/regexp3.html (CTRL-F for one-pass).

The definition in my OP is the key: a one-pass NFA can be used to evaluate a regex where, at any point during the evaluation of the machine, at most one transition can lead to a match. So if you know your machine has that property, you don't need to keep track of as much state as the full NFA simulation.

The last time I looked at implementing this, the tricky part I think was actually detecting one-pass regexes. It can probably be simplified by starting with a routine that reports a lot of false negatives (false positives cannot be allowed).

[SeanRBurton]

Thanks for the info; what I was missing is that it can only be used for anchored matches, so that we do not have to introduce a new thread of execution for each input character.

[BurntSushi]

Right. Unanchored regexes have a .*? put implicitly at the beginning, which immediately defeats the one-pass optimization.

[jneem]

FWIW, the regex-dfa crate makes it trivial to check whether the regex is one-pass: the DFA created by regex-dfa is minimized, and so it's one-pass iff it has no branches.

I'm not sure how to go from there to a one-pass NFA, though. Specifically, you'd need to get back the capture groups somehow.

[ethanpailes]

How does a 1-pass NFA simulation compare with an NFA simulation that does lookahead before spawing new threads at branch points? It seems like the advantage of a 1-pass simulation is that it will never spawn more than 1 thread, because there are no non-deterministic branches. Adding lookahead (or [previews][previews] to generalize even further) is an optimization that other engines sometimes do, and it seems to me like an engine that does lookahead at every branch will never spawn more than 1 thread for a 1-pass NFA.

I bring this up because I keep playing with the idea of trying to impliment previews or lookahead (no promises), but this 1-pass NFA thing also seems like a pretty easy optimization to do and I'm wondering if anyone has any insight about whether or not these optimizations are a 1-or-the-other sort of thing.

[BurntSushi]

It seems like the advantage of a 1-pass simulation is that it will never spawn more than 1 thread

Correct. Thereby eliminating the overhead of managing and tracking threads. A one-pass NFA implementation uses this fact to avoid creating threads in the first place.

and it seems to me like an engine that does lookahead at every branch will never spawn more than 1 thread for a 1-pass NFA.

I don't follow this. A one-pass NFA will never spawn more than one thread, period. Lookahead/preview have nothing to do with that.

Adding previews permits you to limit the creation of threads in the general case for a non-one-pass NFA.

(I suspect I am misunderstanding your query.)

[ethanpailes]

and it seems to me like an engine that does lookahead at every branch will never spawn more than 1 thread for a 1-pass NFA.

I should have said "1-pass regex". You are 100% right that a 1-pass NFA can't spawn new threads. Sorry for the confused communication.

To unpack my point a bit more using the examples that Russ Cox provides on his website. /([^x]*)x(.*)/ is one-pass. An engine that does lookahead before spawning new threads on a repetition will never spawn more than one thread for this regex because the 1-previews of /[^x]*/ and /x/ are disjoint. It seems like a 1-pass NFA would have to do basically the same thing, while being a bit less general, but I'm worried I'm missing something subtle.

[BurntSushi]

@ethanpailes Hmm. I'm still having trouble understanding the essence of your question. Note that the determination of whether a regex is one pass or not is made at compile time, and that information is then used to switch to a completely different implementation of the Pike VM that doesn't use threads at all. In that implementation there would be no previews/look-ahead, and in fact, there would be no point at all in using previews/look-ahead for that case since you would only ever be using one thread.

[ethanpailes]

Oh, now that you mention the PikeVM I realize that the lookahead version would have to do lots of extra work to copy capture group info around because it wouldn't know that it was only ever going to spawn 1 thread. I think my thinking was muddled by thinking more about the bounded backtracker. Thanks!

[ethanpailes]

So I've been quitely spinning my wheels on this for the last month or so, and after a few embarrassing false starts I think I've gotten something worth talking about in public. I'm a little confused by the terminology surrounding onepass matchers, because it seems to me that they are only applicable when a regex has no non-determinism, in which case a DFA can impliment capture groups just fine, so that's what I implimented. The code I linked is a pretty good proof of concept but there are lots of outstanding issues.

• I've completely punted on regexsets. They don't seem neccicary for a first pass over the problem.
• I have not implimented EmptyLook assertions. It seems like it ought to be pretty easy by introducing a new special state, but when I was reading through the DFA code to shameless steal everything that looked useful I saw something about flags. I wanted to ask what was going on there before I just went ahead and did the intermediate state thing.
• The execution planner plumbing that I did is downright criminal. Same goes for my regex-debug changes. Those both need to be fixed before there is any chance of merging.
• It might be worth looking at the applicability criterion that I used to see when a regex is onepass. Right now I just look for branch points and check to see if the first set of any of the regex at the branch points intersect. It think it may be possible to just boldly try to construct a onepass DFA and then give up whenever we see non-determinism instead.
• I have not done any loop unrolling. This is not super pressing, but it would be fun.
• I need to do some more comprehensive benchmarking once all the features are there and correct.

I'm not entirely sure what the execution planner should do with onepass dfas yet. Onepass DFAs are the most useful where we would otherwise have to use an NFA to extract capture groups, but there is a chance that they could do better than the lazy DFA because they should have lower warmup cost. When a regex has no non-determinism, there can never be an exponential blowup in space (no non-determinism means no compound states from the powerset construction), so I just AOT compiled the FSM.

Anyway, here's what happens when I ran all the benchmarks containing capture groups.

 name                           old.bench ns/iter     new.bench ns/iter     diff ns/iter   diff %  speedup 
 misc::short_haystack_1000000x  149,041 (53676 MB/s)  146,018 (54787 MB/s)        -3,023   -2.03%   x 1.02 
 misc::short_haystack_100000x   15,449 (51783 MB/s)   13,817 (57900 MB/s)         -1,632  -10.56%   x 1.12 
 misc::short_haystack_10000x    4,024 (19883 MB/s)    1,259 (63551 MB/s)          -2,765  -68.71%   x 3.20 
 misc::short_haystack_1000x     696 (11510 MB/s)      281 (28508 MB/s)              -415  -59.63%   x 2.48 
 misc::short_haystack_100x      452 (1794 MB/s)       192 (4223 MB/s)               -260  -57.52%   x 2.35 
 misc::short_haystack_10x       400 (227 MB/s)        157 (579 MB/s)                -243  -60.75%   x 2.55 
 misc::short_haystack_1x        391 (48 MB/s)         147 (129 MB/s)                -244  -62.40%   x 2.66 
 misc::short_haystack_20x       425 (402 MB/s)        174 (982 MB/s)                -251  -59.06%   x 2.44 
 misc::short_haystack_2x        405 (66 MB/s)         162 (166 MB/s)                -243  -60.00%   x 2.50 
 misc::short_haystack_30x       421 (596 MB/s)        180 (1394 MB/s)               -241  -57.24%   x 2.34 
 misc::short_haystack_3x        401 (87 MB/s)         149 (234 MB/s)                -252  -62.84%   x 2.69 
 misc::short_haystack_40x       432 (766 MB/s)        187 (1770 MB/s)               -245  -56.71%   x 2.31 
 misc::short_haystack_4x        395 (108 MB/s)        151 (284 MB/s)                -244  -61.77%   x 2.62 

The bigger versions show less speedup because there is a literal scan optimization happening, so as the input grows, less and less time is spent in the main matching engine.

[ethanpailes]

I know this is a pretty big wad of code and issues to cough up, so if you are interested in triage: comments about the EmptyLook stuff and pontification on execution planning would probably be the most helpful to me right now.

[BurntSushi]

That looks like awesome work! I'm not sure when I'll be able to review it, but it might be a good idea to just open a PR when you think it's in a reasonable mergeable state. It is a lot of code though, and unfortunately i won't be able to merge it until I'm confident that I understand it thoroughly.

I'm not sure i understand your question about EmptyLook though.

[ethanpailes]

I'm not sure i understand your question about EmptyLook though.

That's fine. I'll just implement EmptyLooks with an intermediary state. I figured there was about a 50% chance that I wasn't being entirely coherent about flags.

I fully expect this to take a long time to merge even after I open the PR. Considering that this is a whole new backend, getting things to a point where you are comfortable with all of the code is very important. A PR is probably a ways out though.