[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