# Speeding up the Gleam formatter with Rust arenas

Giacomo Cavalieri, on the core team of [Gleam](https://gleam.run/) (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|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:

```rust
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:

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

Nodes are allocated with the [`typed_arena`](https://docs.rs/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.