Blocks with ownership: a novel approach to CPU and GPU memory in C++

Table of Contents

Introduction

Every C and C++ programmer knows the contract: malloc(size) returns a pointer, and free(ptr) takes it back. The size is missing from the second half, free gets only the pointer.

In case you’re unfamiliar with how allocators work there is a great short introduction video about it, you can watch it here:

Most people visualize allocation as something like this:

You call char* buffer = (char*)malloc(1); and you get:

… memory block, size 1 … buffer, exactly 1 byte long

But actually it looks like this:

… memory header your memory block memory footer … malloc(size) returns a pointer to here, and the block is usually larger than the size you asked for memory block the allocator actually allocated

Memory header and footer are usually allocator metadata which is used for allocator operations, optionally some memory tracking, and some mechanism to detect memory errors. Memory footer is not common unless allocator has some memory corruption detection mechanisms.

Memory header is usually where malloc stores the size of the block in order for free(ptr) to work. The allocator knew how much memory it handed out, the caller knew how much it asked for, but free gets only the pointer, so the allocator has to write the size down somewhere, usually in a header in front of the block, and find it again later. std::allocator passes the size back, but the rest is the same: an allocation is a bare pointer, and everything else about it, how big it really is, how it’s aligned, who allocated it, lives somewhere else.

In 2015 Andrei Alexandrescu proposed a different contract: an allocation is not a pointer, it’s a block, the pointer and the size together. The allocator returns the block, the caller keeps it, and hands it back when it’s done. Once allocators speak in blocks they can be small, do one thing, and be composed into larger ones.

This post is about bx::Blk, an implementation of that idea taken further than the talk. The block also knows which allocator it came from, it can’t be copied or freed twice by accident, when it’s invalid it says why, and it describes GPU memory the same way it describes CPU memory. On top of it there is a set of composable allocators, allocation debugging, memory tracking and a general purpose heap.

History of composable allocators

Composition came from C first. Kiem‑Phong Vo’s Vmalloc (1996) splits an allocator into a method, how blocks are handed out (Vmbest, Vmpool, Vmlast), and a discipline, where raw memory comes from (Vmdcsystem for mmap, sbrk or Win32). Any method works with any discipline, and debugging is just another method: Vmdebug checks for overruns and double frees, Vmprofile records usage.

Emery Berger, Benjamin Zorn and Kathryn McKinley’s Heap Layers (PLDI 2001) brought it to C++. Each layer is a template that inherits from the layer below, and an allocator is a stack of layers. Composed allocators matched hand‑written ones, and Hoard and DieHard are built from it. The same year Andrei Alexandrescu’s Modern C++ Design introduced policy‑based design, the mechanism his allocators would use fourteen years later, and Loki’s small object allocator.

Also in 2001, Jeff Bonwick and Jonathan Adams added magazines and vmem to the Solaris slab allocator. Magazines are per‑CPU caches of free blocks. Vmem allocates arbitrary resources, ranges of integers, so it never touches what it manages.

Game developers kept running into the limits of std::allocator. Paul Pedriana’s N2271 (2007) says std::allocator was the largest reason EA wrote EASTL.

Alexandrescu’s talk

Alexandrescu presented composable allocators at CppCon 2015, in the “std::allocator Is to Allocation what std::vector Is to Vexation” talk:

In the talk he introduces two main ideas:

  • Allocation returns Blk { void* ptr; size_t length; }. The allocator says how much it gave, the caller keeps it and hands it back, and the allocator doesn’t have to store the size.

  • Allocators are small parts with the same interface, allocate, deallocate, expand, reallocate and owns, put together with templates. FallbackAllocator<Primary, Fallback> asks Primary::owns to decide who frees a block. Segregator splits by size, Bucketizer makes size classes, AffixAllocator adds a prefix or suffix for metadata, and StatsCollector counts.

Alexandrescu implemented the whole thing in D as std.experimental.allocator, released with D 2.069 in November 2015, where a block is a void[] slice. It is the most complete implementation of the talk, and it is still in experimental.

