diff options
Diffstat (limited to 'notes')
| -rw-r--r-- | notes/260922-use-alloc-3.md | 131 | ||||
| -rw-r--r-- | notes/index.md | 1 |
2 files changed, 132 insertions, 0 deletions
diff --git a/notes/260922-use-alloc-3.md b/notes/260922-use-alloc-3.md new file mode 100644 index 0000000..9ca98f7 --- /dev/null +++ b/notes/260922-use-alloc-3.md @@ -0,0 +1,131 @@ +# 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 an entire block comes out empty, we can release it directly back + to Meta Alloc. Otherwise, we perform a `free()` on individual "now + dead" memory slots which does something similar to Block Alloc, but + freeing directly to the shared free-list of the appropriate size + class, instead of thread-local caches. The 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. + +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. diff --git a/notes/index.md b/notes/index.md index 10bbd93..a9faf3d 100644 --- a/notes/index.md +++ b/notes/index.md @@ -43,3 +43,4 @@ * [Memory management of code](260825-code-gc.html) * [Using Meta Alloc](260826-use-alloc.html) * [Using Meta Alloc, Attempt 2](260920-use-alloc-2.html) +* [Using Meta Alloc, Attempt 3](260922-use-alloc-3.html) |