An O(1) offset sub-allocator. It hands out offsets into a range you own,
a GPU buffer, a VkDeviceMemory block, an ID3D12Heap, an arena, and
never touches the memory itself. #![no_std], needs alloc.
use holeinone::Allocator;
let mut heap = Allocator::new(256 << 20);
let vertices = heap.allocate(3 << 20)?;
let uniforms = heap.allocate_aligned(4096, 256)?;
upload(vertices.offset(), uniforms.offset());
heap.free(vertices);
heap.free(uniforms);Not on crates.io yet:
[dependencies]
holeinone = { git = "https://github.com/mightsleep/holeinone" }Rust 1.89 or newer.
A size becomes a small float: five bits of exponent (the position of
the highest set bit, one lzcnt) and the four bits below it as
mantissa. That gives sixteen size classes per power of two, so blocks
in one class differ by at most a sixteenth. Free blocks sit in a list
per class.
Which classes are non-empty is a two-level bitmap shaped like the float:
one u32 with a bit per exponent, and under each exponent a u16 with
a bit per mantissa. Finding the smallest non-empty class at or above a
request is two bit searches and no loop. Freeing merges with the
neighbours in address order through two links every block keeps, and
the class lists are doubly linked, so taking a neighbour out of its
list is O(1) too.
The algorithm is Sebastian Aaltonen's OffsetAllocator (2023), by way of Patrick Walton's Rust port offset-allocator, which this crate forks.
The round-down bin. A free block is filed under its size rounded down, a request searches from its size rounded up. A request of 69 that is not on a class boundary therefore never sees a free block of 70 in its own class, and the classic symptom is a fresh allocator refusing a request for its whole capacity (pcwalton #9, sebbbi #11). The usual fix is a slow path that looks into that class only when everything above is empty. Here the bitmap search starts at the round-down class instead and checks up to four of its blocks; when that class is empty, which on a lightly used heap it nearly always is, the search is the same instructions with a different start bit. Only when every larger class is empty does it walk the whole class, as the last chance before failing; that is the one place allocation is not O(1).
Sixteen classes per power of two, where upstream has eight. The part of its own class a request skips is half as wide, at the same speed, for 1 KiB more of class heads.
Under churn at 90 % occupancy, allocations failed (examples/rd_first_churn.rs):
| workload | offset-allocator | round-down probe | and 16 classes |
|---|---|---|---|
| 64 MiB, blocks 64 B to 64 KiB | 11.65 % | 0.049 % | 0.010 % |
| 256 MiB, blocks 64 B to 4 MiB | 30.95 % | 21.1 % | 19.2 % |
The second row is past what any placement survives: an exact best-fit over a tree of free ranges fails 18.7 % of the same requests.
Cutting in place. When what is left of a block after an allocation stays in the block's size class, the free node keeps it where it is, its offset moved up, and only the allocation gets a new node. Carving up a large block then touches no list and no bitmap: allocation alone is faster than offset-allocator's although holeinone does more per operation elsewhere.
Free reuses the node. When a freed block merges with a free neighbour, its node becomes the node of the merged block instead of going back to the free-node stack while another one is taken: a push and a pop less on every free that merges.
No separate node pool. Unused nodes form a stack threaded through
their own list link, and nodes are taken from the reserved array only
when first needed. Metadata is 24 bytes per node and grows with the
peak number of live allocations, not with max_allocations; creating an
allocator and reset do not touch the node array at all.
Alignment without over-allocating. allocate_aligned hands the
bytes skipped to reach alignment back to the free lists, so an aligned
allocation is exactly the size asked for.
Handles are moved, not copied, and know their allocator.
Allocation is neither Clone nor Copy and free takes it by
value, so the borrow checker rules out freeing a range twice. Each
handle also carries the id of the allocator that issued it, renewed on
every reset: freeing one in the wrong allocator, or one from before a
reset, panics instead of quietly freeing whatever its node holds now.
Allocation::id gives a Copy + Hash key for side tables.
Freeing after the GPU is done. A renderer cannot free a frame's
buffers when the CPU is done with them: the GPU reads them one to three
frames later. free_after takes the handle and the fence, timeline or
frame value after which the GPU no longer needs it; retire frees
everything up to the value the GPU has reached:
for frame in 0.. {
if let Some(done) = gpu_completed_frame() {
heap.retire(done);
}
let uniforms = heap.allocate_aligned(64 << 10, 256)?;
record(uniforms.offset());
heap.free_after(uniforms, frame);
}Values are expected not to go down; one that does is treated as the largest seen so far, so nothing is ever freed early.
max_allocations means allocations. A free block never borders
another, so there are at most one more of them than live allocations,
and the allocator reserves 2n + 1 nodes for n allocations. That many
always fit as far as metadata goes, however fragmented the space;
OutOfNodes means exactly that n are live.
Also: upstream's off-by-one in counting allocations against
max_allocs (sebbbi #3) is fixed, grow extends the range in O(1),
errors implement core::error::Error, and every type is Debug.
Sizes and offsets are bytes in u64. Inside, they are counted in
quanta of a power-of-two number of bytes, so a node stays 24 bytes for
any capacity. Allocator::new picks the smallest quantum that covers
the capacity: one byte up to 2 GiB, 64 bytes for 64 GiB. A larger one
rounds every allocation up to a multiple of it, which GPU resources
are anyway:
// One buffer for all geometry, offsets in 256-byte units.
let mut geometry = Allocator::builder(64 << 30).quantum(256).build();The capacity, and a single allocation, is at most quantum × (2³¹ − 1)
bytes: the top bit of a node's size marks it used. The number of live
allocations is fixed at construction, 128 Ki by default
(Builder::max_allocations); the 24-byte nodes for them are reserved
as address space and touched on first use.
cargo bench --bench compare # allocate, free in three orders, alignment
cargo bench --bench gpu_workloads # per-frame transients, streaming, fragmentation
cargo run --release --example rd_first_churnBoth suites run the same requests through offset-allocator 0.2.
Sizes come from a seeded xorshift, so runs are reproducible. Each
implementation keeps one allocator across iterations and resets it
untimed, as a program would; a fresh allocator per iteration would
also time when each one first touches its node memory.
Criterion medians on a laptop, 2026-10-11, median of three runs (they agree within 1 %). The ratio is holeinone's time over offset-allocator's: below 1 is faster.
| workload | holeinone | offset-allocator | ratio |
|---|---|---|---|
| allocate and free 2000, random order | 35.5 µs | 44.3 µs | 0.80 |
| allocate and free 2000, LIFO | 29.5 µs | 44.0 µs | 0.67 |
| per-frame transients, 10 frames × 200 | 28.3 µs | 45.4 µs | 0.62 |
| 8 long-lived assets, 10 frames of transients | 11.6 µs | 18.9 µs | 0.61 |
| ring of 3 frame uniform blocks, 16 Ki entities | 0.50 µs | 0.68 µs | 0.74 |
| 500 allocations, free half, 100 larger | 5.8 µs | 7.6 µs | 0.76 |
| allocate only, 5000 × 64 B to 64 KiB | 32.4 µs | 36.4 µs | 0.89 |
| the same into a full 16 MiB heap (90 % fail) | 14.9 µs | 11.3 µs | 1.32 |
| aligned to 64, 256 or 4096, mixed, with frees | 7.8 µs | 6.9 µs | 1.14 |
| aligned to 4096, 500 × 64 B to 1 KiB | 12.0 µs | 4.0 µs | 3.0 |
The per-frame transients freed three frames later through free_after
and retire, as a renderer with frames in flight frees them, take
33.2 µs; offset-allocator has no equivalent.
Most of the allocation speed comes from cutting in place: when what is
left of a block after an allocation stays in the block's size class,
the free node keeps it where it is and only the allocation gets a new
node, so neither list nor bitmap is touched. The aligned rows are not
the same work. With offset-allocator the usual way is to allocate
size + alignment - 1 and round the offset up, so the padding stays
inside every allocation: at 4096 and these sizes the heap holds several
times more than was asked for. holeinone gives the padding back to the
free lists. Failing allocations cost more because a request that does
not fit above its own class still checks the blocks inside it before
giving up.
MIT, as the code it derives from. LICENSE keeps the notice of Sebastian Aaltonen and Patrick Walton.