[antlr-interest] Resetting an AST tree walker

Steve Souza steve at stevesouza.com
Thu Apr 23 14:07:51 PDT 2009


Were you able to track overall performance using both CommonTreeNodeStream
and BufferedTreeNodeStream?  Just because that portion of the code is slower
in BufferedTreeNodeStream doesn't mean that overall the code is slower.

On Thu, Apr 23, 2009 at 4:44 PM, Sam Harwell <sharwell at pixelminegames.com>wrote:

>  I’m working with much larger input files (a few thousand normal source
> code files).
>
>
>
> The significant action performed on a TreeNodeStream is a call to
> LA(int32). For BufferedTreeNodeStream, this encloses the call to
> FillBuffer().
>
>
>
> The profiler revealed that BufferedTreeNodeStream.LA used 3.10% of the
> inclusive profiling samples. CommonTreeNodeStream.LA used only 1.95% over
> the same operation. I believe that for expected case inputs,
> CommonTreeNodeStream is the preferred TreeNodeStream, and the current
> performance is no worse than BufferedTreeNodeStream.
>
>
>
> In FastQueue<T>, constructor the list (FastQueue<T>.data) with a default
> capacity of 20. Let me know if the performance of CommonTreeNodeStream
> improves.
>
>
>
> Sam
>
>
>
> *From:* antlr-interest-bounces at antlr.org [mailto:
> antlr-interest-bounces at antlr.org] *On Behalf Of *Steve Souza
> *Sent:* Thursday, April 23, 2009 2:48 PM
> *To:* Terence Parr
> *Cc:* antlr-interest at antlr.org
> *Subject:* Re: [antlr-interest] Resetting an AST tree walker
>
>
>
> <<I'm surprised by the speed difference though. I might have to rethink my
> filter; that is, which stream it uses.>>
> My test case which I execute 1,000,000 times:
> ((2*3*4)/(2*3*4)+10*(5+5))*.5
>
>
> Execution time Using *BufferedTreeNodeStream* is *5855 ms*.
>                 CommonTree commonTree=(CommonTree)ast.getTree();
>                 TreeNodeStream nodes=new
> BufferedTreeNodeStream(commonTree);
>                 TreeParser walker=new MyTreeParser(nodes);
>
> Execution time Using *CommonTreeNodeStream* is *17387* *ms*.
>                 CommonTree commonTree=(CommonTree)ast.getTree();
>                 TreeNodeStream nodes=new CommonTreeNodeStream(commonTree);
>                 TreeParser walker=new MyTreeParser(nodes);
>
> The performance difference would vary based on how many times you execute
> the case.  My application executes code like this a lot, so I used a high
> numbered test case.
>
> Calling reset on both BufferedTreeNodeStream and CommonTreeNodeStream both
> work properly for my code.   If I call TreeParser.reset() the subsquent
> calls give me the following message:  MyTreeParser.g: node from line 0:0 no
> viable alternative at input 'EOF'
>
> What method should I call to allow me to keep looping the TreeParser?
> Calling it on the NodeStreams seem to work, but I don't know if that is the
> preferred approach.  Also, is there a reason reset() isn't defined on either
> TreeNodeStream or IntStream.  It forces me to do a typecast like the
> following:
>
>              private void resetStream() {
>                 TreeNodeStream nodeStream=getTreeNodeStream();
>                 if (nodeStream instanceof BufferedTreeNodeStream)
>                   ((BufferedTreeNodeStream)nodeStream).reset();
>                 else if (nodeStream instanceof CommonTreeNodeStream)
>                   ((CommonTreeNodeStream)nodeStream).reset();
>              }
>
> Thanks for your help.
>
>
>
> On Thu, Apr 23, 2009 at 2:56 PM, Terence Parr <parrt at cs.usfca.edu> wrote:
>
>
> On Apr 22, 2009, at 8:17 PM, Steve Souza wrote:
>
> <<I don't like this at all, but I believe in the thread that you cited
> earlier someone says it is the intended behaviour.>>
> I wonder what the logic is there.  One of the big benefits of a tree walker
> is to be able to repeatedly walk the nodes.  I hope they don't remove that
> capability from the BufferedTreeNodeStream.
>
>
>
> Don't worry. We will keep the buffered version for sure. The primary reason
> to avoid the buffered version is when you're tree is absolutely huge and you
> can afford to create a big array pointing and all the nodes.  In the new
> tree filter mechanism, not yet officially released but in the software, it
> needs to constantly parse little snippets of the tree. re-creating an array
> for each subtree doesn't make much sense.
>
> I'm surprised by the speed difference though. I might have to rethink my
> filter; that is, which stream it uses.
>
>
>
> Did that one work for you?  Except for increased memory is there ever a
> reason not to use BufferedTreeNodeStream instead of CommonTreeNodeStream?
>
>
>
> Nope.
>
> Ok, just checked.  Added 2 unit tests.  TreeIterator and
> CommonTreeNodeStream reset properly.  Perhaps it's the tree parser?
>
> Ter
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20090423/e2262bd6/attachment.html 


More information about the antlr-interest mailing list