License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECOOP.2022.15
URN: urn:nbn:de:0030-drops-162430
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16243/
Go to the corresponding LIPIcs Volume Portal

Xhebraj, Anxhelo ; Bračevac, Oliver ; Wei, Guannan ; Rompf, Tiark

What If We Don't Pop the Stack? The Return of 2nd-Class Values

pdf-format:
LIPIcs-ECOOP-2022-15.pdf (1 MB)

Abstract

Using a stack for managing the local state of procedures as popularized by Algol is a simple but effective way to achieve a primitive form of automatic memory management. Hence, the call stack remains the backbone of most programming language runtimes to the present day. However, the appealing simplicity of the call stack model comes at the price of strictly enforced limitations: since every function return pops the stack, it is difficult to return stack-allocated data from a callee upwards to its caller - especially variable-size data such as closures.
This paper proposes a solution by introducing a small tweak to the usual stack semantics. We design a type system that tracks the underlying storage mode of values, and when a function returns a stack-allocated value, we just don't pop the stack! Instead, the stack frame is de-allocated together with a parent the next time a heap-allocated value or primitive is returned. We identify a range of use cases where this delayed-popping strategy is beneficial, ranging from closures to trait objects to other types of variable-size data. Our evaluation shows that this execution model reduces heap and GC pressure and recovers spatial locality of programs improving execution time between 10% and 25% with respect to standard execution.

BibTeX - Entry

@InProceedings{xhebraj_et_al:LIPIcs.ECOOP.2022.15,
  author =	{Xhebraj, Anxhelo and Bra\v{c}evac, Oliver and Wei, Guannan and Rompf, Tiark},
  title =	{{What If We Don't Pop the Stack? The Return of 2nd-Class Values}},
  booktitle =	{36th European Conference on Object-Oriented Programming (ECOOP 2022)},
  pages =	{15:1--15:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-225-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{222},
  editor =	{Ali, Karim and Vitek, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16243},
  URN =		{urn:nbn:de:0030-drops-162430},
  doi =		{10.4230/LIPIcs.ECOOP.2022.15},
  annote =	{Keywords: Call stack, closures, stack allocation, memory management, 2nd-class values, capabilities, effects}
}

Keywords: Call stack, closures, stack allocation, memory management, 2nd-class values, capabilities, effects
Collection: 36th European Conference on Object-Oriented Programming (ECOOP 2022)
Issue Date: 2022
Date of publication: 23.06.2022
Supplementary Material: Software (ECOOP 2022 Artifact Evaluation approved artifact): https://doi.org/10.4230/DARTS.8.2.26

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI