Speeding up the Gleam formatter with Rust arenas

Giacomo Cavalieri, on the core team of Gleam (a functional language whose compiler is written in Rust), closed a three-year-old issue by rewriting the formatter's pretty printer to use arena allocation. The issue itself flagged the work as "quite a long manual job," and it was: a +2963/-1032 pull request built over a couple of days of find-and-replace. The payoff was a formatter about 24% faster with roughly 10% lower peak memory.

What changed

Gleam's pretty printer builds a recursive Document tree that describes how code should be rendered and where lines may break. Variants that hold child documents — Nest, and others — stored those children in Box, so every nested node was a separate heap allocation:

pub enum Document<'string> {
    String(&'string str),
    Break { broken: &'string str, unbroken: &'string str },
    Group(Vec<Self>),
    Nest(Box<Self>),
    // ...
}

The change swaps the owning Box for a borrowed reference into an arena, which needs a second lifetime on the enum:

Nest(&'doc Self)   // was: Nest(Box<Self>)

Nodes are allocated with the typed_arena crate. arena.alloc(value) returns a reference that the borrow checker won't let outlive the arena, so there is no manual freeing — when the arena is dropped at the end of formatting, the whole Document tree goes with it. A side benefit is caching: the hundreds of tiny repeated documents (keywords like String("fn"), the list-separator comma) get allocated once and referenced everywhere instead of being reboxed on each use.

The cost was ergonomic rather than conceptual. Every function that previously called Box::new now has to take the arena as an extra argument and thread its lifetime through — the reason the diff is large and mechanical.

Numbers

Formatting the real squirrel project dropped from 13ms to 9.8ms in the pretty printer (about 24% faster). Since formatting is only part of gleam format — reading and parsing the source dominates the rest — the end-to-end command improved about 13%. Peak memory went from 8.4MB to 7.6MB. The lesson is unremarkable but easy to forget: cutting heap allocation makes code both faster and lighter.

The pretty-printing algorithm behind all this is from Christian Lindig's "Strictly Pretty" paper, a Wadler-style approach.

Interesting from the discussion

The Lobsters thread turned into a useful compare of the two arena styles. Cavalieri used a reference-handing arena; a commenter pointed out that a handle-handing arena (opaque 16- or 32-bit indices instead of 64-bit references, e.g. compact_arena) would pack the many small nodes more tightly and might extend the memory win. The counter-argument, from the author of a well-known arena survey, is that references are much nicer to pattern-match on: Rust can't match through a Box in a recursive enum, but it can match transparently through references, and a single arena gives the whole tree one consistent lifetime. rustc itself uses the handle style — it interns types and lowers the AST into arena-allocated HIR with HirId handles rather than references, precisely because interning makes deduplication and caching cheap. This is the same index-not-pointer tradeoff that arena-allocation and safe-gc both lean on.