[antlr-interest] Is this Recognizer optimization valid?

Sander Mägi sander at aqris.com
Wed Oct 3 08:07:43 PDT 2001


RE: [antlr-interest] Is this Recognizer optimization valid?The ASTPair hack gave some 30% reduced garbage and 20% increased speed (on my anyway handoptimized lexer and recognizer)

As for the guessing state hack - I took the enormous effort (that turned out to be 20 minutes with the help of refactoring browser I am developing) to make a copy of recognizer and make duplicates of all methods for 'guessing mode' by hand. This only gave some 7-8% improvement. For vanilla antlr generated recognizer that would be 3% so it's not such a good thing.

Sander 
  ----- Original Message ----- 
  From: mzukowski at bco.com 
  To: antlr-interest at yahoogroups.com 
  Sent: Wednesday, October 03, 2001 3:27 PM
  Subject: RE: [antlr-interest] Is this Recognizer optimization valid?


  Yes, you're right, you wouldn't necessarily need the guessing state as an int, it could be boolean or implied by the code path.  Guess you would have to try it to see how it works.

  Do you know how much speed improvement you gained by your ASTPair hack? 

  Monty 

  -----Original Message----- 
  From: Sander Mägi [mailto:sander at aqris.com] 
  Sent: Wednesday, October 03, 2001 12:58 AM 
  To: antlr-interest at yahoogroups.com 
  Subject: Re: [antlr-interest] Is this Recognizer optimization valid? 



  > You could do that but you still have to have guessing guards around individual productions, of course.  And you still have to increment and decrement the > guessing state just as happens now because syntactic predicates can be nested arbitrarily.

   
  Are you sure? 
    
  I think we would not need the guessing guard nor increment/decrement. 
    
  When code sees a syntatic predicate then it would not to 'guessing++;statement();guessing--' but rather 'statementGuessing();' - statementGuessing would call only guessing rules. It does not matter if the predicates are nested or not because guessing mode ends only when this statementGuessing is completed.

   
  This is same for current mode - only currently the inputstate.guessing becomes 2 when there is a nested predicate and 3 when yet another - it does not matter because the guessing variable is only tested for 0/nonzero anyway.

   
  > Just how much guessing is your code doing? 
    
  I am using java.g grammar from resources section - I really don't if it can be optimized- I can say that the hack I sent earlyer reduced ASTPair object generation by 30 percent (calculated this way that percentages look larger :).

   
  Sander 
    



  You could do that but you still have to have guessing guards around individual productions, of course.  And you still have to increment and decrement the guessing state just as happens now because syntactic predicates can be nested arbitrarily.

  Just how much guessing is your code doing?  Some people overuse syntactic predicates because they don't understand proper factoring of rules or they don't think about the shortest syntactic predicate that will work.  But with a truly ambiguous language you will have no choice but to use syntactic predicates.

   
  Monty 
  > -----Original Message----- 
  > From: Sander Mägi [mailto:sander at aqris.com] 
  > Sent: Tuesday, October 02, 2001 7:58 AM 
  > To: antlr-interest at yahoogroups.com 
  > Subject: Re: [antlr-interest] Is this Recognizer optimization valid? 
  > 
  > 
  > Couldn't the codegen actually generate methods like 'statement' and 
  > 'statementGuessing' and skip the if(inputStateGuessing ==0) 
  > parts at all? 
  > 
  > Probably C++ compilers do proper inlining and make it fast, but my 
  > experience shows that in java many things that should be 'naturally 
  > optimized' are not. 
  > 
  > Sander 
  > 
  > ----- Original Message ----- 
  > From: "Ric Klaren" <klaren at cs.utwente.nl> 
  > To: <antlr-interest at yahoogroups.com> 
  > Sent: Tuesday, October 02, 2001 4:43 PM 
  > Subject: Re: [antlr-interest] Is this Recognizer optimization valid? 
  > 
  > 
  > > Hi, 
  > > 
  > > On Tue, Oct 02, 2001 at 04:40:34PM +0200, Sander Mägi wrote: 
  > > > null would give null pointer exception. The ASTpair's 
  > root and child 
  > > > variables are still read for their content like returnAst = 
  > currentAst.root. 
  > > 
  > > Ack you're right. But in the codegen these could be guarded by an 
  > > (guessing != 0) check. 
  > > 
  > > Ric 
  > > -- 
  > > 
  > -----+++++**************************************************** 
  > *+++++++++-- 
  > ----- 
  > >     ---- Ric Klaren ----- klaren at cs.utwente.nl ----- +31 53 
  > 4893722  ---- 
  > > 
  > -----+++++**************************************************** 
  > *+++++++++-- 
  > ----- 
  > >      Human beings, who are almost unique in having the 
  > ability to learn 
  > >    from the experience of others, are also remarkable for 
  > their apparent 
  > >          disinclination to do so. --- Douglas Adams, Last 
  > Chance to See 
  > > 
  > > 
  > > 
  > > 
  > > Your use of Yahoo! Groups is subject to 
  http://docs.yahoo.com/info/terms/ 
  > 
  > 
  > 



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



  Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service. 



  Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service. 


  Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service. 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20011003/30855e7d/attachment.html


More information about the antlr-interest mailing list