Size as an 8-bit float

The GPU hands you a large chunk of memory, say 256 MiB, and you are on your own from there. Hundreds of buffers and textures live in that chunk, created and destroyed every frame. So I need an allocator, but an odd one: I cannot see into that memory. I cannot write a block header into it like malloc does, and I cannot walk it. The whole allocator has to live on the side and hand out nothing but numbers, offsets into the chunk. Hence: an offset allocator.

It has to be fast and, above all, predictable. An allocation in the middle of a frame that takes ten times longer once in a while is worse than one that is always a little slow.

The result is holeinone, a hole in one. This post is how it got there.

Naive: a list of holes

The simplest allocator keeps a list of free ranges, holes. To allocate, it walks the list and takes the first hole the request fits (first fit), or the smallest one it fits (best fit), and puts the rest of the hole back. To free, it returns the range and glues it to neighbouring holes, if there are any.

It works, and it is linear. With a thousand holes that is a thousand comparisons per allocation, and holes multiply exactly when memory is most fragmented, that is, when it already hurts. Sorting the holes by size into a tree gives a logarithm, which is decent, but still a search.

Buddy: powers of two and XOR

The Linux kernel allocates pages differently. Every block is a power of two in size and sits at an offset that is a multiple of it. A block of size 2^k at offset o then has exactly one possible partner, its buddy, at o ^ (1 << k). Freeing does not search, it computes: is the buddy free? Merge the two into a block one order larger and try again. Free blocks are kept in lists per order, so an allocation takes the first non-empty list from the right order up.

Beautiful, but it costs memory. A request for 65 KiB gets 128 KiB. In the worst case almost half is thrown away.

Size as a float

Buddy has size classes by powers of two, which is too coarse. Linear classes would be too fine: from bytes to gigabytes there would be billions of them. I want something in between, and we all know that something: a float. A float has an exponent, so it covers a huge range, and a mantissa, so it tells a few steps apart within one power of two.

So I take the size and encode it in eight bits as a small float: three bits of mantissa, five of exponent. The exponent is the position of the highest set bit, one lzcnt instruction, and the mantissa is the three bits below it:

const fn uint_to_float_round_down(size: u32) -> u32 {
    if size < 8 {
        return size;
    }
    let highest_set_bit = 31 - size.leading_zeros();
    let mantissa_start_bit = highest_set_bit - 3;
    let exp = mantissa_start_bit + 1;
    let mantissa = (size >> mantissa_start_bit) & 7;
    (exp << 3) | mantissa
}

That makes 256 codes, of which sizes in u32 reach 240, and the top class starts at 3.75 GiB. Each power of two holds eight classes, so the sizes of blocks in one class differ by at most an eighth. A few examples:

And this is not a float only figuratively. Convert the size to f64 and look at the bits. The exponent of an f64 is 1023 + h, where h is the position of the highest bit, and the top three bits of the mantissa sit at bits 49 to 51. My exponent is h − 2, so a shift and a subtraction do it:

fn round_down_f64(size: u32) -> u32 {   // for size >= 8
    ((size as f64).to_bits() >> 49) as u32 - (1025 << 3)
}

fn round_up_f64(size: u32) -> u32 {     // for size >= 8
    (((size as f64).to_bits() + (1 << 49) - 1) >> 49) as u32 - (1025 << 3)
}

Rounding up is adding "almost one" just below the three mantissa bits. When the mantissa overflows from 0b111, the carry walks into the exponent by itself, exactly as with any other float. I checked this against the original functions for every size from 8 to 2³² − 1, and they never differ. It is not faster, the conversion to f64 has a longer latency than lzcnt. But nobody can claim any more that it is only like a float.

A free block goes into the class of its size rounded down. A request is rounded up instead: whoever wants 100 bytes searches from class 37, that is, from 104. That guarantees any block in class 37 or above fits, and nothing inside a class needs comparing. I take the first block of the list and I am done. Not exactly best fit, but at worst an eighth off.

Where is the nearest non-empty class

What remains is finding the smallest non-empty class from 37 up. Naively, walk the lists one by one, all 256 in the worst case. But "is this class non-empty" is one bit, and 256 bits fit in four words. And "find the first one bit from position k on" is a mask and a tzcnt:

fn find_lowest_bit_set_after(mask: u32, start_bit: u32) -> Option<u32> {
    (mask & !u32::low_ones(start_bit)).first_set()
}

