An Empirical and Analytic Study of Stack vs. Heap Cost for Languages with Closures

Abstract:

It has been proposed that allocating procedure activation records on a
garbage collected heap is more efficient than stack allocation.
However, previous comparisons of heap vs. stack allocation have been
over-simplistic, neglecting (for example) frame pointers, or the
better locality of reference of stacks.
We present a comprehensive analysis of all the components of creation,
access, and disposal of heap-allocated and stack-allocated activation
records. Among our results are:
Although stack frames are known to have a better cache read-miss rate than
heap frames, our simple analytical model (backed up by simulation
results) shows that the difference is too trivial to matter.
* The cache write-miss rate of heap frames is very high; we show that
a variety of miss-handling strategies (exemplified by specific modern
machines) can give good performance, but not all can.
* The write-miss policy of the primary cache is much more important
than the write-miss policy of the secondary cache.
* Stacks restrict the flexibility of closure representations
(for higher-order functions) in important (and costly) ways.
* The extra load placed on the garbage collector by heap-allocated frames
is very small.
* The demands of modern programming languages make stacks quite
complicated to implement efficiently and correctly.
Overall, the execution cost of stack-allocated and heap-allocated frames
is very similar; but heap frames are simpler to implement and
allow very efficient first-class continuations (call/cc).

This technical report has been published as

Empirical and Analytic Study of Stack versus Heap Cost for
Languages with Closures. Zhong Shao and Andrew W. Appel, Journal of Functional Programming
6(1) 47-74, 1996.