Closing a three-year-old issue using Rust arenashome<br>writing<br>Closing a three-year-old issue using Rust arenas

I am part of the core team working on Gleam, a small,<br>friendly functional programming language written in Rust.<br>A little while ago I ran into a three-year-old<br>issue suggesting how we could<br>start using arenas to make the language's pretty printer faster.<br>Quite ominously the issue ends with:<br>"This would be quite a long manual job."

That sounds grand. I find it actually quite fun to tackle those boring and<br>repetitive jobs where I can turn my brain off and just punch at a keyboard.<br>^llms<br>After a couple of days of careful find-and-replace and a<br>+2963/-1032 pull request<br>later, I managed to make the Gleam formatter a lot faster, also cutting its peak<br>memory usage by a good 10%!

# What's the problem?<br>As the issue points out, Gleam's pretty printer is based on a recursive data<br>structure, the Document. Here's a slightly simplified version of the one that<br>Gleam uses:<br>pub enum Document {<br>/// A literal string that will be printed<br>/// exactly as it is.<br>String(&'string str),

/// A possible point where the rendered<br>/// document could be broken if any line<br>/// line gets too long.<br>Break {<br>/// The string to render if this is broken<br>broken: &'string str,<br>/// The string to render if this in not broken<br>unbroken: &'string str<br>},

/// A document that can be broken along its<br>/// `Break`s.<br>Group(Vec),

/// If this document is broken, increase its nesting<br>/// by some amount.<br>Nest(Box),

// ...and many more...<br>This allows us to describe how a piece of code should be rendered and how the<br>pretty printer is allowed to break it if it gets too long for the line limit.<br>For example, this is how a list is represented:<br>Group(vec![<br>String("["),<br>Nest(Box::new(Break { broken: "", unbroken: "" })),<br>String("1"),<br>Nest(Box::new(Break { broken: ",", unbroken: ", " })),<br>String("2"),<br>Break { broken: ",", unbroken: "" },<br>String("]")<br>])<br>This means the formatter is allowed to either render the list without ever<br>breaking it, or (if it doesn't fit on the current line) to break it along the<br>given break points:^how-this-works<br>// Rendered with none of the `Break`s broken...<br>[1, 2]

// ...or rendered breaking it along the `Break`s!<br>1,<br>2,<br>Since some Document variants can hold other documents, like Nest does, those<br>will have to be boxed on the heap.<br>And quite a good chunk of time could be spent just doing that!

# Arenas<br>What if instead we could just store references to other documents?<br>The Document enum would need some updating.<br>We need a new lifetime for those references:<br>pub enum Document {<br>- Nest(Box),<br>+ Nest(&'doc Self),

// ...and the other variants...<br>If you've worked with references in Rust you know it can sometimes be quite a<br>bit of a pain to deal with lifetimes. But using an arena can make it a lot<br>nicer.<br>In our case I've decided to use the<br>typed_arena crate.<br>The API is pretty straightforward: you can alloc new things on the arena, and<br>get a reference back. That's basically it!<br>As long as the arena is alive, you will be able to use the data in it; and when<br>the arena gets out of scope and is dropped, all the data will be dropped with<br>it.<br>let arena = Arena::new();

let comma_break = arena.alloc(Break {<br>broken: ",", unbroken: ", "<br>});

let nested_break = arena.alloc(Nest(comma_break));

// ...render the docs or whatever...<br>The borrow checker will make sure that we can't reference data in the arena once<br>the arena is dropped:<br>pub fn alloc(&self, value: T) -> &mut T<br>// ^ ^^^^<br>// The reference to the value allocated in<br>// the arena can't outlive it!<br>Another nice benefit is that we can cache a lot of documents that are repeated<br>throughout the code without having to allocate one every single time.<br>For example the documents with all the language's keywords String("fn"),<br>String("pub"), String("type"); or the comma we use to separate list items:<br>Break { unbroken: ", ", broken: "," }.<br>There's literally hundreds of little documents<br>that are allocated just once rather than being constantly boxed.

# The result<br>As nice as the arena is to use, changing a big chunk of code to start using it<br>required a bit of grunt work: all the bits of code that previously were fine<br>with just Box::new, now need to take the arena where the data will be<br>allocated as an additional argument:<br>const comma_break = Break { broken: ",", unbroken: ", ") };

pub fn format_list(<br>+ arena: &'doc arena : Arena>,<br>items: Vec<br>) -> Document {<br>let comma =<br>- Nest(Box::new(comma_break));<br>+ arena.alloc(Nest(comma_break));

Group(vec![<br>String("["),<br>items<br>.iter()<br>.map(|item|<br>- Nest(Box::new(format_expression(item)))<br>+ Nest(format_expression(arena, item))<br>.intersperse(comma)<br>.collect(),<br>String("]")<br>])<br>In the end, the outcome was much better than I anticipated, the pretty printer<br>alone got a huge speedup.<br>The time spent formatting a real Gleam project like<br>squirrel went from 13ms to<br>9,8ms. That's 24% faster!<br>The formatting is just a fraction of what goes into running gleam format, we<br>first have to read...