An Empirical and Analytic Study of Stack vs. Heap Cost for Languages with Closures
Report ID: TR-450-94Author: Shao, Zhong / Appel, Andrew W.
Date: 1994-03-00
Pages: 12
Download Formats: |Postscript|
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.