# Using Meta Alloc, Attempt 3 _2026 September_ Here's a fairly concrete design proposal. ## Block Alloc This is a simple manual alloc/free allocator, based on the Meta Alloc slabs/blocks, simply adding support for the more granular size classes we discussed earlier. It uses the coarse power-of-two Meta Alloc blocks for efficiently managing the backing memory. (Not needing to use mmap all the time.) It simply uses thread-local free caches, occasionally flushed to or refreshed from shared free-lists. (Meta Alloc does the same thing, just for larger blocks.) In short, Meta Alloc + Block Alloc simply offer a fairly simple, highly efficient, thread-safe, always O(1), multi-layered (slab -> block -> slot), completely general-purpose manual allocator with 56 size classes. It still has the caveats that it requires a size argument to `free()` so it knows which size class the freed slot belongs to, and inherits the Meta Alloc limitation of 256 GiB total heap / 16 GiB per slab. (Every four size classes, roughly; first few classes being exceptions e.g. 8-byte size class gets an entire slab for itself.) ## GC Alloc A fully concurrent (virtually "zero pause") mark-sweep tracing GC built on top of Meta Alloc, supporting the same 56 size classes as Block Alloc, with the following collection strategy: * For each Meta Alloc slab a "GC occupancy bitmap array" is allocated in virtual memory via `mmap()`. Each element (bitmap) of the array corresponds to a Meta Alloc block, whose index is easily calculated in few CPU instructions. * Using `gc_alloc()` sets bits in the GC occupancy bitmap for the current block, acquiring a new block if needed. * If there are interleaved uses of the manual Block Alloc `alloc()`, and `gc_alloc()`, then some bitmaps in the array remain zero, since Block Alloc takes a Meta Alloc block and dedicates it to itself. This isn't ideal, as it creates holes in the GC bitmap array, but should be acceptable, and doesn't break the design. * When the concurrent mark phase begins, a fresh, seconary, all-zero bitmap array is allocated. (Or the previous one explicitly zeroed out; may be faster than having fresh memory paged in. We can swap back and forth between two bitmap arrays.) * The new bitmap array is swapped in eagerly, so new allocations will set bits directly in the new one. Object graph tracing now begins, locating live objects, setting bits in the new bitmap array. Store barriers are used to safely handle concurrent object graph mutation, making sure the new bitmap array remains accurate. * When the mark phase has ended and concurrent sweeping begins, we walk through the original (old, stored away) bitmap array and the new (already swapped into place) bitmap array in parallel, using "AND NOT" to identify memory slots that were live before the mark phase (bit was set in original) but have been found not to be live anymore (bit not set in new). * If a block was completely full, but is now completely empty, we can free it back to Meta Alloc. (If only some slots were occupied and now the whole block is empty, we can't free it, since some of its unoccupied slots may be in a free-list.) * Otherwise, we `free()` individual "now dead" memory slots in it, which works similarly to the `free()` of Block Alloc, but putting the slots directly into the shared free-list of the size class, in chunks to decrease contention. (Mutator threads have thread-local caches anyway, filled from the global free-list in chunks, as an optimization.) * We need a way to identify what size class a block is for. Remember that the blocks supporting multiple size classes use a `u32` but don't need all bits in it; at most 25 bits are used for occupancy data. We can dedicate 2 bits at the "other end" of the integer to identify which of the (up to 4 possible) size classes the block is currently used for. * It may be good to double the size of each Meta Alloc block (i.e., smallest Meta Alloc size class becomes 256) so we can use `u64` bitmaps instead of `u32` which should boost throughput. * The old bitmap array that was used to identify "previously live" memory slots can be zeroed out and used as the new bitmap array in the next GC cycle. It's possible to add a compaction phase to this design, using load barriers with colored pointers and whatnot, like ZGC. It's unclear whether the CPU overhead would be justified; all it gives you is potentially improved spatial locality of objects in memory. ### Pinning Oh, and with regards to object pinning, Gemini gave me a really cool idea on how to do it efficiently: * A third bitmap array is used to represent pinned memory slots. * When the mark phase begins, it's used to "seed" the new bitmaps (immediately marking those slots as live) and also as GC roots. * To prevent the need to scan the entire pinned objects bitmap array which would typically be *very* sparsely populated, a "summary" bitmap array is used, where one bit represents a span of N slots. When pinning, the bit representing the relevant span is marked in the summary bitmap, so during scanning we can look at the summary and only scan the spans that have any bits in them at all. The span size N is probably best decided such that a bit represents a cache line i.e. 64 bytes i.e. 512 bits of the actual pinned objects bitmap array. Assuming that one uses a u32 for the first two block sizes, and u64 beyond that, our bitmap memory needs are: | Slab | Regular Bitmap | Summary Bitmap | |------|----------------|----------------| | 1 | 256 MiB | 0.5 MiB | | 2 | 128 MiB | 0.25 MiB | | 3 | 128 MiB | 0.25 MiB | | 4 | 64 MiB | 0.0125 MiB | | 5 | (halve it...) | (halve it...) | | ... | ... | ... | | SUM | ~640 MiB | ~1.25 MiB | That's a very lean summary bitmap. The regular bitmaps are bigger, and unfortunately there's three of them, but that still gives us: (3 * 640 MiB) / 256 GiB ~= 0.73% metadata overhead That's quite good I think. ### Explicit free As an optimization trick offered to application code that otherwise uses GC, there could be a special explicit `gc_free()` function. This would clear the GC occupancy bit for the given memory slot, and place it into the thread-local allocation buffer. (The same that's fed from the global shared free-list for a size class.) Clearing the occupancy bit ensures that the sweep phase doesn't touch it and the block it's placed in can't be freed to Meta Alloc. It's basically as if it had been swept by the GC, but lands immediately within the thread-local alloc buffer. If the local buffer is full, I suppose a chunk of it would be flushed into the shared free-list of the size class. Basically the same as Block Alloc and Meta Alloc. That's somewhat costlier than simply putting it into the local buffer, but should still remain under a microsecond I suppose. This way, an application that allocates and frees a bunch of objects in a tight loop could make sure that it keeps reusing the same few memory slots already in L1D cache. If the allocation happens at the start of the loop and the freeing at the end, then the programmer could have just used manual alloc/free, or used stack memory, and a smart optimizer should even detect this pattern and turn it into stack usage anyway... But if the loop crosses across module boundaries, conditionals are involved, or it frees some old objects at the start of the loop and then creates new ones or creates them at the end, I could see some situations where this is a useful API to offer. (Conditional free is probably the strongest case; in all other cases the object didn't need to be created with `gc_alloc()` to begin with, I think. Haven't thought hard enough about it.) ### GC handover An object initially allocated as a manually managed object could be simply handed over to the GC, if there is some logical reason to do such a thing. All this entails is setting the GC occupancy bit for the memory slot. That's literally all; the object is now GC managed. Of course, if the object acts as the root of a whole graph of objects that were manually allocated and are meant to be handed over to GC, then a traversal of that graph may be necessary to hand all of them over to GC.