Arenas

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.

• Linked Arena Chunks means that at a basic level, big chunks of contiguous memory are allocated, slowly filled, and linked together to form one big arena built up from smaller chunks.
• Vec (with freelist) refers to the backing storage. An Arena is a Vec, and you get indices to later index the Vec to get the element you stored.
• Linked List means every element in the arena gets its own link in a linked list.

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