Compiling Tree Transforms to Operate on Packed Representations

When written idiomatically in most programming languages, programs

that traverse and construct trees operate over pointer-based data

structures, using one heap object per-leaf and per-node. This

representation is efficient for random access and shape-changing

modifications, but for traversals, such as compiler passes, that

process most or all of a tree in bulk, it can be inefficient. In this

work we instead compile tree traversals to operate on

pointer-free pre-order serializations of trees. On modern

architectures such programs often run significantly faster than

their pointer-based counterparts, and additionally are directly suited

to storage and transmission without requiring marshaling.

We present a prototype compiler, Gibbon, that compiles a

small first-order, purely functional language sufficient for tree

traversals. The compiler transforms this language into intermediate

representation with explicit pointers into input and output buffers

for packed data. The key compiler technologies include an effect

system for capturing traversal behavior, combined with an algorithm to

insert destination cursors. We evaluate our compiler on tree

transformations over a real-world dataset of source-code syntax trees.

For traversals touching the whole tree, such as maps and folds, packed

data allows speedups of over 2x compared to a highly-optimized

pointer-based baseline.