In C++ there are AllocatorBuilder, allocators and KTL, which reproduce the building blocks from the talk, and foonathan/memory, which passes memory_block between allocator layers and hands users plain pointers. The standard took one piece: allocate_at_least in C++23 returns { ptr, count }.

On the GPU side, AMD’s Vulkan Memory Allocator and D3D12 Memory Allocator have virtual blocks, and Sebastian Aaltonen’s OffsetAllocator is TLSF for offsets. They hand out offsets into memory the CPU can’t touch and keep metadata outside of it, each with its own API, separate from how the same program allocates CPU memory.

bx::Blk

The Blk from the talk is two fields, struct Blk { void* ptr; size_t length; }, and it’s a plain value. bx::Blk keeps the idea, the caller holds the block and hands it back, and changes almost everything else about it.

Layout

 1struct Blk                            // 24 bytes, 64-bit layout
 2{
 3    uint64_t ptr;                     // pointer, or offset into GPU memory
 4
 5    uint64_t size            : 40;    // size of block, up to 1TiB
 6    uint64_t log2Alignment   :  5;    // alignment of block
 7    uint64_t cpuAccessible   :  1;    // can CPU read and write this memory?
 8    uint64_t allocatorOp     :  3;    // what the last operation did
 9    uint64_t allocatorHandle :  8;    // which allocator returned the block
10
11    uint32_t bookKeeping;             // private data of the allocator
12    uint16_t slotIndex;               // routing inside of composed allocator
13    uint16_t unused0;
14
15    uint32_t locationIdx;             // only with memory tracking, 32 bytes
16    uint32_t unused1;
17};
only with memory tracking bytes bits 0 8 16 20 22 24 28 32 ptr bit fields bookKeeping slot Index unused locationIdx unused size : 40 5 3 8 unused log2Alignment allocatorHandle cpuAccessible : 1 allocatorOp

What the fields are for, compared to pointer and length in the talk:

  • ptr is 64 bits on every platform, including 32‑bit ones, because it’s not always a pointer. For GPU memory it’s an offset.

  • size is the size the allocator actually gave, which can be more than what was asked for.

  • log2Alignment is there because alignment is something the caller knows at allocation, and has to repeat on every resize and free. Now it’s in the block.

  • allocatorOp says what happened to the block last: no‑operation, alias, allocate, free, grow, realign, or truncate. There is one entry point, realloc(blk, size, alignment), and the caller can tell if the block grew in place or moved.

  • allocatorHandle is the allocator the block came from.

  • bookKeeping and slotIndex belong to allocators. Metadata that an allocator would write into a header in front of the memory can live in the block, which matters when the memory is on the GPU and there is nowhere to write the header.

Unique pointer without automatic release

This is the largest change in behavior. In the talk a block is a plain struct, and nothing stops this:

1Blk a = allocator.allocate(100);
2Blk b = a;               // copy of metadata
3allocator.deallocate(a);
4allocator.deallocate(b); // double free, and `b` looked completely valid

The same happens when a block is resized and the old copy is kept around, the old copy has the wrong pointer or the wrong size, and it’s the caller’s job to never use it.

bx::Blk behaves like std::unique_ptr, there is always only one owner of the block:

  • It can’t be copied, only moved, and moving invalidates the source.

  • Every function that changes a block takes it as Blk&& and returns the result. The block that went in is invalid when the function returns. If a resize fails, the original block is what comes back, marked as no‑operation.

  • It’s [[nodiscard]], the result can’t be dropped on the floor.

In code:

1bx::Blk blk = bx::alloc(allocator, 100);
2blk = bx::realloc(bx::move(blk), 200); // old block is gone, there is only
3                                       // the new one
4blk = bx::free(bx::move(blk) );        // `blk` is now invalid, reason: freed
5
6bx::Blk copy = blk;                    // doesn't compile
7bx::free(blk);                         // doesn't compile

