[armedbear-devel] Performance: Analysis of options to reduce exception handlers

[Erik Huelsmann]

Based on Joel's reaction regarding my profiling attempts on exception
rates/exception handling in ABCL, I've been thinking how to do better
in the exceptions/specials restoration department.


Let me start by describing how our current exception handling/specials
restoration is structured. It should be noted that the current
strategy works the way it does because we were failing to restore
special values all over the place. This made me decide that we should
restore specials when leaving the binding block, even if that is
through non-local transfer of control, with the contrived example for
exception handlers as given in my mail earlier this month.

Looking at the profiling results, we're now correct, but probably
we're not very efficient at doing it.


This is what I've been thinking:

If a block binds special variables, there are 3 ways to exit the block:

 1. through normal sequential execution of the byte code
 2. through a function-local jump out of the block
 3. through a non-local transfer of control (modelled using the
ControlTransfer exception in ABCL)

Case (1) is easy: we just reach the end of the binding block, at which
point there is a call to "LispThread.restoreSpecialBindings(mark);".

Case (2) is a little more involved: before jumping to the target
location the specials are restored at the jump-location. To do this,
there's a bit of logic in the compiler to find out which restore point
to use.

Case (3) is quite involved: at the call site an exception is thrown
causing the stack to be unwound. When looking at it like this, the
catch-site should restore its specials state. There's no need to do
that, currently, because all the intermediate levels restore their
state. There is at least one special case here: unwind-protect may be
executing lisp code (which needs its specials restored to the right
state) without being the final catch location. Final catch requiring
forms are quite easily determined: TAGBODY (to catch GO), BLOCK (to
catch RETURN) and CATCH (to catch THROW).

One of the major drawbacks of this scheme is that all non-local
transfers become responsible for restoring their special bindings.
BLOCK and TAGBODY forms which don't serve as non-local target are not
affected by this reasoning; they fall under case (2). CATCH can never
be considered taking only local transfers of control as it  However,
the entire application may not be binding any specials at all. The
overhead involves a call at the start of each block which contains
non-local-transfer targets to snapshot the special bindings state and
to restore it *in case of a non-local transfer*. The calls involved
are markSpecialBindings() and restoreSpecialBindings(), two very short
and - I think - efficient functions.

So, there's a small drawback in applications which don't use special
bindings much. However, the potential gain in applications which do
use them is quite relevant: the example I gave before shows that a
relatively simple function binding the same special variable three
times will cause 3 separate specials-unwinding-exception blocks, each
rethrowing the exception to the next level. Thinking about it a bit
more, I realize that no additional exception blocks have to be
registered. Just only the catch/restore of specials state.


Looking at it this way, I propose that we stop restoring specials in
finally blocks, moving part of the responsibility of having correct
specials bindings to BLOCK, CATCH, TAGBODY and UNWIND-PROTECT. My
change should affect both the interpreter and the compiler, to get the
full benefit of efficiency. However, I thought I'd implement the
LET/LET* binding optimization in the compiler first, just to see how
much we benefit from this change in Maxima.


Comments?



Bye,



Erik.