diff options
| -rw-r--r-- | notes/261002-free-bitmap.md | 218 | ||||
| -rw-r--r-- | notes/index.md | 1 |
2 files changed, 219 insertions, 0 deletions
diff --git a/notes/261002-free-bitmap.md b/notes/261002-free-bitmap.md new file mode 100644 index 0000000..eebccc8 --- /dev/null +++ b/notes/261002-free-bitmap.md @@ -0,0 +1,218 @@ +# Free-List Improvement + +<!--TOC--> + +_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. diff --git a/notes/index.md b/notes/index.md index de4675a..c3d3387 100644 --- a/notes/index.md +++ b/notes/index.md @@ -2,6 +2,7 @@ ## 2026 Q3 +* [2026-10-02: Free-List Improvement](261002-free-bitmap.html) * [2026-09-29: Pointer Color Bits](260929-color-bits.html) * [2026-09-25: No-STW SATB](260925-gc.html) * [2026-09-23: Green Tea](260923-green-tea.html) |