research-article

Open access

From folklore to fact: comparing implementations of stacks and continuations

Authors:

Kavon Farvardin,

John ReppyAuthors Info & Claims

PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 75 - 90

https://doi.org/10.1145/3385412.3385994

Published: 11 June 2020 Publication History

Abstract

The efficient implementation of function calls and non-local control transfers is a critical part of modern language implementations and is important in the implementation of everything from recursion, higher-order functions, concurrency and coroutines, to task-based parallelism. In a compiler, these features can be supported by a variety of mechanisms, including call stacks, segmented stacks, and heap-allocated continuation closures.

An implementor of a high-level language with advanced control features might ask the question ``what is the best choice for my implementation?'' Unfortunately, the current literature does not provide much guidance, since previous studies suffer from various flaws in methodology and are outdated for modern hardware. In the absence of recent, well-normalized measurements and a holistic overview of their implementation specifics, the path of least resistance when choosing a strategy is to trust folklore, but the folklore is also suspect.

This paper attempts to remedy this situation by providing an ``apples-to-apples'' comparison of six different approaches to implementing call stacks and continuations. This comparison uses the same source language, compiler pipeline, LLVM-backend, and runtime system, with the only differences being those required by the differences in implementation strategy. We compare the implementation challenges of the different approaches, their sequential performance, and their suitability to support advanced control mechanisms, including supporting heavily threaded code. In addition to the comparison of implementation strategies, the paper's contributions also include a number of useful implementation techniques that we discovered along the way.

References

[1]

Brian Anderson. 2013. Abandoning segmented stacks in Rust. https: //mail.mozilla.org/pipermail/rust-dev/2013-November/006314.html

[2]

Todd A. Anderson. 2010. Optimizations in a private nursery-based garbage collector. In Proceedings of the 2010 International Symposium on Memory management (Toronto, Ontario, Canada). Association for Computing Machinery, New York, NY, USA, 21–30. 1145/1806651.1806655

Digital Library

[3]

Andrew W. Appel. 1987. Garbage collection can be faster than stack allocation. Inform. Process. Lett. 25, 4 (1987), 275 – 279. org/10.1016/0020-0190(87)90175-X

Digital Library

[4]

Andrew W. Appel. 1989. Simple generational garbage collection and fast allocation. Software – Practice and Experience 19, 2 (Feb. 1989), 171–183.

[5]

Andrew W. Appel. 1992. Compiling with Continuations. Cambridge University Press, Cambridge, UK.

Digital Library

[6]

Andrew W. Appel. 1998. Modern Compiler Implementation in ML. Cambridge University Press, Cambridge, UK.

[7]

A. W. Appel and T. Jim. 1989. Continuation-passing, Closure-passing Style. In Conference Record of the 16th Annual ACM Symposium on Principles of Programming Languages (POPL ’89) (Austin, TX, USA). Association for Computing Machinery, New York, NY, USA, 293–302.

Digital Library

[8]

Andrew W. Appel and D. B. MacQueen. 1991. Standard ML of New Jersey. In Programming Language Implementation and Logic Programming (Lecture Notes in Computer Science), Vol. 528. Springer-Verlag, New York, NY, USA, 1–26.

[9]

Andrew W. Appel and Zhong Shao. 1992. Callee-save Registers in Continuation-passing Style. Lisp and Symbolic Computation 5, 3 (Sept. 1992), 191–221.

Digital Library

[10]

Andrew W Appel and Zhong Shao. 1996. An Empirical and Analytic Study of Stack vs. Heap Cost for Languages with Closures. Journal of Functional Programming 6, 01 (1996), 47–74. S095679680000157X

[11]

Joe Armstrong. 2007. Programming Erlang: Software for a Concurrent World. Pragmatic Bookshelf, Raleigh, NC.

Digital Library

[12]

Sven Auhagen, Lars Bergstrom, Matthew Fluet, and John Reppy. 2011. Garbage Collection for Multicore NUMA Machines. In MSPC 2011: Memory Systems Performance and Correctness (San José, California, USA). Association for Computing Machinery, New York, NY, USA, 51–57.

Digital Library

[13]

