Optimizing Layout of Recursive Datatypes with Marmoset: Or, Algorithms + Data Layouts = Efficient Programs

Vidush Singhal, Chaitanya Koparkar, Joseph Zullo, Artem Pelenitsyn, Michael Vollmer, Mike Rainey, Ryan R. Newton, and Milind Kulkarni

ECOOP 2024 · European Conference on Object-Oriented Programming · October 2024 · pp. 38:1-38:28

Acceptance rate 42%

Abstract

While programmers know that memory representation of data structures can have significant effects on performance, compiler support to optimize the layout of those structures is an under-explored field. Prior work has optimized the layout of individual, non-recursive structures without considering how collections of those objects in linked or recursive data structures are laid out. This work introduces Marmoset, a compiler that optimizes the layouts of algebraic datatypes, with a special focus on producing highly optimized, packed data layouts where recursive structures can be traversed with minimal pointer chasing. Marmoset performs an analysis of how a recursive ADT is used across functions to choose a global layout that promotes simple, strided access for that ADT in memory. It does so by building and solving a constraint system to minimize an abstract cost model, yielding a predicted efficient layout for the ADT. Marmoset then builds on top of Gibbon, a prior compiler for packed, mostly-serial representations, to synthesize optimized ADTs. We show experimentally that Marmoset is able to choose optimal layouts across a series of microbenchmarks and case studies, outperforming both Gibbon’s baseline approach, as well as MLton, a Standard ML compiler that uses traditional pointer-heavy representations.

BibTeX

@inproceedings{singhal24ecoop,
  author    = {Vidush Singhal and Chaitanya Koparkar and Joseph Zullo and Artem Pelenitsyn and Michael Vollmer and Mike Rainey and Ryan R. Newton and Milind Kulkarni},
  title     = {Optimizing Layout of Recursive Datatypes with Marmoset: Or, Algorithms + Data Layouts = Efficient Programs},
  booktitle = {Proceedings of the European Conference on Object-Oriented Programming (ECOOP)},
  pages     = {38:1--38:28},
  year      = {2024},
  month     = oct,
  doi       = {10.4230/LIPICS.ECOOP.2024.38}
}

Group members