A faster bump allocator for rust

# A faster bump allocator for rust Source: [https://owen.cafe/posts/stumpalo/](https://owen.cafe/posts/stumpalo/) [](https://codeberg.org/414owen/stumpalo)[](https://docs.rs/stumpalo/)[](https://crates.io/crates/stumpalo) Say hello to stumpalo\. Stumpalo is a bump allocator\. Stumpalo has scoped stack support\. Stumpalo is extremely fast\. Stumpalo has a logo, created very hastily\. Stumpalo’s logo is stumpy:  ## [\#Speed](https://owen.cafe/posts/stumpalo/#speed) You’re probably using a bump allocator because you want raw allocation throughput\. Let’s see how fast stumpalo is, compared to other libraries\. operationstumpaloblinkbumpaloalloc\_u8✅ 1\.00x🔴 2\.14x🟠 1\.54xalloc\_u16✅ 1\.00x🔴 2\.46x🟥 2\.54xalloc\_u32✅ 1\.00x🟥 3\.36x🟥 3\.34xalloc\_u64✅ 1\.00x🟥 3\.35x🟥 3\.34xalloc\_u128✅ 1\.00x🟡 1\.19x🟡 1\.18xalloc\_multiple\_u8✅ 1\.00x🔴 1\.82x🔴 1\.85xalloc\_multiple\_u16✅ 1\.00x🔴 2\.30x🔴 2\.34xalloc\_multiple\_u32✅ 1\.00x🟥 3\.12x🟥 3\.14xalloc\_multiple\_u64✅ 1\.00x🟥 3\.23x🟥 3\.25xalloc\_multiple\_u128✅ 1\.00x🟥 2\.70x🟥 2\.61xalloc\_array\_u8\_8✅ 1\.00x🔴 1\.99x🔴 2\.11xalloc\_array\_u8\_32✅ 1\.00x🟢 1\.15x🟡 1\.20xalloc\_array\_u8\_64✅ 1\.00x🟠 1\.55x🟠 1\.59xalloc\_array\_u8\_128✅ 1\.00x🟡 1\.30x🟠 1\.50xalloc\_slice\_u8\_8🟢 1\.11x🟡 1\.27x✅ 1\.00xalloc\_slice\_u8\_32🟢 1\.06x✅ 1\.00x🟢 1\.08xalloc\_slice\_u8\_64✅ 1\.05x✅ 1\.00x🟢 1\.09xalloc\_slice\_u8\_128✅ 1\.00x🟢 1\.06x✅ 1\.04xalloc\_slice\_u16\_8✅ 1\.00x🟡 1\.33x🟡 1\.16xalloc\_slice\_u16\_32✅ 1\.00x🟢 1\.14x🟢 1\.11xalloc\_slice\_u16\_64✅ 1\.00x🟢 1\.14x🟢 1\.10xalloc\_slice\_u16\_128✅ 1\.04x✅ 1\.00x✅ 1\.02xalloc\_slice\_u32\_8✅ 1\.00x🟢 1\.14x🟢 1\.09xalloc\_slice\_u32\_32✅ 1\.00x🟢 1\.14x🟢 1\.10xalloc\_slice\_u32\_64✅ 1\.05x✅ 1\.00x🟢 1\.06xalloc\_slice\_u32\_128🟢 1\.09x✅ 1\.00x🟢 1\.13xalloc\_slice\_u64\_8✅ 1\.00x🟡 1\.25x🟢 1\.11xalloc\_slice\_u64\_32✅ 1\.04x✅ 1\.00x✅ 1\.02xalloc\_slice\_u64\_64🟢 1\.08x✅ 1\.00x🟢 1\.10xalloc\_slice\_u64\_128🟢 1\.07x✅ 1\.00x🟢 1\.08xalloc\_slice\_u128\_8✅ 1\.00x🟢 1\.12x🟢 1\.11xalloc\_slice\_u128\_32🟢 1\.08x✅ 1\.00x🟢 1\.12xalloc\_slice\_u128\_64🟢 1\.07x✅ 1\.00x🟢 1\.08xalloc\_slice\_u128\_128✅ 1\.03x✅ 1\.00x✅ 1\.04xalloc\_struct\_13✅ 1\.00x🟠 1\.55x🟠 1\.39xalloc\_struct\_24✅ 1\.00x🔴 1\.94x🔴 1\.97xalloc\_struct\_26✅ 1\.00x🟠 1\.56x🟠 1\.52xalloc\_struct\_30✅ 1\.00x🟠 1\.54x🟠 1\.45xalloc\_struct\_32✅ 1\.00x🟠 1\.35x🟠 1\.40xalloc\_struct\_64✅ 1\.00x🟠 1\.44x🟠 1\.48xalloc\_struct\_96✅ 1\.00x🟢 1\.13x🟡 1\.18xalloc\_struct\_128✅ 1\.00x🟡 1\.33x🟡 1\.17xalloc\_struct\_192✅ 1\.02x✅ 1\.00x🟢 1\.09xalloc\_struct\_256✅ 1\.00x🟡 1\.16x✅ 1\.01xalloc\_struct\_512🟢 1\.06x✅ 1\.00x✅ 1\.02xalloc\_struct\_1k✅ 1\.00x🟢 1\.05x✅ 1\.01xalloc\_str\_8🟢 1\.11x✅ 1\.05x✅ 1\.00xalloc\_str\_16🟢 1\.07x✅ 1\.02x✅ 1\.00xalloc\_str\_32✅ 1\.04x✅ 1\.00x🟢 1\.07xalloc\_str\_40✅ 1\.00x🟢 1\.08x🟢 1\.06xalloc\_str\_48✅ 1\.00x✅ 1\.03x🟢 1\.06xalloc\_str\_64✅ 1\.00x✅ 1\.04x🟢 1\.06xalloc\_str\_72✅ 1\.04x✅ 1\.00x🟢 1\.07xalloc\_str\_80✅ 1\.03x✅ 1\.00x🟢 1\.07xalloc\_str\_128✅ 1\.00x🟢 1\.11x🟢 1\.08xalloc\_slice\_lit\_u8\_8✅ 1\.00x🔴 2\.47x🔴 2\.23xalloc\_slice\_lit\_u8\_32✅ 1\.00x🔴 1\.83x🟠 1\.71xalloc\_slice\_lit\_u8\_64✅ 1\.00x🟡 1\.34x🟠 1\.42xalloc\_slice\_lit\_u8\_128✅ 1\.00x🟡 1\.31x🟡 1\.31xalloc\_str\_lit\_8✅ 1\.00x🔴 2\.02x🔴 1\.82xalloc\_str\_lit\_16✅ 1\.00x🔴 1\.78x🟠 1\.60xalloc\_str\_lit\_32✅ 1\.00x🟠 1\.51x🟠 1\.42xalloc\_str\_lit\_40✅ 1\.00x🔴 1\.76x🔴 1\.93xalloc\_str\_lit\_48✅ 1\.00x🟠 1\.74x🔴 1\.82xalloc\_str\_lit\_64✅ 1\.00x🔴 1\.75x🟠 1\.69xalloc\_str\_lit\_72✅ 1\.00x🟠 1\.53x🟠 1\.61xalloc\_str\_lit\_80✅ 1\.00x🟠 1\.54x🟠 1\.63xalloc\_str\_lit\_128✅ 1\.00x🟠 1\.36x🟠 1\.35xclear✅ 1\.00x✅ 1\.04x✅ 1\.04xclear\_and\_reuse✅ 1\.00x🟥 3\.35x🟥 3\.35xBenchmark machine: AMD Ryzen 3900x, Arch Linux, kernel 7\.0\.3 ### [\#Where does the speed come from](https://owen.cafe/posts/stumpalo/#where-does-the-speed-come-from) In an arena allocator, the fast path is everything\. The fast path has to check whether there’s room in the current chunk, if so, allocate the value in the current chunk, and if not, jump to the slow path\. #### [\#Using more information](https://owen.cafe/posts/stumpalo/#using-more-information) Rustc / LLVM is able to erase if/else statements whose conditions are expressions known at compile\-time\. Different types have different information available at compile\-time\. Think alignment and size\. When this information is available, stumpalo uses it, as well as information about the hardware you’re running on, to avoid overflow/underflow checks, when overflow/underflow couldn’t possibly occur anyway\. Generally, stumpalo’s fast\-paths contain a single conditional branch, and as few as six instructions\. #### [\#Less indirection](https://owen.cafe/posts/stumpalo/#less-indirection) A stumpalo arena contains pointers to the top and bottom of the chunk\. Other libraries contain a pointer to a chunk, whose header contains pointers to their top\. Stumpalo goes through one less layer of indirection to read the top\. #### [\#Example](https://owen.cafe/posts/stumpalo/#example) The following function: ``` fn alloc_u32(a: &mut Arena, n: u32) -> &mut u32 { a.alloc(n) } ``` Compiles down to this fast path: ``` 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 ``` That’s: 1. Load the top pointer 2. Round top down to a multiple of alignment \(4\) 3. Subtract size \(4\) from top 4. Compare top against bottom 5. If less, tail call to the slow path 6. Write the value to the chunk 7. Store the new top 8. Return If there are multiple allocations in a row, then the first instruction, loading the top, is avoided\. The stub for the slow path is expanded to update the register\. This is a fairly simple example, but stumpalo produces tiny, fast code across the board\. ## [\#Scoped stacks](https://owen.cafe/posts/stumpalo/#scoped-stacks) Scoped stacks let you use the arena temporarily, and revert it to a previous state once you’re done\. This can be useful as a sort of scratch area\. Using the arena after it’s been used as a scratch area will reuse allocations made for the scratch area\. If you’re using a bump allocator, you probably like amortizing allocations\. How about amortizing the allocations across uses of your allocation amortizer? I’m dizzy\. ``` let mut arena = Arena::new(); // This is necessary if you need to keep references alive from // the outer scope, after the inner scope returns. // Otherwise, just call `with_scope` on the arena directly. 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| { // Wow, you can have stacked scopes. // That might be useful... I guess... }); }); // After a scope returns, the arena is reset to its previous position. // Any chunks allocated for the inner scope are added to a free list for reuse. // 'a' is still accessible assert_eq!(*a, 1); ``` A lot of effort went into coming up with a safe API for scoped stacks\. There are tests that various misuses of scopes fail to compile in the[ui tests directory](https://codeberg.org/414owen/stumpalo/src/commit/main/tests/ui)\. --- Thanks for reading, and thank you to bumpalo, a fantastic bump allocator I’ve been using for years\.