Jean-Loup Baer. 2009. Microprocessor architecture: from simple pipelines to chip multiprocessors. Cambridge University Press, Cambridge, UK.

[14]

Lars Bergstrom, Matthew Fluet, Mike Rainey, John Reppy, Stephen Rosen, Nora Sandler, and Adam Shaw. 2017. The Manticore Project. University of Chicago. Retrieved April 4, 2020 from https://manticore. cs.uchicago.edu

[15]

Carl Bruggeman, Oscar Waddell, and R. Kent Dybvig. 1996. Representing control in the presence of one-shot continuations. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’96) (Philadelphia, PA, USA). Association for Computing Machinery, New York, NY, USA, 99–107.

Digital Library

[16]

Perry Cheng, Robert Harper, and Peter Lee. 1998. Generational Stack Collection and Profile-driven Pretenuring. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’98) (Montreal, Quebec, Canada). Association for Computing Machinery, New York, NY, USA, 162–173.

Digital Library

[17]

Will Clinger, Anne Hartheimer, and Eric Ost. 1988. Implementation Strategies for Continuations. In Conference record of the 1988 ACM Conference on Lisp and Functional Programming (Snowbird, Utah, USA). Association for Computing Machinery, New York, NY, USA, 124–131.

Digital Library

[18]

William D. Clinger and Lars T. Hansen. 2017. The Larceny Project. Retrieved April 4, 2020 from http://www.larcenists.org

[19]

William D. Clinger, Anne H. Hartheimer, and Eric M. Ost. 1999. Implementation Strategies for First-Class Continuations. Higher-order and Symbolic Computation 12, 1 (1999), 7–45. 1010016816429

Digital Library

[20]

Olivier Danvy and Julia L. Lawall. 1992. Back to Direct Style II: Firstclass Continuations. In Conference record of the 1992 ACM Conference on Lisp and Functional Programming (San Francisco, CA, USA). Association for Computing Machinery, New York, NY, USA, 299–310.

Digital Library

[21]

Edsger W Dijkstra. 1960. Recursive programming. Numer. Math. 2, 1 (1960), 312–318.

Digital Library

[22]

Amer Diwan, J. Eliot B. Moss, and Richard L. Hudson. 1992. Compiler support for garbage collection in a statically typed language. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’92) (San Francisco, CA, USA). Association for Computing Machinery, New York, NY, USA, 273–282.

Digital Library

[23]

Damien Doligez and Georges Gonthier. 1994. Portable, unobtrusive garbage collection for multiprocessor systems. In Conference Record of the 21st Annual ACM Symposium on Principles of Programming Languages (POPL ’94) (Portland, OR, USA). Association for Computing Machinery, New York, NY, USA, 70–83.

Digital Library

[24]

174673

[25]

Damien Doligez and Xavier Leroy. 1993. A concurrent, generational garbage collector for a multithreaded implementation of ML. In Conference Record of the 20th Annual ACM Symposium on Principles of Programming Languages (POPL ’93) (Charleston, SC, USA). Association for Computing Machinery, New York, NY, USA, 113–123.

Digital Library

[26]

Alan A.A. Donovan and Brian W. Kernighan. 2015. The Go Programming Language (1st ed.). Addison-Wesley, Reading, MA, USA.

Digital Library

[27]

R. Kent Dybvig and Robert Hieb. 1989. Engines from continuations. Computer Languages 14, 2 (1989), 109–123. 0096-0551(89)90018-0

Digital Library

[28]

Kavon Farvardin. 2017. Weighing Continuations for Concurrency. Master’s thesis. Department of Computer Science, University of Chicago, Chicago IL.

[29]

Kavon Farvardin and John Reppy. 2018. Compiling with Continuations and LLVM. In Proceedings 2016 ML Family Workshop / OCaml Users and Developers workshops (Nara, Japan) (Electronic Proceedings in Theoretical Computer Science), Kenichi Asai and Mark Shinwell (Eds.), Vol. 285. Open Publishing Association, Waterloo, NSW, Australia, 131– 142.

[30]

Kathleen Fisher and John Reppy. 2002. Compiler support for lightweight concurrency. Technical Memorandum. Bell Labs. http://moby.cs. uchicago.edu/papers/2002/tm-lightweight-concur.pdf

