Empirical and analytic study of stack versus heap cost for languages with closures

Andrew W. Appel, Zhong Shao

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

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

Original languageEnglish (US)
Pages (from-to)47-74
Number of pages28
JournalJournal of Functional Programming
Volume6
Issue number1
DOIs
StatePublished - Jan 1996

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Empirical and analytic study of stack versus heap cost for languages with closures'. Together they form a unique fingerprint.

Cite this