(low_ones and first_set come from hakmem; otherwise it is a plain mask & !((1 << k) - 1) and trailing_zeros.)

To make it one word instead of four, the bitmap has two levels, shaped exactly like the float: the top five bits of the class (the exponent) pick one of the 32 bits of the top mask, the bottom three (the mantissa) one of the eight bits of the byte below it. The search then goes: try the rest of the byte in your own power of two, and if it is empty, jump in the top mask to the next non-empty power and take its lowest class. Two bit searches, no loop, no walking lists. Allocation is O(1), and the constant really is small.

Free: neighbours by offset

To free, I need to glue the block to its free neighbours. Buddy computed them with an XOR; here blocks have arbitrary sizes, so XOR is no help. What helps is that every block, free or used, remembers its left and right neighbour in memory. Freeing looks at two pointers: is the neighbour free? Take it out of its class and attach it. Then put the result into the class of its new size. O(1) again, no search again.

Well, it should be. My first port had singly linked class lists. That saves 4 bytes per node and is enough for allocation, which always takes the head of a list. But the neighbour I merge with has to come out of the middle of its list, and that needs its predecessor. A singly linked list finds it only by walking from the head. I defended this in a comment: classes tend to be short, and fine classes "naturally bound" their length. They do not. Nothing bounds how many blocks one class can hold.

Allocate n equal blocks, free every other one (n/2 blocks in one class), then free the rest. Every free merges with a neighbour deep in the list:

The time per free grows linearly, the whole thing is quadratic. Upstream has doubly linked lists and holds a constant. A regression I had brought into my own fork, for 4 bytes.

The fix is a doubly linked list, and the 4 bytes can be found elsewhere. A node that sits in no list and no allocation has its list link unused, so the stack of free nodes can be threaded through those nodes instead of a separate array of indices. A node stays at 24 bytes, as before (20 plus 4 in the array), and there is a bonus: nodes are taken from the reserved array only when first needed. Creating an allocator with 128 Ki nodes went from 101 µs to 81 ns and reset from 80 µs to 30 ns, because neither touches the node array any more. And under churn at 90 % occupancy, where merging never stops, allocate and free together got twice as fast (80 against 39 ns per operation), without any constructed worst case.

The asymmetry where the bug hid

I insert rounding down and search rounding up. What if exactly one free block of size 100 exists and someone wants exactly 100? The block sits in class 36, the search starts at class 37 and skips it. The allocator reports out of memory with a perfectly fitting block right there.

