From 264ce15d7ce9069096842fe653a114f039bd421c Mon Sep 17 00:00:00 2001 From: Taylan Kammer Date: Tue, 28 Jul 2026 11:42:45 +0200 Subject: Update last note. --- notes/260727-alloc.md | 75 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 75 insertions(+) diff --git a/notes/260727-alloc.md b/notes/260727-alloc.md index 73af511..0988ee7 100644 --- a/notes/260727-alloc.md +++ b/notes/260727-alloc.md @@ -125,3 +125,78 @@ or two specific size classes. So I guess the main heap will need a totally different strategy. The main heap will also be the main one needing a sophisticated garbage collector, so I guess it's OK to not use this super simple core allocator for it. + +## Addendum A + +To prevent false sharing issues, it may be best to have 64 bytes be +the smallest size class. Objects smaller than this should generally +reside on the stack, or be allocated from some kind of pool; remember +again this isn't for regular language-domain arbitrary heap objects. + +Sticking to 16 size classes, this makes the largest 2 MiB, of which +there can only be 2048, which is fine. Reducing to 8 size classes +would make the biggest 8 KiB, which is no good. + +The 32-bit index, by the way, should use a scaling factor (say 8, so +it's zero-cost via the LEA instruction) so it can't overflow, even if +the 4 GiB slab for a size class is saturated. This means we could go +up to e.g. 16 GiB slabs (for a total of 256 GiB of vmem) which fully +eliminates concerns about ever saturating a size class. + +This also enables a remarkably clean strategy for checking for OOM: +Use a *signed* 32-bit integer for the watermark, and let it overflow +to negative when the last slot of a size class is used. Now we only +need to check if it's negative before an allocation. + +The new 16 GiB slab size means we can have 8192 active slots of the +biggest 2 MiB size class, which is even finer than 2048. + +New Summary: + +* 256 GiB total vmem divided into 16 slabs of 16 GiB. + +* Size classes go from 64 bytes to 2 MiB. + +* The watermark of each slab is kept track of via a 32-bit signed int + using 8-byte units for "free" shifting in certain CPU instructions + on x86-64 and AArch64. + +* Atomic fetch-and-add on the watermark for fresh allocations; check + the fetched value for a negative to decide if we raise OOM due to + slab saturation. (Fetch-and-add returns *previous* value before + addition.) So, every last slot of a 16 GiB slab is usable, and + checking for OOM is a simple less-than-zero check. + +* The biggest size class of 2 MiB can have up to 8192 active slots; + much more than what we would ever realistically need. Just make + sure not to abuse big size classes based on the logic: "It's just + virtual memory anyway; I can reserve lots of 2 MiB slots and only + fill each as much as it needs." No, use a smaller size class; for + example, if you're allocating stacks for green threads or such, of + which there could be millions, use 8 KiB dynamic stack segments or + some strategy like that. + +* Thread-local free-list caches hold up to 64 nodes, transferred in + chunks of 32 to and from the global free-list for the given size + class. Note this is for native threads, not green threads. The + green threads don't need thread-local caches since each can only + execute within one specific native thread. + +The previously discussed "low-cost high-yield" optimization of simply +decrementing the watermark if the last allocation is freed does not +actually make sense in a multi-threaded context with thread-local +caches, so scrap that. However, the following are possible: + +* We might eventually implement an expensive cleanup procedure that + checks whether the last N slots of a slab are currently free by + traversing the global free-list, removing them from the free list, + and accordingly decreasing the watermark. Probably overkill, but + possible. + +* If we use a GC strategy involving a global STW, we could even do + that in a way that involves all thread-local free list caches, just + as an extra "side mission" of the GC; these slabs are not otherwise + subject to any kind of GC since they are not for the regular heap. + +If either or both of these is implemented, we could then also free +memory back to the OS if a slab watermark drops significantly. -- cgit v1.2.3