[31]

Matthew Fluet, Nic Ford, Mike Rainey, John Reppy, Adam Shaw, and Yingqi Xiao. 2007. Status Report: The Manticore Project. In Proceedings of the 2007 ACM SIGPLAN Workshop on ML. Association for Computing Machinery, New York, NY, USA, 15–24.

Digital Library

[32]

Matthew Fluet, Mike Rainey, and John Reppy. 2008. A Scheduling Framework for General-purpose Parallel Languages. In Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming ICFP ’08 (Victoria, BC, Canada). Association for Computing Machinery, New York, NY, USA, 241–252. 1411203.1411239

Digital Library

[33]

Matthew Fluet, Mike Rainey, John Reppy, and Adam Shaw. 2011. Implicitly-threaded Parallelism in Manticore. Journal of Functional Programming 20, 5–6 (2011), 537–576. S0956796810000201 PLDI ’20, June 15–20, 2020, London, UK Kavon Farvardin and John Reppy

[34]

Lal George, Florent Guillame, and John H. Reppy. 1994. A Portable and Optimizing Back End for the SML/NJ Compiler. In Proceedings of the 5th International Conference on Compiler Construction (CC ’94). Springer-Verlag, New York, NY, USA, 83–97. 540-57877-3_6

[35]

GHC. 2020. The Glasgow Haskell Compiler. Retrieved April 4, 2020 from http://www.haskell.org/ghc

[36]

Simcha Gochman, Ronny Ronen, Ittai Anati, Ariel Berkovits, Tsvika Kurts, Alon Naveh, Ali Saeed, Zeev Sperber, and Robert C Valentine. 2003. The Intel Pentium M Processor: Microarchitecture and Performance. Intel Technology Journal 7, 2 (2003), 21–36.

[37]

Marcelo J. R. Gonçalves and Andrew W. Appel. 1995. Cache Performance of Fast-allocating Programs. In Functional Programming Languages and Computer Architecture (FPCA ’95) (La Jolla, CA, USA). Association for Computing Machinery, New York, NY, USA, 293–305.

Digital Library

[38]

Christopher T. Haynes, Daniel P. Friedman, and Mitchell Wand. 1984. Continuations and coroutines. In Conference Record of the 1984 ACM Symposium on Lisp and Functional Programming (Austin, TX, USA). Association for Computing Machinery, New York, NY, USA, 293–298.

Digital Library

[39]

Matthew Hertz and Emery D. Berger. 2005. Quantifying the Performance of Garbage Collection vs. Explicit Memory Management. In Proceedings of the 2005 ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications (OOPSLA ’05) (San Diego, CA, USA). Association for Computing Machinery, New York, NY, USA, 313–326.

Digital Library

[40]

R. Hieb, R. Kent Dybvig, and C. Bruggeman. 1990. Representing control in the presence of first-class continuations. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’90). Association for Computing Machinery, New York, NY, USA, 66–77.

Digital Library

[41]

Richard A. Kelsey. 1995. A Correspondence Between Continuation Passing Style and Static Single Assignment Form. In ACM SIGPLAN Workshop on Intermediate Representations (IR ’95) (San Francisco, CA, USA). Association for Computing Machinery, New York, NY, USA, 13–22.

Digital Library

[42]

Matthew Le and Matthew Fluet. 2015. Partial Aborts for Transactions via First-class Continuations. In ICFP ’15 (Vancouver, BC, Canada). Association for Computing Machinery, New York, NY, USA, 230–242.

Digital Library

[43]

Allen Leung and Lal George. 1999. Static Single Assignment Form for Machine Code. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’99) (Atlanta, GA, USA). Association for Computing Machinery, New York, NY, USA, 204–214.

Digital Library

[44]

Peng Li, Simon Marlow, Simon Peyton Jones, and Andrew Tolmach. 2007. Lightweight concurrency primitives for GHC. In Proceedings of the 2007 Haskell Workshop (Freiburg, Germany). Association for Computing Machinery, New York, NY, USA, 107–118. 10.1145/1291201.1291217

Digital Library

[45]

LLVM Developers. 2019. Garbage Collection Safepoints in LLVM. https://releases.llvm.org/9.0.0/docs/Statepoints.html

