llvm dev - May 2014 - [LLVMdev] Question about implementing exceptions, especially to the VMKit team

Hi all, I'm working on implementing exceptions in Pyston, and I was hoping
to get some guidance from the list.  I think I've learned enough about
C++-style DWARF exceptions to convince myself I have a workable approach,
but then I found this VMKit paper (2010) which says

The exception manager: To manage exceptions, J3 reserves
a
> word for the pending exception in the local storage of each thread.
> After each method invocation, the word is tested. If an exception
> has been raised and the function is able to trap the exception, a
> branch to the exception handler is executed. Otherwise, the function
> returns to the caller. This implementation is not optimal because it
> requires a test and branch after each method invocation. A more
> efficient implementation would use exception tables. However, at
> time of writing the paper, the exception tables generated by LLVM
> rely on the GCC runtime library [19] which is not optimized for
> dynamically generated tables, at least on Linux.

So now I'm reexamining whether C++-style exceptions are a good choice for
Python, which I would guess throws more exceptions than Java.

Does anyone have advice on the subject?  I'm wary of the costs of having to
branch after every function call, but maybe that ends up not being too much
of a performance drain if the CPU can predict them correctly?  But then
again, it looks like VMKit has moved to a setjmp-longjmp approach, which
makes me think that there must have been some overhead that they wanted to
avoid.

I'm also curious about why libgcc is slow on dynamically generated tables,
and if that's still true with MCJIT (I assume the VMKit change was made
while on the old JIT).

thanks,
kmod
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140501/55c66826/attachment.html>

Hi Kevin,

I have beginning a new implementation of exception in VMKit with the
dwarf exception tables. Unfortunately, I have not finished yet, so I
can not answer :) I'm pretty sure that, today, dwarf is a better
solution than our test after each method invocation. But I don't have
any evidence for that...

Anyway, using the dwarf exception tables with VMKit is not so
complicated, so you can also try. If you need help, just tell me.
Basically, I have not yet exhaustively tested them (at least, it
works), mainly because I'm re-writting all VMKit to use MCJIT!

Gaël



2014-05-01 23:09 GMT+02:00 Kevin Modzelewski <kmod at
dropbox.com>:
> Hi all, I'm working on implementing exceptions in Pyston, and I was
hoping
> to get some guidance from the list.  I think I've learned enough about
> C++-style DWARF exceptions to convince myself I have a workable approach,
> but then I found this VMKit paper (2010) which says
>
>> The exception manager: To manage exceptions, J3 reserves a
>> word for the pending exception in the local storage of each thread.
>> After each method invocation, the word is tested. If an exception
>> has been raised and the function is able to trap the exception, a
>> branch to the exception handler is executed. Otherwise, the function
>> returns to the caller. This implementation is not optimal because it
>> requires a test and branch after each method invocation. A more
>> efficient implementation would use exception tables. However, at
>> time of writing the paper, the exception tables generated by LLVM
>> rely on the GCC runtime library [19] which is not optimized for
>> dynamically generated tables, at least on Linux.
>
>
> So now I'm reexamining whether C++-style exceptions are a good choice
for
> Python, which I would guess throws more exceptions than Java.
>
> Does anyone have advice on the subject?  I'm wary of the costs of
having to
> branch after every function call, but maybe that ends up not being too much
> of a performance drain if the CPU can predict them correctly?  But then
> again, it looks like VMKit has moved to a setjmp-longjmp approach, which
> makes me think that there must have been some overhead that they wanted to
> avoid.
>
> I'm also curious about why libgcc is slow on dynamically generated
tables,
> and if that's still true with MCJIT (I assume the VMKit change was made
> while on the old JIT).
>
> thanks,
> kmod


-- 
-------------------------------------------------------------------
Gaël Thomas, Associate Professor, UPMC
http://pagesperso-systeme.lip6.fr/Gael.Thomas/
-------------------------------------------------------------------

I have some data points on this. 

- The style of exception handling employed by VMKit has in the past been used as
an optimization. For example, OpenVM switched to this after using C++ exceptions
for along time because it was a net performance win. This is because Java-like
languages tend to do more exception throwing than the C++ runtime is tuned for
and the cost of unwinding in C++ is too great: so paying one branch after every
call ends up being cheaper, for many benchmarks, than using C++ exceptions
because all benchmarks have some throwing (usually at least internally in the
standard library). Such high exception volume may be a Javaism.

- WebKit uses LLVM and does exceptions. The implementation is incomplete (I.e.
We won't use the LLVM JIT for some exception code paths) but the basic idea
is there: 1) throwing an exception through a function that doesn't catch
just means you need to just use unwind meta-data. That's easy with
compact_unwind. 2) catching can be done by using either deoptimization
(deoptimize the entire catching function) or by ensuring that state live in a
catch is spilled. It's best to do both: use deoptimization if profiling
tells you that the catch doesn't execute and switch to spilling if it does.
The benefit is that the deopt approach is very fast if zero throwing happens and
the spilling approach will let you implement very efficient unwinding for when
it happens with high volume.

I'm not sure this can completely answer your question. Exception
implementation is a tricky subject with many strategies and it's an area
where you could easily come up with fresh ideas. :-)

