使用Rust arena关闭一个三年之久的issue

# 使用 Rust arena 关闭一个三年之久的 issue 来源：https://giacomocavalieri.me/writing/gleam-rust-arenas 我是用 Rust 编写的小巧友好函数式编程语言 [Gleam](https://gleam.run/) 核心团队的一员。不久前，我遇到了一个三年之久的 [issue](https://github.com/gleam-lang/gleam/issues/2251)，它提出了如何使用 arena 来让语言的美观打印器更快。这个 issue 的结尾有点不祥： > *“这将是一份相当漫长的手工活。”* 听起来可真“棒”。我发现处理那些无聊且重复的工作其实挺有趣的，可以关掉大脑，只管敲键盘就行 ^llms（脚注见原文）。经过几天的仔细查找替换，以及一个 `+2963/−1032` 的 [pull request](https://github.com/gleam-lang/gleam/pull/5824)，我成功让 Gleam 格式化器变得更快，同时峰值内存使用也下降了整整 10%！ ## 问题是什么？ 如 issue 所指，Gleam 的美观打印器基于递归数据结构 `Document`。下面是 Gleam 所用的简化版本： ```rust pub enum Document<'string> { /// 将按原样打印的字面字符串。 String(&'string str), /// 一个可能的分行点，如果呈现的文档 /// 任何一行过长，可以在此处断开。 Break { /// 如果断开则渲染的字符串 broken: &'string str, /// 如果未断开则渲染的字符串 unbroken: &'string str, }, /// 可以沿其 `Break` 断开的文档。 Group(Vec<Document<'string>>), /// 如果此文档被断开，则将其嵌套增加一定量。 Nest(Box<Document<'string>>), // …以及许多其他变体… } ``` 这允许我们描述一段代码应该如何呈现，以及如果代码行超过行长度限制，美观打印器可以如何断开它。例如，下面是一个列表的表示： ```rust Group(vec![ String("["), Nest(Box::new(Break { broken: "", unbroken: "" })), String("1"), Nest(Box::new(Break { broken: "," , unbroken: ", " })), String("2"), Break { broken: "," , unbroken: "" }, String("]") ]) ``` 这意味着格式化器可以选择从不断开任何点来呈现列表，或者（如果当前行放不下）在给定的断开点处断开：^how‑this‑works（脚注见原文） ```rust // 无任何 `Break` 被断开时渲染为… [1, 2] // …或者沿 `Break` 断开渲染为！ [ 1, 2, ] ``` 由于某些 `Document` 变体（如 `Nest`）可以容纳其他文档，它们必须在堆上装箱。而大量的时间可能就花在了这上面！ ## Arenas 如果我们改用引用指向其他文档呢？`Document` 枚举需要一些更新。我们需要一个新的生命周期来表示这些引用： ```rust pub enum Document<'doc, 'string> { - Nest(Box<Document<'string>>), + Nest(&'doc Self), // …以及其他变体… } ``` 如果你在 Rust 中使用过引用，你会知道处理生命周期有时会有些麻烦。但使用 arena 可以让事情变得简单得多。在我的例子中，我决定使用 [`typed_arena`](https://docs.rs/typed-arena/latest/typed_arena/) crate。它的 API 非常直接：你可以在 arena 上 `alloc` 新东西，并获得一个引用。基本上就是这样！只要 arena 存活，你就可以使用其中的数据；当 arena 离开作用域并被丢弃时，所有数据也会随之丢弃。 ```rust let arena = Arena::new(); let comma_break = arena.alloc(Break { broken: ",", unbroken: ", " }); let nested_break = arena.alloc(Nest(comma_break)); // …然后渲染文档等…… ``` 借用检查器会确保我们不会在 arena 被丢弃后引用其中的数据： ```rust pub fn alloc(&self, value: T) -> &mut T // ^ ^^^^ // 分配在 arena 中的值的引用不能比它活得久！ ``` 另一个好处是，我们可以缓存许多在整个代码中重复的文档，而不必每次都分配一个。例如，所有语言关键字的文档 `String("fn")`、`String("pub")`、`String("type")`；或者用于分隔列表项的逗号：`Break { unbroken: ", ", broken: "," }`。实际上有[数百个小文档](https://github.com/gleam-lang/gleam/pull/5824/changes#diff-fd77bddd869b2a4e981c876948b9c61e195184ef23a2becbc4ac023aed51f920R590)只分配一次，而不是不断装箱。 ## 结果 尽管 arena 使用起来很方便，但更改大量代码以开始使用它仍需要一些体力活：以前只需要 `Box::new` 的代码，现在需要额外接受一个 arena 参数，用于分配数据： ```rust const comma_break = Break { broken: ",", unbroken: ", " }; pub fn format_list( + arena: &'doc Arena<Document<'doc, 'string>>, items: Vec<Document<'string>>, ) -> Document<'string> { let comma = - Nest(Box::new(comma_break)); + arena.alloc(Nest(comma_break)); Group(vec![ String("["), items .iter() .map(|item| - Nest(Box::new(format_expression(item))) + Nest(format_expression(arena, item)) ) .intersperse(comma) .collect(), String("]"), ]) } ``` 最终的结果比我预想的要好得多，单是美观打印器就获得了巨大的加速。格式化一个真实的 Gleam 项目（如 [`squirrel`](https://github.com/giacomocavalieri/squirrel)）的时间从 13ms 降到了 9.8ms——*快了 24%！* 格式化只是运行 `gleam format` 的一部分，我们首先需要读取并解析项目的源代码。即便如此，实际的改进也是可察觉的：运行 `gleam format` 快了 13%。峰值内存占用也从 8.4MB 降到了 7.6MB。 事实证明，减少在堆上分配的时间可以让代码更快、更省内存，而 Rust 中的 arena 是实现这一目标的极好方式。 --- ^how‑this‑works：美观打印算法本身相当迷人，如果你好奇它是如何工作的，可以查阅《Strictly Pretty》论文。我觉得它读起来很棒，Gleam 的美观打印器正是基于它！ ^llms：这也是我如此厌恶 LLM 的原因之一，你不会看到我使用它们：我喜欢自己打字和思考，谢谢！