]> Savannah Git Hosting - gnulib.git/commit
dfa: optimize alternation in NFA
authorNorihiro Tanaka <noritnk@kcn.ne.jp>
Tue, 18 Sep 2018 17:07:23 +0000 (10:07 -0700)
committerPaul Eggert <eggert@cs.ucla.edu>
Wed, 19 Sep 2018 02:16:52 +0000 (19:16 -0700)
commit4299106ceab30ee5f3333e6b0c1adf5568699e5f
tree732fa0f1a3033c285897d6b5e57904cf74d3621c
parente648401be0895249f29c8804aefff49a5ff7b957
dfa: optimize alternation in NFA

Even when similar states exist in alternation, the DFA treats them
as separate items, which may complicate the transition in NFA and
cause slowdown.  This change assembles the states into one.  For
example, ab|ac is changed into a(b|c).  This change speeds-up
matching for many branched patterns.  For example, grep speeds up
more than 30× in:

  seq 10000 | sed 's/$/ abcdefghijklmnopqrstuvwxyz/; s/$/./' >in
  time -p env LC_ALL=C grep -vf in in

* lib/dfa.c (prune): New function.
(merge_nfa_state): New function.  It merges similar NFA states.
(dfaoptimize): New function.  It seeks merged and removed nodes.
(dfaanalyze): Call new function.
(dfautf8noss): Change name from dfaoptimize because of addition of new
function.
(dfacomp): Update caller.
ChangeLog
lib/dfa.c