Unlike std::unique_ptr, Blk doesn’t free memory when it goes out of scope. Allocation and release stay explicit, there are no frees hidden behind a closing brace, and without a destructor Blk is trivially relocatable, 24 bytes that containers and allocators can move around with memcpy. What unique_ptr gives for free at scope exit is done by containers that own a block: ArrayT, HashMapT, UniquePtrT.

Forgetting to free is caught another way. With memory tracking turned on, Blk gets a destructor that doesn’t free, it asserts if the block that’s going away still owns memory, and reports where that block was allocated. A leak is reported at the place where the block is lost, not as a list of leaked pointers at exit.

When more than one piece of code needs to look at the same block, the copy has to be asked for: Blk(Copy, blk) makes a non‑owning alias. It’s marked as AllocatorOp::Alias, it can’t be resized or freed, and it’s not counted as a leak.

Memory tracking changes the size of Blk, so Blk lives in an inline namespace named after BX_CONFIG_MEMORY_TRACKING. Code built with tracking and code built without it doesn’t link, instead of crashing at runtime.

The block knows its allocator

In the talk the allocator is not part of the block. The caller has to remember which allocator a block came from, and composed allocators find the owner by asking each part owns(blk).

bx::Blk carries an 8‑bit handle of the allocator that returned it. free(blk) and realloc(blk, ...) don’t take an allocator argument, there is no header in front of the memory, and no lookup by address.

The handle is 8 bits because it has to fit into the block next to the size and alignment, and that makes 256 handles. A handle is an index into a table of allocators, so getting from a block to its allocator is one read from an array. Allocators get a handle when they’re created, and handle 0 is the process default, which is the heap until it’s set to something else with setDefaultAllocatorBlk.

256 sounds small, but handles are for allocators, not for allocations, and a program has few allocators. The whole bx heap takes about 12. The limit is also on allocators that are alive at the same time, not on how many are created: when an allocator is destroyed its handle is released, and released handles are reused in turn. Running out of handles is an assert, and code that creates and destroys allocators all the time should reset them instead.

Reuse of handles is why an allocator has to outlive every block it returned. A block that is still around after its allocator is gone carries a handle that sooner or later belongs to another allocator. With memory tracking, destroying an allocator that has live blocks is an assert.

Some allocators are never destroyed, they live as long as the process. Those can be marked with setAllocatorPermanent, and a permanent handle is never given to another allocator. That handle means the same allocator for as long as the process runs, so the pointer to the allocator can be cached instead of looked up. The heap marks its own allocators as permanent. The default handle is not permanent, because it can be pointed at another allocator.

Containers get smaller because of it. They take a one byte AllocatorHandle instead of an allocator pointer, and ArrayT or UniquePtrT store nothing but their Blk.

Invalid blocks say why

A null pointer says that something failed. An invalid Blk says what: allocation failed, no block large enough (but smaller ones are available), resize failed, realign failed, not supported, or the block was freed. A block that was freed is distinguishable from one that was never allocated.

One entry point

The allocator interface in the talk has allocate, deallocate, reallocate and expand. A bx allocator has one function, realloc(blk, size, alignment). An invalid block going in is an allocation, size 0 is a free, anything else is a resize, and allocatorOp in the block that comes back says which one happened.

The functions users call are built on top of it, and each comes in three forms:

  • tryAlloc, tryRealloc report failure through Error*, and the caller has to deal with it.

  • alloc, realloc, free stop on failure.

  • Unchecked variants skip the checks, for hot paths where the caller guarantees the preconditions.

Not all code can hold a 24 byte block. For code that can only keep a pointer there are allocPtr, reallocPtr, freePtr and BX_NEW_PTR/deletePtr, which store the Blk in a header in front of the pointer. It’s what malloc does, but only where it’s asked for.

Block allocators and old pointer based AllocatorI can’t be confused. Passing one where the other is expected doesn’t compile.

Allocators

