Arena

Plenty of work produces many small pieces of memory whose lives all end together: everything built while handling one request, one frame of a game, one round of a loop. Releasing each piece separately is slow and easy to get wrong. An arena takes a different approach — it never takes back a single piece, and instead takes back everything at once.

How an arena hands out memory

An arena holds a large block and a marker. Each request is served from the marker onwards, and the marker moves forward past it. That is all an allocation costs: an addition and a check that the block still has room.

When a block runs out, the arena takes a bigger one from the allocator behind it, its backing allocator. Reset moves the marker back to the start, keeping the largest block for next time, and the arena's destructor returns all its blocks when the arena itself dies.

flowchart LR
    sys["SystemAllocator"] -- "large blocks" --> arena["Arena"]
    arena -- "Handle()" --> h["Allocator"]
    h -- "Allocate:<br/>move the marker" --> work["one round<br/>of work"]
    work -- "Reset:<br/>marker back to the start" --> arena
    arena -- "~Arena:<br/>blocks returned" --> sys

Setting one up

The arena is built over a backing allocator, with the size of its first block:

var arena = Arena(backing, 256);
var handle = arena.Handle();
let allocator: Allocator = handle;

The arena is used through Handle(), an Allocator that points back at it. Code like Squares takes that Allocator and has no idea an arena is behind it.

Nobody releases anything

Squares asks for storage and never gives it back:

let numbers = (allocator.Allocate(layout)? as *var int64)[..count];

With SystemAllocator that would be a leak. With an arena it is the intended use: the memory belongs to the round, and the round ends with one call.

arena.Reset();

Watching it grow

The three Squares calls of a round ask for 10, 20 and 30 numbers of eight bytes — 480 bytes in all. The first round outgrows the 256-byte block and takes a second, larger one, so it ends holding two blocks. Reset keeps only the larger block, and every later round fits inside it: the output shows blocks held 1 from then on, and the arena never asks the system for anything again. BytesUsed counts across every block the arena holds.

The rule the compiler does not check

After Reset, every address the arena handed out is invalid, even though the pointers holding them still look fine. Finish with them first. That includes any Box built on the arena: destroy the box before the reset, or its destructor will later run on memory the arena has already handed out again.

The handle has a rule of its own. It holds a pointer back to the arena, so it must not outlive the arena, and it must not be used after the arena moves.

The program

The whole lesson is one package in the Examples repository. Its comments explain every step.

// An arena hands out memory by moving a marker forward through a large block, and never takes
// back a single piece. Instead, `Reset` takes everything back at once, and the arena's
// destructor returns its blocks to the allocator behind it.
//
// That fits work whose pieces all end together: one request, one frame, one round of a loop.
// Asking is fast, nothing has to be released piece by piece, and nothing can be released twice.
// When a block runs out, the arena takes a bigger one from its backing allocator; `Reset` keeps
// the largest, so the next round usually needs nothing new.
//
// The price is one rule the compiler does not check: after `Reset`, every address the arena
// handed out is invalid. Finish with them first, and that includes any `Box` built on the
// arena, which must be destroyed before the reset. The arena is used through `Handle()`, an
// `Allocator` that points back at it, so the handle must not outlive the arena or be used after
// the arena moves.
import Allocator::{ AllocError, Allocator, Arena, Layout, SystemAllocator };
import Io::PrintLine;

// Scratch storage for one round. Nothing here releases it; the arena's reset will.
func Squares(allocator: Allocator, count: uint) -> int64 ! AllocError {
    let layout = Layout::ForArray<int64>(count) ?? fail AllocError::Unsupported;
    let numbers = (allocator.Allocate(layout)? as *var int64)[..count];
    var total: int64 = 0;
    for i in 0..count {
        numbers[i] = (i * i) as int64;
        total += numbers[i];
    }
    return total;
}

func Main() -> ! AllocError {
    var system = SystemAllocator();
    let backing: Allocator = system;

    // The first block holds 256 bytes; later ones grow as needed.
    var arena = Arena(backing, 256);
    var handle = arena.Handle();
    let allocator: Allocator = handle;

    for round in 1..=3 {
        // 10, 20 and 30 numbers of eight bytes: 480 bytes in all. The first round outgrows the
        // 256-byte block and takes a second, larger one. The reset keeps that larger block, and
        // every later round fits inside it. `BytesUsed` counts across every block the arena holds.
        let total = Squares(allocator, 10)? + Squares(allocator, 20)? + Squares(allocator, 30)?;
        PrintLine("round {}: total {}, bytes in use {}, blocks held {}",
            round, total, arena.BytesUsed(), arena.BlockCount());

        // The round is over and nothing from it is still in use, so all of it goes at once.
        arena.Reset();
        PrintLine("  reset: bytes in use {}, blocks held {}",
            arena.BytesUsed(), arena.BlockCount());
    }
}

Besides Io, its Rux.toml lists Allocator under [Dependencies].

Run it

cd Examples/Memory/Arena
rux run

round 1: total 11310, bytes in use 480, blocks held 2
  reset: bytes in use 0, blocks held 1
round 2: total 11310, bytes in use 480, blocks held 1
  reset: bytes in use 0, blocks held 1
round 3: total 11310, bytes in use 480, blocks held 1
  reset: bytes in use 0, blocks held 1

Common mistakes

Try it yourself

1. Change the first block size from 256 to 1024. How many blocks does round 1 hold now?
2. Remove arena.Reset() and watch BytesUsed and BlockCount grow from round to round.
3. In Main, allocate two blocks in a row through allocator. Release the first and print BytesUsed, then release the second and print it again. Which release made a difference, and why?

Learn more

• Allocator — the interface the handle implements
• Fixed buffer — the same idea over storage you already have
• Pool — for pieces that come and go in no particular order