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.