Optimizing Layout Of Recursive Datatypes with Marmoset

[vidsinghal]

Title

Optimizing Layout Of Recursive Datatypes with Marmoset

Abstract

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 Gibbon’s baseline approach, as well
as MLton, a Standard ML compiler that uses traditional pointer-heavy representations.

Bio

Vidhush Singhal is a 3rd year Ph.D. student advised by Ryan Newton. His interests like in compilers, compiler optimizations and programming languages.