FWIW, I would say that it's difficult for a Thompson NFA on its own to beat backtracking in non-pathological cases. So I actually think your prior is still most

FWIW, I would say that it's difficult for a Thompson NFA on its own to beat backtracking in non-pathological cases. So I actually think your prior is still mostly correct. Now a hybrid NFA/DFA (or a "lazy DFA") that does subset construction at search time using a Thompson NFA can definitely beat out a backtracker. A lazy DFA will generally match the speed of a fully compiled DFA, and is about an order of magnitude faster than a Thompson NFA simulation: [andrew@frink regex-automata]$ regex-cli find nfa thompson pikevm "@$medium" '(?m)^\w{30}$' build pike vm time: 6.584596ms create cache time: 278.231µs search time: 7.798138892s counts: [3] [andrew@frink regex-automata]$ regex-cli find hybrid dfa "@$medium" '(?m)^\w{30}$' parse time: 24.256µs translate time: 20.202µs compile nfa time: 5.966991ms nfa memory: 486196 build hybrid dfa time: 3.137µs hybrid dfa memory: 486196 create cache time: 21.793µs search time: 406.746917ms cache clear count: 0 counts: [3] [andrew@frink regex-automata]$ regex-cli find dfa dense "@$medium" '(?m)^\w{30}$' parse time: 22.824µs translate time: 15.513µs compile nfa time: 6.000195ms nfa memory: 486196 compile dense dfa time: 106.35009ms dense dfa memory: 4501024 dense alphabet length: 117 dense stride: 128 search time: 448.568888ms counts: [3] $ ls -lh $medium -rw-rw-r-- 1 andrew users 280M Jul 14 2021 /home/andrew/data/benchsuite/subtitles/2018/OpenSubtitles2018.raw.sample.medium.en (This is using an yet-unreleased tool as part of ongoing regex development.)