Arenas

Press for table of Contents

Sometimes you just really need an arena. Sometimes for performance reasons, other times for lifetime-related reasons. In their most basic forms, they're just a vec with some extra guarantees. However, it's those extra guarantees that matter. I've found myself looking for the right kind of arena too many times, so here's an overview of literally everything there is. I think, let me know if I forgot something.

What's an arena?

Very basically, an arena is a way to store your data somewhere without directly going through the system allocator. If you have a lot of small objects which you don't mind to deallocate together instead of individually, this can be a lot faster. You could use a Vec for this. However, if you store data in a vec its address might change all the time.

When the vector grows, its contents move around memory. That's not actually as inefficient as you think, it happens less and less often as the vec grows. The real problem with this moving around is that you can't depend on the address of your elements staying the same. It's common that you want to hold on to those addresses in a datastructure while also adding new objects.

The simplest kind of arena is built to solve that exact problem, by allocating in large chunks, and promising never to deallocate or move those. To grow, such an arena would simply allocate a whole new chunk of memory. However, there are so many more ways to do this which give you arenas with slightly different properties.

properties of arenas

In the table below, I talk about various properties arena do and don't have. Sometimes, you might not need an arena at all. Libraries such as elsa or rpds can help you write efficient datastructures, that are immutable, or provide quick clones because they are mostly based on pointers internally. That could be what you're actually looking for.

In the table, I've abbreviated some things a little, so here is the full explanation:

Type

Some arena implementations only allow you to store a single datatype in them. This can be good for performance, and might make it possible to iterate over the full list of allocations. However, it can be a limitation too. If the arena is supposed to work a little like an alternative to the built-in memory allocator, then you might want to allocate arbitrary elements of mixed types. This makes element iteration harder, since elements aren't stored at well-known offsets in the arena.

Interestingly, bumpalo supports both kinds. By default, the arena is mixed-type, but you can allocate vectors of a single type in their arena.

Requires

This indicates what kind of reference to the arena you need to allocate something in it.

Gives Out, and Deref Key

Some arenas directly give you references, but some are based on indices, and you might even need to have access to the arena to use these indices. "Gives Out" documents what kind of type you get to refer to an allocation. Sometimes it has a 'a lifetime, refering to the fact that it is bound to the lifetime of the arena, or T: 'static, meaning the type given out must be 'static. If no such lifetime is given, the index type is completely free from the arena's lifetime. "Deref Key" documents whether you need access to the arena to use the key, or whether the key directly gives access to the element.

Reuse Memory

Some arena allocators assume you only allocate, never free. That might be what you want, but sometimes it might not be. Most freeing arenas use a linked list of free spots, a freelist, though there are other options like garbage collection (GC), and I found one library that can actually compact itself and shrink.

Note, that for performance reasons, shrinking usually isn't often a very good idea.

Runs Drop

Especially the mixed-type arenas sometimes don't run Drop of stored elements. It's hard to call Drop if you don't know where in the arena elements are stored. This is a problem if you, for example, want to store an Rc in an arena, though there are many more types for which this is a problem.

Iteration

Although an arena isn't a vec, the items are often stored prety much in-order. So this column is about whether the arena supports this. The type behind it indicates whether to iterate you need a reference or mutable reference to the arena.

Collections

A few arena libraries also provide an alternative set of collections like Vec, String, and pointers like Box and Rc.

no_std and no unsafe

These should be pretty obvious.

ABA mitigation

If your arena supports deletions, the arena must be careful that on re-allocation it doesn't accidentally reuse an ID it previously gave to you. If you had still stored that old ID, you could now use it to access a new allocation. Or not, some arenas don't care and let you deal with this.

Concurrent

This documents whether the arena can be used concurrently. For some, I documented whether they require locking.

Dedup

Interners often deduplicate keys, to gain pointer equality. So far I only investigated one library doing this.

Approach

This roughly documentes how the library works.

The others I think mostly make sense.

Note that there are instances where I left a cell blank. That's on some new columns, for which I've not gone through all the crates yet, so I don't have all the data yet. Feel free to help out!

Overview

Ordered by number of downloads, not by what you should use!! That only depends on your situation.

