# Free-List Improvement _2026 October_ Here's a set of optimizations for small size classes. ## Bitmap in Free-List Instead of referencing individual slots within Meta Alloc blocks, free-list entries of the GC could consist of: Inside Block 0x557799A0: Slot 0x557799A5 = { free: u32, next: u32, } The pointer to the free slot would be an implicit reference to the containing block. The field `free` is a bitmap declaring which slots of that block (other than this one) are free. Thus, one entry of the free-list can declare up to 31 empty slots. (If all 32 were empty, the whole block would have been released to Meta Alloc.) That's for the smallest two size classes, which fit 32 elements at most per block. Starting from size classes that can fit more, the bitmap can be a `u64`. At some point, it stops making sense to use this strategy, since you don't want a single thread to hog an entire block, given the massive sizes they have for the bigger size classes. A sane cutoff would probably be the fourth block size. It serves the size classes up to 64 bytes, and the block size is 2048, so a thread will hog at most 2 KiB, and temporally close allocations will also be spatially close, sharing a page; and if you're lucky, a cache line. So, for the first two block sizes, holding up to 32 slots each, we would use the struct above. For the next two block sizes, we would use a version where the `free` field is a `u64`. Starting from the fifth block size, where the smallest hosted size class is 80 bytes, Meta Alloc style chunky free-list entries can be used again. I've not made clear whether this design is only for global free-lists of small size classes, or also the thread-local "free-cache" arrays. Both should work. In the local arrays, we can pre-link the entries, despite keeping them in an array, so later we only need to push one node onto the list. Oh, that's assuming support for manual freeing, by the way. If that weren't part of the design, then the local arrays would only ever be filled from the global free-list, while the GC recycles memory into that global free-lists, and so on. One way cycle. But I'd like to support manual free even of GC-managed memory, for those who need a performance boost. ## Manual free How to best support one by one freeing of objects in blocks, when the entries in our local free-cache arrays correspond to entire blocks? Each free action must check whether any of the existing entries are for the same block, and manipulate the bitmap of that. It should be possible to make this highly efficient with SIMD operations, so that there's still a benefit to this. And then, if no entry in the array matches, do we flush? At this point I realize that may be a bad idea, because it's just too easy to use it wrong. If you fill the array with entries for blocks that each have a single free slot, then the next free would have to flush a bunch of single-slot entries into the global free-list. Perhaps it's best to transparently ignore manual freeing if the local free-cache array is full, and the user calls `free()` on a slot that isn't in any of the blocks represented by the free-cache entries. ## Batch-update 'Allocated' Imagine a thread has just acquired a 256-byte block from Meta Alloc, and used 120 of them to serve 15 allocations of 8 bytes. Then the GC runs, and 12 of them are dead already. Is it really worth adding a free-list entry for just 12 slots, when our bitmap strategy allows representing up to 31 freed 8-byte slots? For small size classes, the allocator shouldn't immediately update a bit in the Allocated Bitmap. It should do so when the current Meta Alloc block is filled up and a new one is being requested. Given this behavior, we wouldn't ever end up with partially-filled bitmaps in the Allocated Bitmap, which makes one wonder whether it could be drastically cut down in size (one bit per block) but that won't work for the following reason. Say a block was filled up, and later, the GC discovers that 30/32 of the objects in it are dead. Without a compaction strategy, we have two options: 1. Don't free any object in the block. Hope that, on a subsequent GC cycle, the remaining objects will be dead, so it can be collected altogether. This is not good, as a single live object could keep the whole block uncollected forever. Multiply by N blocks and we get tons of wasted memory (enormous fragmentation). 2. Create a free-list entry for those 30 slots of the block. Later, some thread will take that entry, use up the 30 slots, and now it needs some way to register this in the Allocated Bitmap, so we do need slot-level granularity in the Allocated Bitmap after all. (The other 2 slots may or may not still be allocated!) There's an interesting implementation detail that comes up here, by the way: When partially free blocks like that are acquired for use, their original occupancy status must be remembered, so once we used all the slots that were still free when we acquired it, we set only the corresponding bits in the Allocated Bitmap. As for the other slots (in this example, the remaining 2/32) they may actually be freed at any point, but we don't know that; we must only record the changes that we make, with an atomic RMW on the Allocated Bitmap. Essentially, the 2/32 and 30/32 slots get split into two independent sets of slots. But if at any point they're all allocated at the same time, they can merge again. That is: 1. Some thread acquires the fresh block. It "remembers" the initial state of all slots being free. (This is just because it would be simplest to have one implementation for full & partial blocks.) 2. Once all 32 slots are used up, it commits the 32-bit update to the Allocated Bitmap and acquires another. 3. At some point, 30/32 slots are collected, and inserted into the global free-list with the structure explained further up in the first section of this note. 4. At some other point, the other 2/32 slots have the same happen. 5. Some thread acquires the 30/32. It "remembers" that only 30 were free when acquired. 6. Some thread acquires the 2/32 and does the same. 7. When the 30 slots fill up, the corresponding bits in the Allocated Bitmap get updated. 8. Likewise at some point for the other 2 slots. Consequently, the Allocated Bitmap now once again has a full 32-bit allocated block. 9. Now if all objects in the block die at once, it can be collected entirely, or it could be split up again in some way. (Some of the listed events can occur in different order; 4 to 8 can pretty much happen in any order, I think.) The worst-case scenario for this strategy is that we keep collecting singular dead objects in tons of separate blocks. At that point, it basically degenerates into a basic linked-list style free-list with one slot per entry. As a mitigation strategy: The GC could refuse to free objects in a block if they would form a free slot set smaller than N. The value should probably be very small, to cap worst-case memory waste to N-1 slots that remain unfreed. At N = 5 it's 4/32 = 12.5%; at N = 3 it's 2/32 = 6.25%; either choice would be defensible, or exactly in between with N = 4 for 3/32 = ~10%. When a thread takes an entry from the global free-list, it gets at least N slots to use, but hopefully many more on average. One could combine this with a strategy akin to the chunky free-list entries of Meta Alloc, for size classes greater than 8 bytes, but it probably isn't worth the complexity. ## Summary So, we have a split strategy depending on size class: 1. Up to size class 64, corresponding to the first four Meta Alloc slabs / block sizes, we use the bitmap-based free-list entries. 2. For larger size classes, we use Meta Alloc style chunky free-list entries with embedded pointers to N other free slots. The second is nothing new, but let's sum up the first and what it entails more broadly. * Each thread has a "current block" from which allocations are served and an "original occupancy" bitmap declaring how it started out, as well as the "current occupancy" bitmap to know what slot is next in line to be given out and when the block is full. * When full, the diff between the original and current bitmap is used to perform an atomic update to the Allocated Bitmap, and the next block is acquired, either from the thread-local free-cache or the global free-list. * The thread-local free-cache can be filled by manual freeing as an optimization for advanced users. The expectation is that objects allocated together are freed together, so freeing entails a lookup for existing entries corresponding to the block containing the slot being freed, so we just update the bitmap of that entry. The free call is silently ignored if the free-cache array is full and no entry for the containing block was found. * The local cache can be filled in chunks by following N links in the global free-list, and updating the head pointer to a corresponding later node; thus we steal N nodes with one atomic CAS. (This may not be worth it? Not sure.) * When the GC sweeps, there's a lower limit N, below which it refuses to free slots in a block, so it doesn't add free-list entries with very few slots.