Memory · Lesson 15.13

Pool

Reuse fixed-size blocks from a Pool, where a released block goes straight back to the next request of its size.

You'll need: Allocator, Arena, Absence to error, Fallible main

An arena suits values that all end together. A pool suits the opposite shape: many small values that come and go in no particular order — the nodes of a list, the entries of a table, the bullets in a game. Each one is released on its own, and the very next request of that size gets the released block straight back.

Blocks of a few fixed sizes

A pool cuts large chunks of memory into equal blocks and keeps the free ones on a list. To keep that fast, it only serves a handful of block sizes, called classes, and rounds every request up to the nearest one:

PrintLine("block sizes: {} {} {} {} {}", pool.ClassSize(0), pool.ClassSize(1),
    pool.ClassSize(2), pool.ClassSize(3), pool.ClassSize(4));
let odd = Layout::New(20, 8) ?? fail AllocError::Unsupported;
PrintLine("a 20-byte request uses a {}-byte block", pool.ClassSize(ClassIndexFor(odd)));

Request	Block it takes	Unused bytes
1–16 bytes	16	up to 15
17–32 bytes	32	up to 15
33–64 bytes	64	up to 31
65–128 bytes	128	up to 63
129–256 bytes	256	up to 127
more than 256	none — passed straight to the backing allocator	—

Rounding is the price of speed. A 20-byte request takes a 32-byte block, and the other 12 bytes sit unused until that block comes back. Layout::New(size, alignment), used for odd, builds a layout from two plain numbers; it is none when the pair cannot be a layout, such as an alignment that is not a power of two.

Taking and returning blocks

The pool is created over a backing allocator with the number of blocks per chunk, and used through its handle like every allocator in this part:

var pool = Pool(backing, 8);
var handle = pool.Handle();
let allocator: Allocator = handle;

Three 16-byte points come out of the first chunk, and the middle one goes back first:

let first = allocator.Allocate(layout)?;
let second = allocator.Allocate(layout)?;
let third = allocator.Allocate(layout)?;
PrintLine("three out:   {} live blocks, {} chunk", pool.LiveBlocks(), pool.ChunkCount());

allocator.Deallocate(second, layout)?;

flowchart LR
    chunk["a chunk from the<br/>backing allocator"] -- "cut into<br/>8 blocks" --> list[("free list<br/>16-byte class")]
    list -- "Allocate<br/>takes one" --> use["in use"]
    use -- "Deallocate<br/>puts it back" --> list

The next request reuses the block

A released block goes straight back on the free list of its class, so the next request of that size gets that very block:

let fourth = allocator.Allocate(layout)?;
PrintLine("fourth reuses the second's block: {}", fourth == second);

No search, no new chunk — a handful of instructions. When every block is back, LiveBlocks is 0, but the chunk stays: it is ready for the next requests, and goes back to the backing allocator only when the pool is destroyed.

Arena or pool?

	Arena	Pool
Values end	all together	one by one, in any order
Releasing one value	does nothing (unless it was the latest)	puts its block back for reuse
You must release	nothing — `Reset` takes it all	every block, with its layout
Wasted space	only padding for alignment	the rounding up to a class

The program

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

Src/Main.rux

// A pool suits many small values that come and go in no particular order: the opposite of an
// arena, where everything ends together. It cuts large chunks into equal blocks and keeps the
// free ones on a list. Allocating takes a block off the list, and releasing puts it straight
// back, ready for the next request of that size.
//
// Requests are rounded up to a few fixed block sizes, called classes: 16, 32, 64, 128 and 256
// bytes. Rounding is the price of speed. A 20-byte request takes a 32-byte block, and the other
// 12 bytes sit unused until that block comes back.
//
// Unlike an arena, a pool expects each block back: `Deallocate` with the same layout, through
// the pool it came from. The chunks themselves go back to the backing allocator when the pool
// is destroyed.
import Allocator::{ AllocError, Allocator, ClassIndexFor, Layout, Pool, SystemAllocator };
import Io::PrintLine;

struct Point {
    x: int64;
    y: int64;
}

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

    // Each chunk is cut into eight blocks.
    var pool = Pool(backing, 8);
    var handle = pool.Handle();
    let allocator: Allocator = handle;

    PrintLine("block sizes: {} {} {} {} {}", pool.ClassSize(0), pool.ClassSize(1),
        pool.ClassSize(2), pool.ClassSize(3), pool.ClassSize(4));
    let odd = Layout::New(20, 8) ?? fail AllocError::Unsupported;
    PrintLine("a 20-byte request uses a {}-byte block", pool.ClassSize(ClassIndexFor(odd)));

    // Three 16-byte points, all out of the first chunk.
    let layout = Layout::ForValue<Point>();
    let first = allocator.Allocate(layout)?;
    let second = allocator.Allocate(layout)?;
    let third = allocator.Allocate(layout)?;
    PrintLine("three out:   {} live blocks, {} chunk", pool.LiveBlocks(), pool.ChunkCount());

    // Blocks can come back in any order. The middle one goes first.
    allocator.Deallocate(second, layout)?;
    PrintLine("one back:    {} live blocks", pool.LiveBlocks());

    // The next request of the same size gets that very block back.
    let fourth = allocator.Allocate(layout)?;
    PrintLine("fourth reuses the second's block: {}", fourth == second);

    allocator.Deallocate(first, layout)?;
    allocator.Deallocate(third, layout)?;
    allocator.Deallocate(fourth, layout)?;

    // Every block is back, and the chunk stays for the next requests.
    PrintLine("all back:    {} live blocks, {} chunk", pool.LiveBlocks(), pool.ChunkCount());
}

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

Run it

cd Examples/Memory/Pool
rux run

block sizes: 16 32 64 128 256
a 20-byte request uses a 32-byte block
three out:   3 live blocks, 1 chunk
one back:    2 live blocks
fourth reuses the second's block: true
all back:    0 live blocks, 1 chunk

Common mistakes

Releasing with a different layout.
The pool works out a block's class from the layout alone, so it cannot tell when the layout is wrong. Release a 16-byte point with the 20-byte odd layout and the call succeeds — and the block lands on the 32-byte list, where the next 20-byte request receives a block that is only 16 bytes long. Always release with the layout you allocated with.

Forgetting to release.
A pool expects each block back. A block never released stays counted in LiveBlocks and cannot be reused; its memory only returns when the whole pool is destroyed.

Using a block after releasing it.
As fourth == second shows, a released block is handed out again at the very next request. Anything still writing through the old pointer now writes into someone else's value.

Try it yourself

Allocate nine points instead of three, with eight blocks per chunk. What does ChunkCount say now?
Ask ClassIndexFor about a 300-byte layout. It returns 5, one past the last class — what does that mean for where the memory comes from?
Release first and third before allocating fourth. Which of the two does fourth reuse?

Learn more

Arena — the opposite trade: nothing released one by one
Allocator — the Deallocate contract every allocator shares
Part 17: Collections — containers that take an Allocator and allocate as they grow

15.12 Fixed buffer

Allocate from storage you already own with FixedBuffer, which refuses with OutOfMemory once the storage is full.

15.14 Zeroize

Wipe a secret with Zeroize, a clear that the compiler promises never to optimize away.

Edit this page on GitHub