This is not an academic exercise. The cleanest case is a fresh allocator holding its whole capacity in one block, asked for its whole capacity. Unless the capacity lies on a class boundary, the answer is None. The Rust port offset-allocator has it as a known bug (pcwalton #9, sebbbi #11 in the original). The fix is a slow path: when the fast search finds nothing, walk the list of the round-down class as well and check the actual block sizes. That class usually holds few blocks, and the fast path stays untouched.

It can all be said algebraically, and then it is clear why the bug happened. Rounding up is rounding down the number one smaller, plus one:

It holds because sizes are integers: a class's lower bound is at least r exactly when it is greater than r − 1. With floats it would not hold.

So the fast path searches for the strict successor of the class that r − 1 falls in. But the blocks that would fit exactly sit in class round_down(r), and unless r lies on a class boundary, that is the same class as round_down(r − 1): precisely the one the strict successor skips. The right query is "successor or equal" for round_down(r), with sizes to check in that one class only. The slow path does exactly this, it just has a name now. And the second rounding function is not needed any more.

The tip of the iceberg

But the slow path only gets its turn when everything above round_down(r) is empty. Until then the class is skipped every time. Whoever wants 100 bytes while class 36 holds a block of 101 does not get it: they get a piece of the first block a class or more higher, and that one gets split. On an empty allocator it does not matter. On a full one it turns into rubble.

I measured it on a long workload: log-uniform sizes in a range, allocate until occupancy reaches 90 %, then free random allocations, round and round a million times. How many allocations failed:

The fix is that identity again, this time in the fast path. The bitmap is asked not for the strict successor of class round_down(r) but for "successor or equal". When the round_down class is empty, which on a lightly used allocator it nearly always is, the query returns exactly what it did before: the same instructions, a different start bit. When it is not empty, I check at most four of its blocks, and if none fits, continue one class up.

The third row is the second lever. The asymmetry never goes away, the width of a class only sets how much of its own class a request skips. With four mantissa bits a class is a sixteenth wide instead of an eighth, and failures on the smaller blocks drop another five times, at the same speed, for 1 KiB more of class heads. With the large blocks, 90 % is past what any placement survives: even an exact best fit over a tree of free ranges fails 18.7 % of the same requests, so 19.2 % is at the ceiling.

Try it: two 4 MiB heaps get exactly the same stream of requests (blocks of 64 B to 8 KiB, occupancy held at the target) and differ only in where the allocator starts searching. Both hold the same occupancy, so both have the same amount of free memory. The difference is where that free memory is: the original has it broken into holes an ordinary request does not fit, and so it fails. The lower chart shows it directly, free memory by hole size.

Cutting in place

After all the fixes, holeinone was faster than upstream wherever blocks are freed and reused. Only allocation alone, carving up one large block in sequence, was 1.23 times slower. So I looked at where the time went.

perf annotate showed allocation bound by the latency of a chain of dependent loads: the bitmap, the class head (20 % of samples), the node, the store of the new head (9 %), the remainder's class and its head (18 %). The block comes out of its list, the allocation is cut off its front, and the rest goes back in. But when one large block is being carved up, the rest almost always lands in the same class the block came from. The list empties, the bitmap bits are cleared, and right after, the same list fills up again and the bits are set.

Turn it around: the free node keeps the rest. It stays where it is, in the same list, with its offset moved up and its size reduced, and the allocation gets the new node. Neither the lists nor the bitmap are touched. Placement does not change, the allocation still takes the front of the block, so the failure counts on the long workload came out identical to the last block. Only the cost changed: sequential allocation went from 44.9 to 32.4 µs, 0.89 of upstream.

One trap on the way: I generalised it to a cut at any offset, to cover aligned allocations with front padding as well, and the unaligned path slowed back down to 40 µs. The general function, one branch richer, was expensive on the hot path. The unaligned path now has its own specialised version.

Beyond 4 GiB, and freeing when the GPU is done

Offsets in u32 mean a heap of up to 4 GiB, and since the top bit of a size marks a node used, in fact up to 2 GiB. That is enough for blocks of the size VMA and friends allocate, but not for one huge buffer holding all geometry. So holeinone counts in quanta inside, units of a power-of-two number of bytes, and speaks bytes in u64 outside. A node stays 24 bytes for any capacity, the quantum is chosen as the smallest that covers the capacity (one byte up to 2 GiB), and GPU resources need alignment of tens of bytes and more anyway.

The second thing I only realised when I imagined actually using the crate: a renderer cannot free a frame's buffers when the CPU is done with them. The GPU reads them one to three frames later. Hence free_after(allocation, value), with a fence or timeline semaphore value, and retire(completed), which frees everything up to that value. Transients freed three frames later cost 33.2 µs against 28.3 µs for freeing right away: about 7 % is the queue, the rest more merging, since blocks leave while more of their neighbours are alive.

What it buys

The core is not mine: it is Sebastian Aaltonen's OffsetAllocator (2023), by way of Patrick Walton's Rust port. Against offset-allocator 0.2 on a laptop, median of three criterion runs, the ratio being holeinone's time over upstream's:

The last two rows are not the same work. A failing request in mine still checks the blocks in its own class; upstream gives up at once, at the price of bug #9. And with alignment, upstream users allocate size + alignment − 1 and the padding stays inside the allocation, so at an alignment of 4096 the heap holds several times what was asked for. holeinone gives the padding back.

Benchmarks that lied

This part was not planned, and it taught me the most.

The probe that cost 18 %. The first measurement on a light workload said the probe into the round_down class cost 5 to 18 %. But the counter said that on the light workload it never once touched a non-empty class. So I measured A/A: two variants with the same fast path, differing only in dead code in the slow path. One of them "got faster" by 3 to 10 %. On microsecond benchmarks, a shift in code alignment is as large as what you are trying to measure. The instruction count from perf stat settled it: the probe adds 2 to 5 % instructions and is indistinguishable from noise in cycles.

A fresh allocator every iteration. The benches built a new allocator in the iteration setup and consumed it in the timed part. Once the node array became lazy, the page faults moved from the constructor into the timed part and holeinone looked slower. What was measured was when the pages got paid for, not how fast allocation is. Now each implementation keeps one allocator, reset between iterations outside the timing, the way a real program uses it.

The bench that measured failure. "Allocate into 16 MiB" allocated 5,000 blocks of 32 KiB on average. A tenth of them fit. The bench pretended to measure allocation and measured the failure path.

Same code, another binary, a third off. Adding two branches to main of a measuring harness moved the times of an entirely different function by a third. I trust only comparisons within one binary, or instruction counts from perf stat.

Cross-crate inlining. After the API became a thin wrapper over an inner function, the body of allocation started being instantiated in the caller's crate, and small helpers without #[inline] could not be inlined across the crate boundary. A forced #[inline(always)], on the other hand, made sequential allocation 3 % faster and the full-heap path almost twice as slow.

An estimate from one harness. I estimated the cost of the new API at 7 % from a harness that dropped the returned handle almost at once. Criterion, which passes it on, showed over 20 %. Then perf showed it was about neither: 96 % of the time was in the allocation function, and that is where the road to cutting in place started.

1994

I started seeing the pattern everywhere: "round the key to a small float, get few classes, put a bitmap with lzcnt over them". Timers: since 2016 the Linux kernel sorts timers into buckets with a granularity of about an eighth, and admits a timer may expire that much later. The commit says it outright, "worst case inaccuracy of 12.5%" (500462a9de65). A priority queue for Dijkstra: the radix heap. Sets of integers: the van Emde Boas tree. I wrote a timer wheel on this pattern and measured it against BinaryHeap from std: seven times faster on dense data. That is to be expected: a binary heap knows nothing of keys being small integers. But then I wrote a priority queue for Dijkstra on the same pattern (Dial's algorithm: buckets by distance, a two-level bitmap over them), about a hundred lines, and measured it against the radix-heap crate. The radix heap is a structure capable people have been refining since Ahuja, Mehlhorn, Orlin and Tarjan described it in 1990. On dense graphs my queue was 1 to 22 % faster, on sparse ones 31 to 74 %. To be fair: a radix heap takes any monotone keys, mine needs a bounded edge weight and a bucket for every distance in the window, and the gain is exactly that with monotone keys nothing gets redistributed. Still. A general pattern! A universal primitive!

Then I found Matias, Vitter and Young, Approximate Data Structures with Applications, SODA 1994. Keys rounded to a truncated float, error at most 1 + ε in value, operations in constant time, and as the application exactly Dijkstra, with a proof of how the error adds up along the path. Their constant time comes with hashing, so only with high probability; two bitmaps over the classes do it deterministically. Three mantissa bits are their ε = 1/8, four are ε = 1/16. Thirty-year-old theory that authors of allocators, kernels and network packet schedulers have since reinvented more or less independently. TLSF from 2004 has a first- and second-level index, an exponent and a mantissa, and the Vulkan Memory Allocator uses it today with five mantissa bits, 32 classes per power of two.

I noted two things. That I was not thinking wrong, only thirty years late. And that it pays to search before naming the thing.

So

An offset allocator is a float and two bitmaps. The float squeezes a huge range of sizes into a few hundred classes with an error of at most a sixteenth, the bitmap turns "find the nearest non-empty class" into two instructions, neighbour links turn merging into two comparisons, and doubly linked lists keep it O(1) in a full class. Nothing is searched, everything is computed. A single character in the bitmap query, "successor or equal" instead of "successor", decides whether memory crumbles under load. And the fastest list operation is the one that does not happen.

Method

Times are from a laptop with criterion, median of three runs that agree within 1 %; the ratios matter, not the microseconds. Each implementation keeps one allocator, reset between iterations outside the timing. Allocation sizes come from a xorshift with a fixed seed, the same for both implementations. The cost of individual changes: perf stat (instructions, cycles, mispredictions) and perf annotate, A/B only within one binary. The timer wheel against BinaryHeap: 100,000 timers, dense distribution, 6 ns against 46 ns per operation. Dijkstra: an N × N grid with four neighbours, edge weights uniform in 1 to W, shortest paths from a corner, all queues must produce the same distances; "dense" means W ≤ 200, "sparse" W ≥ 500.

Long workload (examples/rd_first_churn.rs in holeinone): a million operations, log-uniform sizes, target occupancy 90 %, a failure frees a random allocation; percentages are the mean over three seeds. The best fit for comparison is an exact allocator over a tree of free ranges in a simplified simulation. Worst case of singly linked lists: n blocks of 64 B, free the odd ones, time freeing the even ones.