Loading ...
Sorry, an error occurred while loading the content.

Re: [antlr-interest] Is this Recognizer optimization valid?

Expand Messages
  • Sander Mägi
    RE: [antlr-interest] Is this Recognizer optimization valid?The ASTPair hack gave some 30% reduced garbage and 20% increased speed (on my anyway handoptimized
    Message 1 of 13 , Oct 3, 2001
    • 0 Attachment
      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 -----
      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@...]
      Sent: Wednesday, October 03, 2001 12:58 AM
      To: antlr-interest@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@...]
      > Sent: Tuesday, October 02, 2001 7:58 AM
      > To: antlr-interest@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@...>
      > To: <antlr-interest@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@... ----- +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.
    • Ric Klaren
      ... For testing I already implemented it in my development version. Ric -- ... And this rebooting business? Give it a good kicking, do you? Oh, no, of
      Message 2 of 13 , Oct 3, 2001
      • 0 Attachment
        On Wed, Oct 03, 2001 at 05:07:43PM +0200, Sander M�gi wrote:
        > 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)

        For testing I already implemented it in my development version.

        Ric
        --
        -----+++++*****************************************************+++++++++-------
        ---- Ric Klaren ----- klaren@... ----- +31 53 4893722 ----
        -----+++++*****************************************************+++++++++-------
        'And this 'rebooting' business? Give it a good kicking, do you?' 'Oh, no,
        of course, we ... that is ... well, yes, in fact,' said Ponder. 'Adrian
        goes round the back and ... er ... prods it with his foot. But in a
        technical way,' he added. --- From: Hogfather by Terry Pratchett.
      • mzukowski@bco.com
        Thanks for trying it! Monty ... From: Sander Mägi [mailto:sander@aqris.com] Sent: Wednesday, October 03, 2001 8:08 AM To: antlr-interest@yahoogroups.com
        Message 3 of 13 , Oct 3, 2001
        • 0 Attachment
          RE: [antlr-interest] Is this Recognizer optimization valid?

          Thanks for trying it!

          Monty

          -----Original Message-----
          From: Sander Mägi [mailto:sander@...]
          Sent: Wednesday, October 03, 2001 8:08 AM
          To: antlr-interest@yahoogroups.com
          Subject: 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@...
          To: antlr-interest@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@...]
          Sent: Wednesday, October 03, 2001 12:58 AM
          To: antlr-interest@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@...]
          > Sent: Tuesday, October 02, 2001 7:58 AM
          > To: antlr-interest@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@...>
          > To: <antlr-interest@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@... ----- +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.


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

        • Terence Parr
          ... My $0.02 here. The real way to optimize this is to do awy with the ASTPair in favor of two local variables. No mem allocation/deallocation. At the cost
          Message 4 of 13 , Oct 7, 2001
          • 0 Attachment
            On Wednesday, October 3, 2001, at 08:07 AM, Sander Mägi wrote:

            > The ASTPair hack gave some 30% reduced garbage and 20% increased speed
            > (on my anyway handoptimized lexer and recognizer)

            My $0.02 here. The real way to optimize this is to do awy with the
            ASTPair in favor of two local variables. No mem
            allocation/deallocation. At the cost of some inline code (since I would
            remove the surrounding object ASTPair), currentAST could be converted to
            currentAST_root and currentAST_child. The resulting inlined code would
            increase code size (but hopefully not that much).

            Ter
          Your message has been successfully submitted and would be delivered to recipients shortly.