Allocators are plain classes without virtual functions, composed with templates, so the calls between the parts inline. The parts:

First fit and TLSF don’t own the memory they manage. Memory is added to them and removed from them as slabs (addSlab, removeUnusedSlab), and that is the same interface whether the slab is RAM or a GPU heap.

CPU and GPU memory

In the talk a block is CPU memory, void*, and allocators are free to write into memory they manage. In bx::Blk the cpuAccessible bit says if ptr can be dereferenced. When it can’t, ptr is an offset, allocators keep all metadata outside of the memory, and debug features that touch memory are skipped.

That’s all it takes for the same allocators and the same composition to work on both. TLSF, first fit, or frame ring sub‑allocate a GPU heap the same way they sub‑allocate RAM. bgfx does exactly this:

  • D3D12 and Vulkan renderers have one TwoLevelSegregatedFitAllocatorT per kind of memory. Each ID3D12Heap or VkDeviceMemory is added as a slab the CPU can’t access, with the index of the heap in the upper bits of ptr. Heaps that are no longer used are removed and given back to the driver.

  • Dynamic vertex and index buffers are ranges of a larger GPU buffer, handed out by FirstFitAllocatorT, not TLSF. It’s a different allocator behind the same slab interface, each GPU buffer is added as a slab.

This is how a VkDeviceMemory goes in and an allocation comes out in bgfx’s Vulkan renderer, simplified:

 1// Device memory is added as a slab. Index of the slab is in the upper 32 bits
 2// of `ptr`, and the block is marked as not accessible by the CPU.
 3allocator.addSlab(
 4      bx::Blk(uint64_t(slabIdx + 1) << 32
 5    , size
 6    , 0
 7    , false
 8    , bx::AllocatorOp::Allocate
 9    ) );
10
11// Allocation is a block. Which device memory, and the offset into it,
12// are both in `ptr`.
13bx::Blk blk = allocator.alloc(requirements.size, requirements.alignment);
14
15const uint16_t slabIdx = uint16_t( (blk.ptr >> 32) - 1);
16const uint32_t offset  = uint32_t(blk.ptr);

Nothing is written into the device memory, what TLSF needs to free the block later is in the block’s bookKeeping.

Memory tracking and debugging

With BX_CONFIG_MEMORY_TRACKING every allocation records where in the source it was made. The location is a defaulted argument of alloc, like std::source_location, so there are no macros at call sites. Each location keeps the number of live blocks and bytes, their peaks, the number of operations, and the call stack of the first allocation from it, and all locations can be enumerated at any time. The block points to its location, which is how the leak assert in ~Blk knows what to report. With tracking compiled out Blk goes back to 24 bytes with no destructor.

Debugging tools are allocators too, and they’re added by composition, around any allocator and at any level:

  • StatsAllocatorT counts bytes, blocks and operations, and is thread safe.

  • DebugClearAllocatorT fills new memory with 0xcd and freed memory with 0xdd.

  • DebugStompAllocator places each block against a guard page, after the block to catch overruns or before it to catch underruns, so out of bounds access and use after free trap at the instruction that did it (see Memory Stomp Allocator).

General purpose heap from the same parts

bx::malloc, realloc, alignedAlloc, free and usableSize run on a heap composed from the same block allocators. It’s a test of the whole idea: if composition from blocks had a cost, this is where it would show.

The heap has three modes, picked with setHeap:

  • Throughput. Threads own their pages.

  • Footprint. Threads share pages, and thread caches are bounded.

  • Balanced, the default. Blocks up to 8KiB come from pages owned by the thread, larger ones from shared pages.

Where the heap gets its memory from is also an allocator, set with setHeapUpstream.

Performance

All bx results below are from the balanced heap, which is the default. The throughput and footprint modes are not represented.

mimalloc‑bench

mimalloc‑bench is the benchmark that matters the most, because it’s based on reality. It runs real, familiar open source programs, redis, rocksdb, lean, espresso, cfrac, a Linux kernel build, next to the allocator stress tests, with each allocator loaded as the malloc of the process.

