[antlr-interest] comments on suggestion to reduce tree constr uction code size

Terence Parr parrt at jguru.com
Wed Dec 26 10:50:14 PST 2001

On Wednesday, December 26, 2001, at 07:16  AM, mzukowski at bco.com wrote:

>> Parsing all of ANTLR code itself without gates is 17sec
>> on my G4 450Mhz OS X box versus the regular 19sec
> I'm scratching my head as to why the version without gates ran faster 
> than
> the one with gates?  Are the if()s taking more time than just creating 
> the
> AST node?

That's what I thought at first until I realized that the gates are 
always being executed while the wasted ast creation is only done while 
"guessing", which by design is done infrequently.  Somehow, removing the 
gates wins over the infrequent but expensive memory allocation.  
Probably depends a lot on the garbage collector's efficiency at 
reallocating objects of a common.

> To make this scheme work, you would have to make sure that your 
> initialize()
> methods in your node class were side-effect free.  Folks with 
> heterogenous

Very true.  But that makes sense I'd say.  We could make it a rule :)

> trees might be more inclined to do table adds in their initialize(),
> perhaps?  I suppose that the guessing state could be passed to the
> initializer....or for that matter to the factory which could then just 
> not
> build a tree, right?

Sure...ASTFactory.create() could also just ask the parser (have to add a 
ref to the parser in there though).  That would be like executing all of 
the gates again though.

> I like that better.  astFactory.create() returns nullAST if currently
> guessing.  Will addASTChild and friends deal with that ok?  Will a java

Hm...probably not.

> optimizer cache inputState.guessing==0 for those tests?  Probably 
> not--can't

maybe not across method calls.

> guarantee another thread won't muck with it.  The generated code could 
> have
> a boolean in the method, updated only upon entry to the method and on 
> every
> guessing++ and guessing--.

I'm thinking we can get away with saying that creation of nodes (even 
hetero nodes) must be side effect free.

Chief Scientist & Co-founder, http://www.jguru.com
Creator, ANTLR Parser Generator: http://www.antlr.org


Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 

More information about the antlr-interest mailing list