[antlr-interest] how to do exceptions quickly

[Benjamin Niemann]

Terence Parr wrote:
> 
> On Nov 4, 2007, at 1:16 AM, Benjamin Niemann wrote:
> 
>> Hi,
>>
>> Terence Parr wrote:
>>> I had a long conversation at Google last night with Neal Gafter, the 
>>> guy who built the javac compiler when he was at Sun. He told me that 
>>> exceptions can be made to execute very quickly.  The only thing you 
>>> have to avoid is the actual exception object creation which has to do 
>>> all of the expensive stack trace creation and so on.  He says that 
>>> the actual throwing of the exception itself is not a problem.  This 
>>> might be something to look at later to see if it goes quickly, 
>>> because it results in cleaner backtracking code.  Anyway, we can 
>>> create some singleton objects, which will solve the problem.  Hooray!
>>> Anyway, this might be useful to people in general.  I thought was 
>>> pass along this interesting trick.
>>
>> As a follow-up to this long forgotten thread: I just replaced the 
>> failed flag by a BacktrackingFailed exception in my Python target. I 
>> got rid of all flag checking reducing the file size of the generated 
>> parser by ~5% and having a small performance gain of about ~2 (using 
>> the Java.g parser).
>> If you are interested, look at CL 4272.
> 
> So 2% faster in python?  Perhaps python is slow to try/catch (only 
> create is slow in java).
> 
> Code was much cleaner though right?

I got rid of all the book keeping code for _state.failed, which gives me 
the small but still measurable perf gain (I had to reintroduce a similar 
flag when memoization is turned on, but it is much cheaper).
Adding the try..except block (only in synpredNN methods, where the 
parser is interested of the success/failure result) should be very cheap 
in Python AFAIK.
Also note that my perf timing was very simple. I just timed the whole 
process runtime, including interpreter startup (which should not be 
significant, because the parsed file was big enough to take a few 
seconds) and most significantly including the lexing phase - where most 
of the time is spent and the lexer was not effected by this change!
So the parser itself should see more than these 2%.
And it would probably be nice to have a grammar and input where 
backtracking fails very often to see the worst case impact of raising 
exceptions. Java.g had ~750 BacktrackingFailed exceptions for the 80KB 
java input file.