Re: exception systems

[Marc Feeley <feeley@iro.umontreal.ca>]

> > 3) References to parameters when the reference follows a non-tail call
> > (because frames can't be extended in place, you actually have to chain
> > the various parts of a function's frame, each part corresponding
> > to a non-tail call in the function's body).
> 
> I didn't quite follow.  Parameters are always passed in
> registers... so why does parameter access slow down?

It is when the number of parameters and/or the number of live local
variables exceeds the number of registers that the overhead occurs.
So for trivial benchmarks you will not see an overhead but for
"realistic" code you will probably see it (note: I have no data to
back this up).  Anyway, for simplicity, assume you have no registers,
then in the following code:

(lambda (x)
  (let ((y (f x)))
    (+ y x)))

which is CPS-converted to:

(lambda (x k)
  (f x (lambda (y) (k (+ y x)))))

the second reference to x is more expensive than the first because you
have to follow one static link to get to it.  The situation gets worse
and worse as you increase the number of non-tail calls, for example in:

(lambda (x)
  (let* ((a (f x))
         (b (g x))
         (c (h x)))
    (+ a b c x)))

the last reference to x needs to traverse 3 static links to get to x.
The reference cost can be decreased by using a "flat-closures" representation
but then it becomes more expensive to create each continuation frame
because the live variables need to be copied to the new frame.  In a stack
implementation you can simply extend the current frame by adjusting
the stack-pointer/frame-pointer (which can be done lazily, i.e. at
most one pair of SP increment/decrement per function call).

Marc