Why is PikeVM the slowest engine?

[zackradisic]

In the docs it says the PikeVM regex engine "tends to be a tool of last resort because it is also usually the slowest regex engine".

I feel like executing bytecode should be faster than dealing with the big graph data structures associated with the other DFA-based approaches

Can anyone offer any insight on why this is the case?

[BurntSushi]

I think I answered this on HackerNews:

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

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 for now.

I also very briefly touch on this in my blog post on regex internals:

The main problem with the PikeVM is performance, and its poor performance is primarily rooted in having to keep track of so much state. The capture group positions are required to report the start and end match offsets, while the currently active states must be tracked in order to guarantee worst case O(m * n) time. That is, in contrast to a backtracking approach, the PikeVM visits each byte in the haystack at most a constant number of times, and it does so by computing all possible active states in lock-step. This adds quite a bit of overhead, and it can be exacerbated by regexes with a lot of epsilon transitions. (This is one of the reasons why, earlier in this blog, we spent so much time talking about optimizations in the NFA to elide epsilon transitions.)

You can even see this in the code itself. For example, this bit is executed for every byte in a haystack:

regex/regex-automata/src/nfa/thompson/pikevm.rs

Lines 1457 to 1490 in 837fd85

	/// Process the active states in 'curr' to find the states (written to
	/// 'next') we should process for the next byte in the haystack.
	///
	/// 'stack' is used to perform a depth first traversal of the NFA when
	/// computing an epsilon closure.
	///
	/// When a match is found, the slots for that match state (in 'curr') are
	/// copied to 'caps'. Moreover, once a match is seen, processing for 'curr'
	/// stops (unless the PikeVM was configured with MatchKind::All semantics).
	#[cfg_attr(feature = "perf-inline", inline(always))]
	fn nexts(
	&self,
	stack: &mut Vec<FollowEpsilon>,
	curr: &mut ActiveStates,
	next: &mut ActiveStates,
	input: &Input<'_>,
	at: usize,
	slots: &mut [Option<NonMaxUsize>],
	) -> Option<PatternID> {
	instrument!(|c| c.record_state_set(&curr.set));
	let mut pid = None;
	let ActiveStates { ref set, ref mut slot_table } = *curr;
	for sid in set.iter() {
	pid = match self.next(stack, slot_table, next, input, at, sid) {
	None => continue,
	Some(pid) => Some(pid),
	};
	slots.copy_from_slice(slot_table.for_state(sid));
	if !self.config.get_match_kind().continue_past_first_match() {
	break;
	}
	}
	pid
	}

Compare that with a DFA, where the number of instructions executed per byte of haystack is constant and very small:

regex/regex-automata/src/dfa/search.rs

Lines 97 to 124 in 837fd85

	let mut prev_sid;
	while at < input.end() {
	prev_sid = unsafe { next_unchecked!(sid, at) };
	if dfa.is_special_state(prev_sid) || at + 3 >= input.end() {
	core::mem::swap(&mut prev_sid, &mut sid);
	break;
	}
	at += 1;
	sid = unsafe { next_unchecked!(prev_sid, at) };
	if dfa.is_special_state(sid) {
	break;
	}
	at += 1;
	prev_sid = unsafe { next_unchecked!(sid, at) };
	if dfa.is_special_state(prev_sid) {
	core::mem::swap(&mut prev_sid, &mut sid);
	break;
	}
	at += 1;
	sid = unsafe { next_unchecked!(prev_sid, at) };
	if dfa.is_special_state(sid) {
	break;
	}
	at += 1;
	}