一个更快的 Rust 内存块分配器

# 一个更快的 Rust bump 分配器 源地址：https://owen.cafe/posts/stumpalo/ [](https://codeberg.org/414owen/stumpalo)[](https://docs.rs/stumpalo/)[](https://crates.io/crates/stumpalo) 向 stumpalo 问好。 Stumpalo 是一个 bump 分配器。 Stumpalo 支持作用域栈。 Stumpalo 极速无比。 Stumpalo 有一个仓促创作的 logo。 Stumpalo 的 logo 叫做 stumpy： stumpy，logo 图案 ## \#速度 (https://owen.cafe/posts/stumpalo/#speed) 你使用 bump 分配器，大概是因为你追求极致的分配吞吐量。 让我们看看 stumpalo 与其他库相比有多快。 操作 | stumpalo | blink | bumpalo --- | --- | --- | --- alloc\_u8 | ✅ 1\.00x | 🔴 2\.14x | 🟠 1\.54x alloc\_u16 | ✅ 1\.00x | 🔴 2\.46x | 🟥 2\.54x alloc\_u32 | ✅ 1\.00x | 🟥 3\.36x | 🟥 3\.34x alloc\_u64 | ✅ 1\.00x | 🟥 3\.35x | 🟥 3\.34x alloc\_u128 | ✅ 1\.00x | 🟡 1\.19x | 🟡 1\.18x alloc\_multiple\_u8 | ✅ 1\.00x | 🔴 1\.82x | 🔴 1\.85x alloc\_multiple\_u16 | ✅ 1\.00x | 🔴 2\.30x | 🔴 2\.34x alloc\_multiple\_u32 | ✅ 1\.00x | 🟥 3\.12x | 🟥 3\.14x alloc\_multiple\_u64 | ✅ 1\.00x | 🟥 3\.23x | 🟥 3\.25x alloc\_multiple\_u128 | ✅ 1\.00x | 🟥 2\.70x | 🟥 2\.61x alloc\_array\_u8\_8 | ✅ 1\.00x | 🔴 1\.99x | 🔴 2\.11x alloc\_array\_u8\_32 | ✅ 1\.00x | 🟢 1\.15x | 🟡 1\.20x alloc\_array\_u8\_64 | ✅ 1\.00x | 🟠 1\.55x | 🟠 1\.59x alloc\_array\_u8\_128 | ✅ 1\.00x | 🟡 1\.30x | 🟠 1\.50x alloc\_slice\_u8\_8 | 🟢 1\.11x | 🟡 1\.27x | ✅ 1\.00x alloc\_slice\_u8\_32 | 🟢 1\.06x | ✅ 1\.00x | 🟢 1\.08x alloc\_slice\_u8\_64 | ✅ 1\.05x | ✅ 1\.00x | 🟢 1\.09x alloc\_slice\_u8\_128 | ✅ 1\.00x | 🟢 1\.06x | ✅ 1\.04x alloc\_slice\_u16\_8 | ✅ 1\.00x | 🟡 1\.33x | 🟡 1\.16x alloc\_slice\_u16\_32 | ✅ 1\.00x | 🟢 1\.14x | 🟢 1\.11x alloc\_slice\_u16\_64 | ✅ 1\.00x | 🟢 1\.14x | 🟢 1\.10x alloc\_slice\_u16\_128 | ✅ 1\.04x | ✅ 1\.00x | ✅ 1\.02x alloc\_slice\_u32\_8 | ✅ 1\.00x | 🟢 1\.14x | 🟢 1\.09x alloc\_slice\_u32\_32 | ✅ 1\.00x | 🟢 1\.14x | 🟢 1\.10x alloc\_slice\_u32\_64 | ✅ 1\.05x | ✅ 1\.00x | 🟢 1\.06x alloc\_slice\_u32\_128 | 🟢 1\.09x | ✅ 1\.00x | 🟢 1\.13x alloc\_slice\_u64\_8 | ✅ 1\.00x | 🟡 1\.25x | 🟢 1\.11x alloc\_slice\_u64\_32 | ✅ 1\.04x | ✅ 1\.00x | ✅ 1\.02x alloc\_slice\_u64\_64 | 🟢 1\.08x | ✅ 1\.00x | 🟢 1\.10x alloc\_slice\_u64\_128 | 🟢 1\.07x | ✅ 1\.00x | 🟢 1\.08x alloc\_slice\_u128\_8 | ✅ 1\.00x | 🟢 1\.12x | 🟢 1\.11x alloc\_slice\_u128\_32 | 🟢 1\.08x | ✅ 1\.00x | 🟢 1\.12x alloc\_slice\_u128\_64 | 🟢 1\.07x | ✅ 1\.00x | 🟢 1\.08x alloc\_slice\_u128\_128 | ✅ 1\.03x | ✅ 1\.00x | ✅ 1\.04x alloc\_struct\_13 | ✅ 1\.00x | 🟠 1\.55x | 🟠 1\.39x alloc\_struct\_24 | ✅ 1\.00x | 🔴 1\.94x | 🔴 1\.97x alloc\_struct\_26 | ✅ 1\.00x | 🟠 1\.56x | 🟠 1\.52x alloc\_struct\_30 | ✅ 1\.00x | 🟠 1\.54x | 🟠 1\.45x alloc\_struct\_32 | ✅ 1\.00x | 🟠 1\.35x | 🟠 1\.40x alloc\_struct\_64 | ✅ 1\.00x | 🟠 1\.44x | 🟠 1\.48x alloc\_struct\_96 | ✅ 1\.00x | 🟢 1\.13x | 🟡 1\.18x alloc\_struct\_128 | ✅ 1\.00x | 🟡 1\.33x | 🟡 1\.17x alloc\_struct\_192 | ✅ 1\.02x | ✅ 1\.00x | 🟢 1\.09x alloc\_struct\_256 | ✅ 1\.00x | 🟡 1\.16x | ✅ 1\.01x alloc\_struct\_512 | 🟢 1\.06x | ✅ 1\.00x | ✅ 1\.02x alloc\_struct\_1k | ✅ 1\.00x | 🟢 1\.05x | ✅ 1\.01x alloc\_str\_8 | 🟢 1\.11x | ✅ 1\.05x | ✅ 1\.00x alloc\_str\_16 | 🟢 1\.07x | ✅ 1\.02x | ✅ 1\.00x alloc\_str\_32 | ✅ 1\.04x | ✅ 1\.00x | 🟢 1\.07x alloc\_str\_40 | ✅ 1\.00x | 🟢 1\.08x | 🟢 1\.06x alloc\_str\_48 | ✅ 1\.00x | ✅ 1\.03x | 🟢 1\.06x alloc\_str\_64 | ✅ 1\.00x | ✅ 1\.04x | 🟢 1\.06x alloc\_str\_72 | ✅ 1\.04x | ✅ 1\.00x | 🟢 1\.07x alloc\_str\_80 | ✅ 1\.03x | ✅ 1\.00x | 🟢 1\.07x alloc\_str\_128 | ✅ 1\.00x | 🟢 1\.11x | 🟢 1\.08x alloc\_slice\_lit\_u8\_8 | ✅ 1\.00x | 🔴 2\.47x | 🔴 2\.23x alloc\_slice\_lit\_u8\_32 | ✅ 1\.00x | 🔴 1\.83x | 🟠 1\.71x alloc\_slice\_lit\_u8\_64 | ✅ 1\.00x | 🟡 1\.34x | 🟠 1\.42x alloc\_slice\_lit\_u8\_128 | ✅ 1\.00x | 🟡 1\.31x | 🟡 1\.31x alloc\_str\_lit\_8 | ✅ 1\.00x | 🔴 2\.02x | 🔴 1\.82x alloc\_str\_lit\_16 | ✅ 1\.00x | 🔴 1\.78x | 🟠 1\.60x alloc\_str\_lit\_32 | ✅ 1\.00x | 🟠 1\.51x | 🟠 1\.42x alloc\_str\_lit\_40 | ✅ 1\.00x | 🔴 1\.76x | 🔴 1\.93x alloc\_str\_lit\_48 | ✅ 1\.00x | 🟠 1\.74x | 🔴 1\.82x alloc\_str\_lit\_64 | ✅ 1\.00x | 🔴 1\.75x | 🟠 1\.69x alloc\_str\_lit\_72 | ✅ 1\.00x | 🟠 1\.53x | 🟠 1\.61x alloc\_str\_lit\_80 | ✅ 1\.00x | 🟠 1\.54x | 🟠 1\.63x alloc\_str\_lit\_128 | ✅ 1\.00x | 🟠 1\.36x | 🟠 1\.35x clear | ✅ 1\.00x | ✅ 1\.04x | ✅ 1\.04x clear\_and\_reuse | ✅ 1\.00x | 🟥 3\.35x | 🟥 3\.35x 基准测试机器：AMD Ryzen 3900x，Arch Linux，内核 7\.0\.3 ### \#速度从何而来 (https://owen.cafe/posts/stumpalo/#where-does-the-speed-come-from) 在 arena 分配器中，快速路径至关重要。快速路径需要检查当前 chunk 是否还有空间，如果有则在当前 chunk 中分配值，否则跳转到慢速路径。 #### \#利用更多信息 (https://owen.cafe/posts/stumpalo/#using-more-information) Rustc / LLVM 能够消除条件为编译期已知表达式的 if/else 语句。 不同类型在编译期有不同的可用信息，例如对齐方式和大小。当这些信息可用时，stumpalo 会结合当前硬件的相关信息加以利用，在溢出/下溢不可能发生的情况下省略相关检查。 通常，stumpalo 的快速路径只包含一个条件分支，最少只需六条指令。 #### \#减少间接层次 (https://owen.cafe/posts/stumpalo/#less-indirection) stumpalo 的 arena 直接持有指向 chunk 顶部和底部的指针。其他库则持有一个指向 chunk 的指针，chunk 的头部再存放指向顶部的指针。stumpalo 读取顶部指针时少了一层间接寻址。 #### \#示例 (https://owen.cafe/posts/stumpalo/#example) 以下函数： `` fn alloc_u32(a: &mut Arena, n: u32) -> &mut u32 { a.alloc(n) } `` 会被编译成如下快速路径： `` alloc_u32: mov rcx, qword ptr [rdi] and rcx, -4 lea rax, [rcx - 4] cmp rax, qword ptr [rdi + 8] jb example::ArenaRef::alloc_slow_with::h903e68372b5b408b mov dword ptr [rcx - 4], esi mov qword ptr [rdi], rax ret `` 步骤如下： 1. 加载顶部指针 2. 将顶部指针向下对齐到对齐量（4）的倍数 3. 从顶部减去大小（4） 4. 将顶部与底部进行比较 5. 如果更小，则尾调用慢速路径 6. 将值写入 chunk 7. 存储新的顶部指针 8. 返回 如果连续进行多次分配，则第一条指令（加载顶部）可以省略，慢速路径的桩代码会展开以更新寄存器。 这只是一个较简单的例子，但 stumpalo 在各种情况下都能生成精简、高效的代码。 ## \#作用域栈 (https://owen.cafe/posts/stumpalo/#scoped-stacks) 作用域栈允许你临时使用 arena，并在使用完毕后将其恢复到之前的状态。 这可以用作一种临时缓冲区。在作用域结束后继续使用 arena，会复用该临时缓冲区所占用的分配空间。 如果你在使用 bump 分配器，那你大概喜欢摊销分配开销。何不把摊销的对象也摊销一下？我头都晕了。 `` let mut arena = Arena::new(); // 如果需要在内层作用域返回后，继续在外层作用域使用其中的引用， // 则需要这一步。否则直接在 arena 上调用 `with_scope` 即可。 let arena = arena.as_arena_ref_mut(); let a = arena.alloc(1u32); arena.with_scope(|scope: &mut ArenaRef| { let temporary = scope.alloc(2u32); scope.with_scope(|scope: &mut ArenaRef| { // 哇，作用域可以嵌套。 // 也许某些时候会用到……吧…… }); }); // 作用域返回后，arena 会被重置到之前的位置。 // 为内层作用域分配的 chunk 会被加入空闲链表以供复用。 // 'a' 仍然可以访问 assert_eq!(*a, 1); `` 为了设计出安全的作用域栈 API，付出了大量心血。在 [ui 测试目录](https://codeberg.org/414owen/stumpalo/src/commit/main/tests/ui)中，有针对各种错误用法无法通过编译的测试用例。 --- 感谢阅读，同时感谢 bumpalo——一个我已经用了多年的优秀 bump 分配器。