[antlr-interest] Exception tests eat performance?

Karl Meissner meissnersd at yahoo.com
Wed Jan 7 10:29:41 PST 2004



--- mzukowski at yci.com wrote:
> There are other sources of exceptions which you would need to analyze the
> code before knowing you could use goto.  For instance rules can have initial
> actions, which are executed during syn preds and which could potentially
> throw exceptions.  And when lookahead conditions aren't met we throw an
> exception because remember the same code is used during syn preds and when
> not in a syn pred.  So you would need a hook into the user exception
> handling stuff so it would be handled a different way if you aren't
> exceptioning out.


I agree.   sigh. It would be a major rewrite and could only be done on a big version change. 

The biggest impact would be to the way antlr does predicate checking 
and user errors. 

But I still think it would be a big performance win. 

No gotos in java, thats do-able.   

Instead of every code block being a try{}catch 
you could do most things with break and returning a result stucture. 
Null result is success.

At the end of every block check result is null to coninue. 

   struct ResultInfo ; //ErrorInfo is a struct that can hold the 
                           //info we are putting into the exception currently


Have match and rules return errorinfo structs on error, null on success. 

ErrorInfo Match( Symbol t ) { 
      if ( LA( 1 ) != t ) 
            return new ResultInfo( t, linenumber, etc); 

      consume(); 
      return null; //success
}


ResultInfo Rule1() { 

    ResultInfo  result=null; //null until sucess
   //stuff

   for(;;){ // inside some block


       for(;;) { 
          if( (result = Rule2()) != null  } break;

          if( (result = Match( SYM123 ) ) != null  } break;
       }
       if( result != null ) break;  //put this after every single code block
                                    // will break to the top level
                                    // a poor man's goto
                                    // still cheaper then a catch even if nested deep
   } 
   if( result != null ) break;  //etc.

   //stuff

    if( result != null ) { 
     //handle result  

    } 
    return result;    
}
 

  



> 
> And of course you can't do this for java because of the lack of goto.  Maybe
> you could get away with labeled breaks and continues, I haven't thought it
> through yet.
> 
> This will be easier to experiment with in antlr 3 because writing code
> generators will be template driven.
> 
> Monty
> 
> -----Original Message-----
> From: Karl Meissner [mailto:meissnersd at yahoo.com] 
> Sent: Wednesday, January 07, 2004 8:55 AM
> To: antlr-interest at yahoogroups.com
> Subject: [antlr-interest] Exception tests eat performance?
> 
> 
> It seems that antlr uses exceptions in a lot of the generated parsers where
> simple test will do. 
> Everything that I have read is that an exceptions have a very high overhead
> and it is undesirable 
> to  generate them in a tight loop where they happen a lot. 
> 
> Exceptions are used so extensivly it would require a big rewrite to change
> but I wanted to 
> raise it as an issue
> 
> A very common piece of code in a parser is 
> 
> try {
>   {
>     match( SYM1 );
>     match( SYM2 );
>     match( SYM3 );
>  }
> } catch (RecognitionException)	{
>   synPredMatched84 = false;
> }
> 
> where match throws an exception if the next token is not the parameter. 
> Since match is just
> public virtual void  match(int t)
> {
>     if (LA(1) != t)
> 	throw new MismatchedTokenException(tokenNames, LT(1), t, false,
> getFilename());
>     else
> 	consume();
> }
> 
> 
> Using if based tests would be faster I think...
> 
> Something like this
> 
> bool Rule10() { 
>   if( !Rule22() ) goto 	_RecognitionException_123:
> 
>   currentSym = SYM1; if ( LA( 1 ) != currentSym ) goto
> _RecognitionException_123; consume(); 
>   currentSym = SYM2; if ( LA( 1 ) != currentSym ) goto
> _RecognitionException_123; consume(); 
>   currentSym = SYM3; if ( LA( 1 ) != currentSym ) goto
> _RecognitionException_123; consume(); 
>     
>   return true; 
> 
>   _RecognitionException_123:
>     if (0 == inputState.guessing)
>     {
>       reportError(currentSym);
>       consume();
>       consumeUntil(tokenSet_27_);
> 
>       return true;  //attempt to recover in the calling rule
>     }
>     else //guessing
>     {
> 	return false; 
>     }
>   }
> 
> I probably missed some the the code paths with predicate guessing and error
> handling but 
> I still think you can get the same behavior as the exception with a
> combination of if, goto and
> storing information into stack.   
> 
> And get a performance improvement....
> 
> Karl 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> __________________________________
> Do you Yahoo!?
> Yahoo! Hotjobs: Enter the "Signing Bonus" Sweepstakes
> http://hotjobs.sweepstakes.yahoo.com/signingbonus
> 
>  
> 
> Yahoo! Groups Links
> 
> To visit your group on the web, go to:
>  http://groups.yahoo.com/group/antlr-interest/
> 
> To unsubscribe from this group, send an email to:
>  antlr-interest-unsubscribe at yahoogroups.com
> 
> Your use of Yahoo! Groups is subject to:
>  http://docs.yahoo.com/info/terms/ 
> 
> 
>  
> 
> Yahoo! Groups Links
> 
> To visit your group on the web, go to:
>  http://groups.yahoo.com/group/antlr-interest/
> 
> To unsubscribe from this group, send an email to:
>  antlr-interest-unsubscribe at yahoogroups.com
> 
> Your use of Yahoo! Groups is subject to:
>  http://docs.yahoo.com/info/terms/ 
> 
> 


__________________________________
Do you Yahoo!?
Yahoo! Hotjobs: Enter the "Signing Bonus" Sweepstakes
http://hotjobs.sweepstakes.yahoo.com/signingbonus

 

Yahoo! Groups Links

To visit your group on the web, go to:
 http://groups.yahoo.com/group/antlr-interest/

To unsubscribe from this group, send an email to:
 antlr-interest-unsubscribe at yahoogroups.com

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




More information about the antlr-interest mailing list