Optimizing Layout of Recursive Datatypes with Marmoset
<|reference_start|>Optimizing Layout of Recursive Datatypes with Marmoset: While programmers know that the low-level 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 Gibbons baseline approach, as well as MLton, a Standard ML compiler that uses traditional pointer-heavy representations.<|reference_end|>
@article{singhal2024optimizing,
    title={Optimizing Layout of Recursive Datatypes with Marmoset},
    author={Vidush Singhal, Chaitanya Koparkar, Joseph Zullo, Artem Pelenitsyn,
  Michael Vollmer, Mike Rainey, Ryan Newton, Milind Kulkarni},
    journal={European Conference on Object Oriented Programming 2024},
    year={2024},
    doi={10.4230/LIPIcs.ECOOP.2024.38},
    archivePrefix={arXiv},
    eprint={2405.17590},
    primaryClass={cs.PL cs.PF}
}