The FLINT Project

Research

People

Publications

Software

Support

Links

Internal

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

Last modified: Tue Mar 14 19:33:30 2000 GMT.

Authors

Andrew Appel
Zhong Shao

Abstract

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.
  • 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.
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.

Published

In Journal of Functional Programming, 6(1): 47-74, January 1996.

Text

Gzipped Postscript [754k]
PDF
BibTeX Entry

Copyright © 1996-2017 The FLINT Group <flint at cs dot yale dot edu>
Yale University Department of Computer Science
Validate this page
colophon