Crate Type Takes Gives Out Idx Size Deref Key Reuse Mem Runs Drop Iteration Collections no_std no unsafe ABA mitigation concurrent dedup Approach Downloads Last Update Version
slab Single &mut usize usize ❌ ✅ compact1 ✅ ✅ & ❌ ✅ ✅ ❌ ❌ ❌ Vec with Freelist
bumpalo Both & &'a mut NonZero<usize> ✅ ❌ ❌ ❌ ✅ ✅ ❌ ❌ ❌ Linked Arena Chunks
sharded-slab Single & usize usize ❌ ✅ freelist ✅ ✅ & ❌ ❌ ❌ ✅ ❌ Linked Arena Chunks
typed-arena Single & &'a mut NonZero<usize> ✅ ❌ ✅ ✅ &mut ❌ ❌ ❌ ❌ ❌ Linked Arena Chunks
slotmap Single &mut K: Key NonZero<u64> ❌ ✅ freelist ✅ ✅ & ❌ ✅ ❌ ✅ ❌ ❌ Vec with Freelist
id-arena Single &mut Id usize+u32 ❌ ❌ ✅ ✅ & ❌ ✅ ✅ ✅ ❌ Indexed Vec
generational-arena Single &mut Index usize+u64 ❌ ✅ freelist ✅ ✅ & ❌ ✅ ✅ ❌ ❌ Vec with Freelist
internment Single & ArenaIntern<'a> usize ✅ ❌ ✅ ❌ ❌ ❌ ❌ 🔒 ✅ Hashset of Boxes
concurrent_arena Single & ArenaArc 2*u32+Arc ✅ ✅ ✅ ❌ ❌ ❌ ❌ ✅ alloc may 🔒 ❌ Reference Counted Buckets
thunderdome Single &mut Index NonZero<u64> ❌ ✅ freelist ✅ ❌ ❌ ✅ ❌ ✅ ❌ ❌ Memory efficient generational-arena
atree Single &mut Token NonZero<usize> ❌ ✅ freelist ✅ ✅ & ❌ ❌ ✅ ❌ ❌ Vec-Backed Linked Tree
multi-stash Single &mut Key usize ✅ ❌ ✅ ✅ & ❌ ✅ ❌ ❌ ❌ Indexed Vec
colosseum Single & &'a mut NonZero<usize> ✅ ❌ ✅ ❌ ❌ ❌ ❌ 🔒 ❌ Mutexed typed-arena
gc Mixed glob Gc usize ✅ ✅ GC ✅ ❌ ❌ ❌ ❌ ❌ ❌ Garbage Collector
atomic_arena Single &mut?? Key 2*usize ❌ ✅ freelist ✅ ✅ & ❌ ❌ ❌ 🔒 ❌ Vec2
gc-arena Single & Gc<'a> NonZero<usize> ✅ ✅ GC ✅ ❌ ❌ ✅ ❌ ❌ ❌ Garbage Collector
typed-arena-nomut Single & &'a usize ✅ ❌ ✅ ✅ & ❌ ❌ ❌ ❌ ❌ Linked Arena Chunks
typed-generational-arena Single &mut Index ~usize+u64 ❌ ✅ freelist ✅ ✅ & ❌ ✅ ✅ ✅ ❌ ❌ Various backings with Freelist3
compact_arena Single &mut IdxN<'a> u32/u16/u8 ❌ ❌ ✅ ❌ ❌ ✅ ❌ ❌ ❌ Vec with "branded" indices
blink-alloc Mixed & &mut (T: 'static) NonZero<usize> ✅ ❌ ✅ ❌ ✅ ✅ ❌ 🔒 ❌ Linked Arena Chunks
bumpalo-herd Mixed & &'a mut NonZero<usize> ✅ ❌ ❌ ❌ ❌ ✅ ❌ ✅ ❌ Per-thread bumpalo arena
bump_scope Both & BumpBox<'a> NonZero<usize> ✅ ❌ ✅ ❌ ✅ ✅ ❌ ✅ ❌ Linked Arena Chunks4
shredder Mixed glob Gc<'a> Arc+2*usize ✅ ✅ GC ✅ ❌ ❌ ❌ ❌ 🔒 (spinlock) ❌ Single Global GC
erased-type-arena Mixed & AllocMut<'a> NonZero<usize>+Arc ✅ ❌ ✅ ❌ ❌ ❌ ❌ ❌ ❌ Linked List
riddance Single &mut Id<T> u32/u64 ❌ ✅ freelist ✅ ✅ ❌ ❌ ❌ ❌ ❌ Vec with Freelist
drop-arena Single & DropBox<'a> NonZero<usize> ✅ ✅ freelist ✅ ❌ ❌ ❌ ❌ ❌ ❌ typed-arena + free list
elise Mixed glob Gc<'a> usize ✅ ✅ GC ✅ ❌ ❌ ❌ ❌ 🔒 ❌ Single Global GC
hato Mixed &mut Handle u32+u32 ❌ ✅ freelist ❌ ❌ ❌ ❌ ❌ ❌ 🔒 ❌ Vecs of bitwise-copyable objects grouped by type

Footnotes

  1. Also uses a freelist, but on request can actually reduce its memory size. ↩

  2. Allocating slots in the arena is atomic, but using and storing data into the arena requires &mut and the only useful way to use this library across threads is by putting the Arena in a Mutex ↩

  3. Seems to be a fork of sorts of generational-arena . Supports many more types of backing storage including more space-efficient ones. ↩

  4. Surprisingly well-made and documented library compared to its number of downloads. Super well tested too. Also has arena-per-thread. ↩