Re: Compiling with continuations

As pointed out by Delacour and Boehm, heap allocation of
activation/suspension records usually results in bad cache and virtual
memory behavior. Besides, there's another factor that makes heap
allocation of activation records essentially slower than stack allocation
-- even with huge caches and clever, VM-conscious garbage collectors.


Heap-allocated records are not necessarily contiguous, hence every record
must contain a pointer to the previous record. Stack-allocated records
are contiguous, hence you don't have to link them. It is true that many
compilers do link stack frames, by maintaining a frame pointer. However,
some modern compilers such as the MIPS compiler do not maintain a frame
pointer, and perform all stack accesses relative to the stack pointer.


As a consequence, setting up a heap-allocated suspension record requires
at least two memory references, one to write the return address, one to
write a pointer to the previous record. (This is in addition to the cost
of actually allocating the record in the heap, which, as Appel correctly
points out, can be as low as if it were allocated in the stack.)
Activating the suspension record also requires two memory references, to
fetch the return address and the saved continuation. With stack frames,
the corresponding operations -- setting up a frame, and returning to the
caller -- perform only one memory reference each (to save and restore the
return address), with the "no frame pointer" approach. And for leaf
functions, this drops to zero memory references on the MIPS and the SPARC.


- Xavier Leroy
    The Caml Light racing team
    Projet Formel, INRIA Rocquencourt, France
--

Return to the comp.compilers page.
Search the comp.compilers archives again.