[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