[46]

James S. Miller and Guillermo J. Rozas. 1994. Garbage Collection is Fast, but a Stack is Faster. Technical Report AIM-1462. MIT AI Laboratory. https://apps.dtic.mil/docs/citations/ADA290099

[47]

MLton. 2020. The MLton Standard ML compiler. Retrieved April 4, 2020 from http://mlton.org

[48]

Mikael Pettersson, Konstantinos Sagonas, and Erik Johansson. 2002. The HiPE/x86 Erlang Compiler: System Description and Performance Evaluation. In International Symposium on Functional and Logic Programming (FLOPS ’02) (Aizu, Japan) (Lecture Notes in Computer Science). Springer-Verlag, New York, NY, USA, 228–244. 3-540-45788-7_14

[49]

Norman Ramsey. 1990. Concurrent programming in ML. Technical Report CS-TR-262-90. Department of Computer Science, Princeton University.

[50]

Norman Ramsey and Simon Peyton Jones. 2000. Featherweight concurrency in a portable assembly language. (Nov. 2000). https: //www.cs.tufts.edu/~nr/pubs/c--con.pdf

[51]

Keith Randall. 2013. Contiguous Stacks in Go. golang.org. Retrieved April 4, 2020 from http://golang.org/s/contigstacks

[52]

John Reppy. 2002. Optimizing nested loops using local CPS conversion. Higher-order and Symbolic Computation 15 (2002), 161–180.

Digital Library

[53]

John Reppy, Claudio Russo, and Yingqi Xiao. 2009. Parallel Concurrent ML. In Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming ICFP ’09 (Edinburgh, Scotland, UK). Association for Computing Machinery, New York, NY, USA, 257–268.

Digital Library

[54]

John H. Reppy. 1991. CML: A higher-order concurrent language. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’91) (Toronto, Ontario, Canada). Association for Computing Machinery, New York, NY, USA, 293–305.

Digital Library

[55]

John H. Reppy. 1999. Concurrent Programming in ML. Cambridge University Press, Cambridge, UK.

Digital Library

[56]

John C. Reynolds. 1993. The discoveries of continuations. Lisp and Symbolic Computation 6, 3 (1993), 233–247. BF01019459

Digital Library

[57]

Zhong Shao and Andrew W. Appel. 1994. Space-efficient Closure Representations. SIGPLAN Lisp Pointers VII, 3 (July 1994), 150–161.

Digital Library

[58]

Zhong Shao and Andrew W. Appel. 2000. Efficient and safe-for-space closure conversion. ACM Transactions on Programming Languages and Systems 22, 1 (2000), 129–161.

Digital Library

[59]

K. C. Sivaramakrishnan, Lukasz Ziarek, and Suresh Jagannathan. 2014. MultiMLton: A multicore-aware runtime for Standard ML. Journal of Functional Programming 24 (Nov. 2014), 613–674. Issue 6.

[60]

Darko Stefanovic and J. Eliot B. Moss. 1994. Characterization of Object Behaviour in Standard ML of New Jersey. In Conference record of the 1994 ACM Conference on Lisp and Functional Programming (Orlando, Florida, USA). Association for Computing Machinery, New York, NY, USA, 43–54.

Digital Library

[61]

Yngve Sundblad. 1971. The Ackermann function. a theoretical, computational, and formula manipulative study. BIT Numerical Mathematics 11, 1 (March 1971), 107–119.

[62]

Mitchell Wand. 1980. Continuation-based multiprocessing. In Conference Record of the 1980 ACM Conference on Lisp and Functional Programming (Stanford University, CA, USA). Association for Computing Machinery, New York, NY, USA, 19–28. 800087.802786

Digital Library

Cited By

Ma CGe ZLee EZhang Y(2024)Lexical Effect Handlers, DirectlyProceedings of the ACM on Programming Languages10.1145/36897708:OOPSLA2(1670-1698)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689770
Pham COdersky MRacordon DZendra O(2024)Stack-Copying Delimited Continuations for Scala NativeProceedings of the 19th ACM International Workshop on Implementation, Compilation, Optimization of OO Languages, Programs and Systems10.1145/3679005.3685979(2-13)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3679005.3685979
Elsman M(2024)Explicit Effects and Effect Constraints in ReMLProceedings of the ACM on Programming Languages10.1145/36329218:POPL(2370-2394)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632921
Show More Cited By

