High-level spectrum of call stack implementations, as a function of the number of pointers used to maintain the structure. Dashed lines separate stack frames. (From Farvardin & Reppy, 2020)
High-level spectrum of call stack implementations, as a function of the number of pointers used to maintain the structure. Dashed lines separate stack frames. (From Farvardin & Reppy, 2020)

Like many fields of expertise, programming language implementation often relies on conventional wisdom. But occasionally, when you trace that assumed knowledge back to its source, it is not actually based on scientific evidence. Such is the case with the implementation of continuations, a mechanism that is fundamental to implementing language features such as concurrency and parallelism, and which can be used to get the most mileage out of the multicore processors now standard on most modern computers.

In “From Folklore to Fact: Comparing Implementations of Stacks and Continuations” UChicago CS PhD student Kavon Farvardin and Professor John Reppy sought to bust the myths and empirically judge six different implementation approaches on the same system. The results provide trustworthy guidance for building future programming language implementations, and their hard work was rewarded with a Distinguished Paper award at the 2020 SIGPLAN Conference on Programming Language Design and Implementation (PLDI). The conference will be held virtually in mid-June.

“The goal of this paper is not only to provide an empirical apples-to-apples, or well-normalized comparison of these different strategies for performance, but also to dive into the deep details of all the trade-offs in choosing one of these strategies or developing your own custom strategy.” Farvardin said. “Our goal wasn't really to say whether one is the best or not; we really intended for this paper to present all the information so that people can make an informed decision.”

The research utilized the Manticore system, developed by Reppy’s group at UChicago in collaboration with Matthew Fluet’s group at the Rochester Institute of Technology. The Manticore system implements an experimental parallel functional programming language, which provided Farvardin and Reppy with a level playing field on which to pit different approaches against each other. A competition of this caliber had never been conducted before, Farvardin said, for one simple reason: it’s difficult.

“Nobody really truly understood what the differences were, because nobody in their right mind would ever want to implement so many different types of call stacks in one compiler’s runtime system,” Farvardin said. “It's a huge pain…it's hard enough to get one full-featured call stack implementation.”

But once set up, the authors could compare performance using several dozen different benchmark programs that test aspects such as recursion, looping, concurrency, and other language mechanisms. While small, these benchmarks are good “torture tests,” Farvardin said, for the seemingly routine tasks that can create bottlenecks in larger programs. 

Over the range of benchmarks tested, there was no definitive winner. Some approaches (closure-based stacks) offer easier implementation at the cost of sequential performance, others (resizing, segmented, and their own hybrid scheme) offered solid performance across different benchmark types with similar implementation overhead. Only one strategy (linked-frame stacks) was discouraged by the authors, who concluded that the hybrid approach is what they would themselves choose if they were rebuilding Manticore from scratch.

“There's no silver bullet, and we didn't really expect there to be any one strategy that's the winner,” Farvardin said. “It's really up to your language and your priorities. We aimed to be the latest and greatest knowledge on the trade-offs in this space, both empirically and in terms of implementation details.”

Related News

More UChicago CS stories from this research area.
UChicago CS News

Concurrency Bug Research by Prof. Shan Lu Receives ASPLOS Influential Paper Award

Mar 29, 2022
UChicago CS News

Overhaul of Standard ML of New Jersey System Wins Special IFL Award

Aug 05, 2021
UChicago CS News

Two UChicago CS PhD Students Receive 2021 Harper Fellowship

Jun 07, 2021
UChicago CS News

Quantum Compiler Co-Created by Robert Rand Named Distinguished Paper at POPL 21

Jan 21, 2021
UChicago CS News

Ravi Chugh Promoted to Associate Professor at UChicago Computer Science

Jan 06, 2021
UChicago CS News

UChicago CS Alums Go On To Exciting Futures in Academia, Industry, and Startups

Nov 24, 2020
UChicago CS News

New Asst. Prof. Robert Rand Writes the Language of Tomorrow’s Quantum Computers

Nov 17, 2020
UChicago CS News

Why TIPP&SEE Works: CANON Lab Research Wins Best Paper at CS Education Conference

Oct 15, 2020
UChicago CS News

PhD Student Yi Ding Receives CRA Computing Innovation Fellowship

Aug 24, 2020
UChicago CS News

Four New Faculty Join UChicago Computer Science for 2020-21

Jul 27, 2020
UChicago CS News

Leading CS Ed Conference Features Five Papers from UChicago CANON Research Group

Mar 25, 2020
UChicago CS News

CS Education Expert Diana Franklin Promoted to Associate Professor

Feb 27, 2020
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube