[antlr-interest] pleasant new table-based DFA speed
Terence Parr
parrt at cs.usfca.edu
Sun Jun 4 12:51:29 PDT 2006
Howdy,
Current DFAs are implemented as one object per state and virtual
method calls are used to transition from 1 state to another. New
implementation uses one object per DFA and does array lookups to
move. The new DFA are much smaller and it turns out much faster.
Parsing time (no tree construction) for Java 1.4.2 source with 16.8M
of code (as measured by System.currentTimeInMillis averaged over 3
attempts after one throwaway to get into mem cache).
Old DFA: 3619.00ms
Both old and new DFA: 4123.66ms
New DFA: 3036.00ms
That implies that we get about both-old = 4123.66 - 3619=505ms cost
for DFA simulation when parsing Java using new DFA and both-new =
1088ms for using old DFA. The ms counter in Java is not very
accurate, but it looks like we save almost 600ms using new DFA. That
is 83% of old cost to parse. Not bad. The wallclock shows an
overall drop from an average of 4.29s to 3.57, again about a 17%
savings.
Not bad...almost done with them; gotta do the predicated "special"
states.
Wow. Parsing is really moving now. 3.57s to parse all of that text
is pretty nice. :) v3 Lexing speed is like 5x v2 speed.
Ter
More information about the antlr-interest
mailing list