Index Terms

From folklore to fact: comparing implementations of stacks and continuations
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Runtime environments
    2. General programming languages
      1. Language features
        Concurrent programming structures
        Procedures, functions and subroutines
        Recursion
      2. Language types
        Concurrent programming languages
        Functional languages
        Parallel programming languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Multithreading

Recommendations

Threads Yield Continuations

Just as a traditional continuation represents the rest of a computation from a given point in the computation, a subcontinuation represents the rest of a subcomputation from a given point in the subcomputation. Subcontinuations are more expressive than ...
The anatomy of a loop: a story of scope and control
Proceedings of the tenth ACM SIGPLAN international conference on Functional programming

Writing loops with tail-recursive function calls is the equivalent of writing them with goto's. Given that loop packages for Lisp-family languages have been around for over 20 years, it is striking that none have had much success in the Scheme world. I ...
Compiling with continuations, continued
Proceedings of the ICFP '07 conference

We present a series of CPS-based intermediate languages suitable for functional language compilation, arguing that they have practical benefits over direct-style languages based on A-normal form (ANF) or monads. Inlining of functions demonstrates the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2020

1174 pages

ISBN:9781450376136

DOI:10.1145/3385412

General Chair:
Alastair F. Donaldson
Imperial College London, UK
,
Program Chair:
Emina Torlak
University of Washington, USA

Copyright © 2020 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

PLDI '20

Sponsor:

SIGPLAN

PLDI '20: 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation

June 15 - 20, 2020

London, UK

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
2,358
Total Downloads

Downloads (Last 12 months)328
Downloads (Last 6 weeks)41

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ma CGe ZLee EZhang Y(2024)Lexical Effect Handlers, DirectlyProceedings of the ACM on Programming Languages10.1145/36897708:OOPSLA2(1670-1698)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689770
Pham COdersky MRacordon DZendra O(2024)Stack-Copying Delimited Continuations for Scala NativeProceedings of the 19th ACM International Workshop on Implementation, Compilation, Optimization of OO Languages, Programs and Systems10.1145/3679005.3685979(2-13)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3679005.3685979
Elsman M(2024)Explicit Effects and Effect Constraints in ReMLProceedings of the ACM on Programming Languages10.1145/36329218:POPL(2370-2394)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632921
Müller MSchuster PStarup JOstermann KBrachthäuser J(2023)From Capabilities to Regions: Enabling Efficient Compilation of Lexical Effect HandlersProceedings of the ACM on Programming Languages10.1145/36228317:OOPSLA2(941-970)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622831
Elsman MHenriksen T(2023)Parallelism in a Region Inference ContextProceedings of the ACM on Programming Languages10.1145/35912567:PLDI(884-906)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591256
Müller MSchuster PBrachthäuser JOstermann K(2023)Back to Direct Style: Typed and TightProceedings of the ACM on Programming Languages10.1145/35860567:OOPSLA1(848-875)Online publication date: 6-Apr-2023
https://dl.acm.org/doi/10.1145/3586056
Xie NLeijen D(2021)Generalized evidence passing for effect handlers: efficient compilation of effect handlers to CProceedings of the ACM on Programming Languages10.1145/34735765:ICFP(1-30)Online publication date: 19-Aug-2021
https://dl.acm.org/doi/10.1145/3473576
Sivaramakrishnan KDolan SWhite LKelly TJaffer SMadhavapeddy AFreund SYahav E(2021)Retrofitting effect handlers onto OCamlProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454039(206-221)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454039
Farvardin KReppy J(2020)A New Backend for Standard ML of New JerseyProceedings of the 32nd Symposium on Implementation and Application of Functional Languages10.1145/3462172.3462191(55-66)Online publication date: 2-Sep-2020
https://dl.acm.org/doi/10.1145/3462172.3462191
Hillerström DLindley SLongley J(2020)Effects for efficiency: asymptotic speedup with first-class controlProceedings of the ACM on Programming Languages10.1145/34089824:ICFP(1-29)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3408982

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents