News for hackers. Stuff that matters.
Re:Go performance from version 1.2 to 1.18 by burntsushi on Friday February 04, 2022 @09:57AM (#30207514)
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.)

There are no comments on this comment yet.