An Empirical and Analytic Study of Stack vs. Heap Cost for Languages with Closures
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.