For each test an allocator gets the best result divided by its own, and the score is the geometric mean over all tests times 100, so 100 means the best on every test. Overall is time and memory weighted equally:

allocator time memory overall
mimalloc 1.8.2 90.0 82.0 85.9
snmalloc 0.7.6 90.0 69.8 79.2
bx 83.9 74.7 79.2
rpmalloc 2.0.1 82.9 70.9 76.7
mimalloc 2.1.2 84.5 68.1 75.9
glibc 2.39 61.4 81.2 70.6
jemalloc 5.4.0 77.1 61.7 69.0
mimalloc 3.6.0 87.2 45.8 63.2
tcmalloc (gperftools 2.18) 67.1 55.7 61.1

bx is in the leading group. It’s 1.37x faster than glibc, about 7% behind mimalloc 1.8 and snmalloc, about even with mimalloc 2 and 3 and rpmalloc, and ahead of jemalloc and tcmalloc. Only glibc and mimalloc 1.8 use less memory overall. It ties for the fastest on the kernel build, and trails the most on small block churn, where sh6bench is about 2x behind the fastest.

rpmalloc‑benchmark

rpmalloc‑benchmark is synthetic. Threads do nothing but allocate and free blocks of random sizes, and hand some of them to other threads to free. A program that only allocates doesn’t exist, so the differences it shows are much larger than what a real program would see, and it should be read as a stress test of the allocator and not as a prediction. It’s useful for comparing against platform allocators, because it runs everywhere. Three ranges of block sizes at 1, 4 and 8 threads:

platform platform allocator bx is faster by
Windows, Ryzen 9 7950X Windows heap 1.6–54x
Linux, i9‑9900K glibc 2.39 2.6–4.7x
macOS, Apple M4 libmalloc 3.1–9.1x
iPhone 16e, A18 libmalloc 4.2–8.5x
iPhone 17 Pro Max, A19 Pro libmalloc 3.6–15x
Pixel 9a, Tensor G4 Scudo 3.9–77x

Peak memory is close to even, except on Linux where glibc uses 4–14% less. Against the other allocators on Windows, scored the same way as above, bx gets 90.5 for speed and 86.8 for memory, rpmalloc 75.5 and 70.7, mimalloc 60.0 and 83.7, snmalloc 57.0 and 79.8, tcmalloc 48.8 and 69.5.

GPU sub‑allocation

bx allocators against Vulkan Memory Allocator and D3D12 Memory Allocator, both as virtual blocks over a 256MiB virtual heap, with three workloads: churn of live blocks, transient blocks of one frame, and three frames in flight. For 256 allocations and 256 frees of each, bx TLSF, the one bgfx uses, takes 25.6µs in total, VMA 32.1µs and D3D12MA 31.4µs.

Conclusion

Blocks are not new, composable allocators are not new, and neither is any single allocator described here. Blocks with a size come from Alexandrescu’s talk, composition from Vmalloc and Heap Layers, and TLSF, magazines and GPU sub‑allocators all existed before. What is novel is what bx::Blk does with the block. As far as I know, no other implementation makes the block the single owner of its memory, puts the allocator into the block, or manages CPU and GPU memory with the same blocks and the same allocators, and none has built a general purpose malloc replacement out of blocks.

None of this is paid for with performance. On real programs the general purpose heap composed from these parts is in the same group as allocators that do nothing else, and 1.37x faster than glibc.

It’s not an experiment. It landed in bx, and bgfx’s D3D12 and Vulkan renderers sub‑allocate GPU memory with the same allocators.

References

Further reading


- One more thing...


My mission with bgfx is to empower game developers by providing a cross-platform, graphics API-agnostic rendering library that simplifies porting games across diverse platforms, ensuring seamless performance and compatibility without engine lock-in.

If you like this article and support my mission please consider becoming a sponsor! ❤️