Writing arenas in Rust from scratch | Artem Golubin

Custom memory allocations and arenas are notoriously hard to deal with in Rust due to the ownership model.

In a lot of projects, they can significantly improve performance.<br>For example, let's take databases.<br>Sending a query to a database produces a lot of temporary objects, and if the default allocator is used,<br>you will need to allocate and deallocate thousands of small objects for each query, which is wasteful.

Almost every database engine uses custom memory pools to improve performance.<br>Some go so far as to statically allocate<br>all the memory before the program starts.

Another good example is scripting languages. I have an article<br>on how Python uses arenas to reduce the number of allocations for Python types. A simple web app in Python can<br>allocate more than a million of objects after 100 HTTP requests.<br>Using a system allocator for such a case is wasteful.

And yet, to this day, there is no proper way to deal with custom allocations and arenas in Rust.<br>The allocator_api, which allows using a custom allocator, has been nightly-only (experimental) since 2016.

Recently, I wanted to learn how to implement an arena in Rust.<br>This is my explanation of how to implement a basic version.

What is an arena?

An arena is a preallocated memory block that you allocate only once.<br>Instead of allocating 1000 small objects, you can allocate one big block of memory and put the objects there when needed.<br>This is usually done by simply moving the pointer forward in the allocated memory block.<br>Usually, blocks allocated inside the arena are called slots or cells.

When you are done working with the allocated block, you can reuse the allocated space for the next<br>set of objects instead of deallocating it.<br>You don't even need to clear the memory - all you need to do is move the pointer back to the beginning of the block.

By using arenas, you get faster allocations, less memory fragmentation, and better cache locality.

Basic implementation

The simplest possible arena can be implemented as a vector that has a fixed capacity.

struct ArenaT> {<br>items: VecT>,<br>capacity: usize,

implT> ArenaT> {<br>fn with_capacity(capacity: usize) -> Self {<br>Self {<br>items: Vec::with_capacity(capacity),<br>capacity,

fn alloc(&mut self, value: T) -> Optionusize> {<br>if self.items.len() >= self.capacity {<br>return None;

let id = self.items.len();<br>self.items.push(value);<br>Some(id)

fn get(&self, id: usize) -> OptionT> {<br>self.items.get(id)

fn get_mut(&mut self, id: usize) -> Optionmut T> {<br>self.items.get_mut(id)

fn len(&self) -> usize {<br>self.items.len()

This can even be simplified to:

type ArenaT> = VecT>;

fn allocT>(arena: &mut ArenaT>, value: T) -> Optionusize> {<br>if arena.len() == arena.capacity() {<br>return None;

let id = arena.len();<br>arena.push(value);<br>Some(id)

fn main() {<br>let mut arena: Arenai32> = Vec::with_capacity(3);

It uses a fixed capacity because we don't want the arena to be reallocated.<br>The whole point of arenas is to minimize memory allocations and fragmentation.

Right now, this code is safe, but it has a lot of limitations and is only used for simple use cases.

You can only store one data type

You can't remove objects

It can't hold collections or any dynamically sized objects (the actual values will be allocated outside of the arena)

You can't have multiple mutable references to different memory blocks

It's not thread-safe, even when different threads mutate different slots

The borrow checker doesn't let you hold multiple mutable (&mut) references into the same vector:

fn main() {<br>#[derive(Debug)]<br>struct Point {<br>x: i32,<br>y: i32,<br>let mut arena = Arena::with_capacity(10);

let p1 = arena.alloc(Point { x: 10, y: 20 }).unwrap();<br>let p2 = arena.alloc(Point { x: 30, y: 40 }).unwrap();

let a = arena.get_mut(p1).unwrap();<br>let b = arena.get_mut(p2).unwrap();

println!("{:?}", a);<br>println!("{:?}", b);

error[E0499]: cannot borrow `arena` as mutable more than once at a time<br>--> src/main.rs:49:13<br>48 | let a = arena.get_mut(p1).unwrap();<br>| ----- first mutable borrow occurs here<br>49 | let b = arena.get_mut(p2).unwrap();<br>| ^^^^^ second mutable borrow occurs here<br>50 |<br>51 | println!("{:?}", a);<br>| - first borrow later used here

When we store simple objects, they are stored directly inside the arena:

let mut arena = Arena::i32>::with_capacity(4);

arena.alloc(10);<br>arena.alloc(20);<br>arena.alloc(30);

The memory layout looks something like this:

arena<br>+-- Vec<br>+-- ptr ────────────────┐<br>+-- len = 3 |<br>+-- capacity = 4 |<br>Vector based buffer:<br>+--------+--------+--------+--------+<br>| i32 10| i32 20| i32 30| unused |<br>+--------+--------+--------+--------+

Now let's look at the strings:

let mut arena = Arena::String>::with_capacity(3);

arena.alloc("hello".to_string());<br>arena.alloc("world".to_string());<br>arena.alloc("arena".to_string());

arena<br>+-- Vec<br>+-- ptr ────────────────────────────────┐<br>+-- len = 3 |<br>+-- capacity = 3 |<br>Vector based buffer:<br>+----------------+----------------+----------------+<br>| String...