[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