-Filip
> On May 1, 2014, at 2:09 PM, Kevin Modzelewski <kmod at dropbox.com>
wrote:
> 
> Hi all, I'm working on implementing exceptions in Pyston, and I was
hoping to get some guidance from the list.  I think I've learned enough
about C++-style DWARF exceptions to convince myself I have a workable approach,
but then I found this VMKit paper (2010) which says
> 
>> The exception manager: To manage exceptions, J3 reserves a
>> word for the pending exception in the local storage of each thread.
>> After each method invocation, the word is tested. If an exception
>> has been raised and the function is able to trap the exception, a
>> branch to the exception handler is executed. Otherwise, the function
>> returns to the caller. This implementation is not optimal because it
>> requires a test and branch after each method invocation. A more
>> efficient implementation would use exception tables. However, at
>> time of writing the paper, the exception tables generated by LLVM
>> rely on the GCC runtime library [19] which is not optimized for
>> dynamically generated tables, at least on Linux.
> 
> 
> So now I'm reexamining whether C++-style exceptions are a good choice
for Python, which I would guess throws more exceptions than Java.
> 
> Does anyone have advice on the subject?  I'm wary of the costs of
having to branch after every function call, but maybe that ends up not being too
much of a performance drain if the CPU can predict them correctly?  But then
again, it looks like VMKit has moved to a setjmp-longjmp approach, which makes
me think that there must have been some overhead that they wanted to avoid.
> 
> I'm also curious about why libgcc is slow on dynamically generated
tables, and if that's still true with MCJIT (I assume the VMKit change was
made while on the old JIT).
> 
> thanks,
> kmod
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140501/0a1787de/attachment.html>

On 05/01/2014 02:09 PM, Kevin Modzelewski wrote:
> Hi all, I'm working on implementing exceptions in Pyston, and I was 
> hoping to get some guidance from the list.  I think I've learned 
> enough about C++-style DWARF exceptions to convince myself I have a 
> workable approach, but then I found this VMKit paper (2010) which says
>
>     The exception manager: To manage exceptions, J3 reserves a
>     word for the pending exception in the local storage of each thread.
>     After each method invocation, the word is tested. If an exception
>     has been raised and the function is able to trap the exception, a
>     branch to the exception handler is executed. Otherwise, the function
>     returns to the caller. This implementation is not optimal because it
>     requires a test and branch after each method invocation. A more
>     efficient implementation would use exception tables. However, at
>     time of writing the paper, the exception tables generated by LLVM
>     rely on the GCC runtime library [19] which is not optimized for
>     dynamically generated tables, at least on Linux.
>
>
> So now I'm reexamining whether C++-style exceptions are a good choice 
> for Python, which I would guess throws more exceptions than Java.
>
> Does anyone have advice on the subject?  I'm wary of the costs of 
> having to branch after every function call, but maybe that ends up not 
> being too much of a performance drain if the CPU can predict them 
> correctly?  But then again, it looks like VMKit has moved to a 
> setjmp-longjmp approach, which makes me think that there must have 
> been some overhead that they wanted to avoid.
We have a local implementation which supports both check-after-call and 
unwind tables.  I don't have good performance numbers across a wide 
suite of benchmarks (yet), but our early numbers showed using C++-style 
exceptions to be a significant win on the normal path.  We haven't 
measured the exception path yet.

An interesting point is that (at least in theory), you don't need to 
pick one strategy.  You could use c++ style exceptions for "cold 
throws", and check-after-call for "warm throws".  This is quite a
bit of
infrastructure to build mind you.  :)

We've also considered the idea of speculating that functions don't throw
and de-optimizing if it turns out they do.  We haven't implemented this 
yet, but on the surface, it sounds like a pretty good idea.  Note that 
you'd need a recompilation mechanism to support the best use of this.

>
> I'm also curious about why libgcc is slow on dynamically generated 
> tables, and if that's still true with MCJIT (I assume the VMKit change 
> was made while on the old JIT).
I don't know the answer to this.  I'm not familiar with the mechanism 
the old JIT provided in this area.

Philip
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140502/c7224bcf/attachment.html>

Hi Kevin,

To elaborate on Philip's point, depending on the state Pyston's
runtime already is in, you may have the choice of using a hybrid of a
"pending exception" word in your runtime thread structure, and an
implicit alternate ("exceptional") return address for calls into
functions that may throw.  This lets you elide the check on the
pending exception word after calls by turning them into invokes that
unwind into a landingpad containing a generic exception handler.  This
generic exception handler then checks the type of the pending
exception word and handles the exception (which may involve rethrowing
to the caller if the current frame doesn't have catch handler).

Instead of relying on libgcc to unwind when you throw you can then
parse the [call PC, generic exception handling PC] pairs from the
.eh_frame section, and when throwing to your caller, look up the
generic exception handling PC (using the call PC pushed on the stack)
and "return" to that instead.  Rethrow is similar.

This scheme has the disadvantage of "returning" through every active
frame on an exception throw, even if a particular frame never had an
exception handler and could've been skipped safely.  However, this
scheme allows you to easily switch to one of two other implementations
based on profiling data on a per-callsite basis:

 1. high exception volume -- if an invoke has seen too many exception
    throws, recompile by replacing the invoke with a call followed by
    a test of "pending exception" and branch.  The logic to generate
    the branch target should largely be the same as logic to generate
    the landing pad block.

 2. low exception volume -- keep the invoke, but put a deoptimization
    trap in the landing pad block.

We did some rough benchmarking, and using such implicit exceptions
(i.e. not explicitly checking the pending exception word) reduces
non-throwing call overhead by 20-25%.  I don't have any numbers on how
it affects the performance of exceptional control flow though.

-- Sanjoy