An Empirical and Analytic Study of Stack vs. Heap Cost for Languages with Closures
Last modified: Tue Mar 14 19:33:30 2000 GMT.
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:
Overall, the execution cost of stack-allocated and heap-allocated
frames is similar; but heap frames are simpler to implement and allow
very efficient first-class continuations.
- 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
- 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.
- 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 small.
- The demands of modern programming languages make stacks
complicated to implement efficiently and correctly.
In Journal of Functional Programming, 6(1): 47-74,