[antlr-interest] Resetting an AST tree walker

Steve Souza steve at stevesouza.com
Thu Apr 23 12:48:20 PDT 2009


<<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/673a240a/attachment.html 


More information about the antlr-interest mailing list