diff options
Diffstat (limited to 'notes/260920-use-alloc-2.md')
| -rw-r--r-- | notes/260920-use-alloc-2.md | 338 |
1 files changed, 338 insertions, 0 deletions
diff --git a/notes/260920-use-alloc-2.md b/notes/260920-use-alloc-2.md new file mode 100644 index 0000000..05289c3 --- /dev/null +++ b/notes/260920-use-alloc-2.md @@ -0,0 +1,338 @@ +# Using Meta Alloc, Attempt 2 + +<!--TOC--> + +_2026 September_ + +After chatting with people and LLMs a bit over the original design of +the general-purpose allocator and/or GC I'm planning to build on top +of Meta Alloc, some issues came up. + + +## Size Class Count + +For one, using mere 64-byte alignment even for very large allocations +means there's an ungodly number of size classes, because alignment is +basically the steps between size classes. Using 64-byte alignment on +any allocation between 16 KiB and 256 KiB means we have: + + (256 KiB - 16 KiB) / 64 Bytes = 15360 Size Classes + +Not even counting those under 16 KiB. This leads to two issues: + +* Way too many free-list roots per thread, since we want thread-local + cached free-lists. (Or free-arrays, meaning even more memory use.) + +* Potentially large amounts of freed memory never being reused due to + the application never requesting that exact size again. E.g. if an + allocation of 76800 bytes (64 x 1200) is made and then freed, then + one of 80000 bytes (64 x 1250), then one of 78400 bytes (64 x 1225), + all three would end up being separate allocations (no memory reuse + despite freeing in between) because they're different size classes. + +General-purpose allocators apparently tend to have four or eight size +classes between powers of two. That seems like a good middle ground +between too coarse and too fine-grained size classes. + +This comes out to be equivalent to using power of two steps for the +alignment of different size "categories" so to speak. Although we +start with 8-byte alignment for the first few categories, and only +begin doubling at a later point. + +Here's a table of how this maps to Meta Alloc slabs: + +<style> +td:first-child { font-weight: bold; } +td:not(:first-child) { font-family: mono; } +td { text-align: right; } +</style> + +| Slab | Block size | Alignment | Min Size | Max Size | Class Count | +|------|------------|-----------|----------|----------|-------------| +| 1 | 128 | 8 | 8 | 8 | 1 | +| 2 | 256 | 8 | 16 | 16 | 1 | +| 3 | 512 | 8 | 24 | 32 | 2 | +| 4 | 1024 | 8 | 40 | 64 | 4 | +| 5 | 2048 | 16 | 80 | 128 | 4 | +| 6 | 4096 | 32 | 160 | 256 | 4 | +| 7 | 8192 | 64 | 320 | 512 | 4 | +| 8 | 16 K | 128 | 640 | 1024 | 4 | +| 9 | 32 K | 256 | 1280 | 2048 | 4 | +| 10 | 64 K | 512 | 2560 | 4096 | 4 | +| 11 | 128 K | 1024 | 5120 | 8192 | 4 | +| 12 | 256 K | 2048 | 10240 | 16384 | 4 | +| 13 | 512 K | 4096 | 20480 | 32768 | 4 | +| 14 | 1024 K | 8192 | 41960 | 65536 | 4 | +| 15 | 2048 K | 16384 | 81920 | 131072 | 4 | +| 16 | 4096 K | 32768 | 163840 | 262144 | 4 | + +This means, for example, that Slab 3 hosts size classes 24 and 32, +Slab 4 hosts size classes 40, 48, 56, and 64, and Slab 10 hosts the +size classes 2048 + 512, 2048 + 1024, 2048 + 1536, and 4096. + +Slabs 1 and 2 are just for the size classes 8 and 16, respectively. + +This yields a total of 56 size classes. If for each size class we +have a `[32]u32` to represent the thread-local free slot cache, that +comes out to `56 * 32 * 4 = 7 KiB`, which seems reasonable enough. + +Maybe double or even quadruple that because for small sizes we may +want a lot of thread-local free entries; even 28 KiB would still be +acceptable per thread, I think. Although it may be smarter to use +explicit dynamic allocation at thread creation, because for larger +size classes, most of the space will remain empty, as they'll have +smaller upper limits for the thread-local caches. Anyway, details +will emerge during implementation; the point is that having 56 size +classes is vastly superior to having many thousands. + +Reuse between allocations close in size also dramatically improves, +without imposing *too* much alignment waste. Using the example from +before: The allocations of size 76800, 80000, and 78400 would all be +rounded up to size class 81920, so if you free one then allocate the +next, it will use the same memory. + + +## Small Size Alignment + +I had the idea of quickly increasing alignment to 16, and then 32, +using an alignment sequence like 8, 16, 32, 32, 32, 32, ... but that +forces every allocation just over 16 to be padded to 32 bytes, and +those just over 32 to be padded to 64 bytes. That hurts density too +much, so it's best to stick with 8-byte alignment for small classes. + +But what if there's a struct of 24 bytes, but with a 128-bit element +that needs 16-byte alignment? Should the allocator include logic to +insert padding to guarantee some alignment given as an argument? + +I think I have a neat, simple solution to this: + +First of all, size classes are isolated within their blocks. A whole +512-byte block will be used either exclusively for 24-byte objects or +exclusively for 32-byte objects. + +The size class 24 will not support 16-byte alignment guarantees. But +size class 32 inherently has 32-byte alignment, so all you need to do +is pad your struct to 32 bytes total, and then you decide whether to +put the 128-bit value in the first or second half; both halves have +16-byte alignment. + +I initially thought that SIMD operations perform better when e.g. a +16-byte object is aligned to 16 bytes, but apparently that is not so +with modern hardware; the start offset of the object could be *any* +byte at all, and the performance of the 16-byte SIMD op will be the +same so long as it's within a single cache line. + +Size class 32 will guarantee cache line isolation anyway, thanks to +the inherent 32-byte alignment; size class 24 guarantees neither any +alignment beyond 8, nor cache line isolation, but the improved memory +density from *not* adding superfluous padding should be the superior +choice anyway. + +If you really need an entire 24-byte object to always be within the +same cache line, you'll once again need to use explicit padding and +allocate 32 bytes for it. + + +## Occupancy Bitmaps + +For small size classes, we end up with potentially a *lot* of bitmaps +so it would be neat if we could minimize them as much as possible. + +The 128-byte blocks and 256-byte blocks, serving exclusively the size +classes 8 and 16 respectively, fit exactly 16 objects in a block, so +they should use 16-bit integers for their occupancy bitmaps. + +A 512-byte block may serve the size classes 24 or 32, so it can fit +either 21 or 16 objects. Other blocks fit 25, 21, 18, or 16 objects +depending on which size class the block currently serves. + +Since we want each block to map to a bitmap in an array with parallel +indexes, we must assume the largest bit count. And although we could +save a little memory by using tightly packed bit arrays, this causes +problems with concurrent access, as a single bitmap ends up possibly +crossing cache line or even byte boundaries. + +So, for the bitmaps of block sizes 128 and 256 we use u16 arrays, and +for the others we use u32 arrays. + +This may sound like it would require branching, but I think there's a +branchless solution to select between u16 and u32: + +* Shift-right the size class value such that 8 and 16 become zero and + anything beyond non-zero. + +* Use CMOV or arithmetic trickery to scale a bitmap index value by 2 + (u16) or 4 (u32) to get the raw offset from the starting address of + the bitmap array. + +* Always load a `u32` from that address. + +We need to handle an edge case where loading the very last bitmap may +load two bytes beyond what would be allocated for that bitmap array, +if it's one of the u16 arrays; this is solved by simply adding 1 to +the array length (another u16 i.e. 2 bytes at the end). + +(This last trick suffers from the unfortunate issue that sometimes we +may end up faulting in an entire page of memory just for 2 bytes that +will be ignored. I can't think of a solution to that, but it's still +better than doubling bitmap size, which would altogether double the +number of page faults from bitmap fetching.) + +At this point, we always have a u32, but depending on the size class, +we only care about the first 16, 18, 21, or 25 bits. How do we use +the u32 to represent the occupancy of 16, 18, 21, or 25 slots, while +ignoring remaining bits? + +Just do a bitwise NOT on the bitmap, then CLZ (aka TZCNT) to find the +index of the first unoccupied slot. Here we need a branch anyway, to +check if the block is full, so we just test the index value resulting +from the TZCNT against an `INDEX_MAX` which I guess we simply look up +from a static `[4]u8` indexed by `population_count(size_class) - 1`. +(A size class always has exactly 1, 2, 3, or 4 bits set, if you think +about it, due to powers of two divided into steps of 4.) + +This way, it doesn't matter whether the bits beyond the first 16, 18, +21, or 25 bits are all zero, or gibberish values. Any value between +`INDEX_MAX` and 32, returned from TZCNT, means the same thing: block +fully occupied; allocate next block. Hence the trick of loading 32 +bits even for the 16-bit bitmaps works without the need for any extra +masking operations, though that would be easy to add in a branchless +manner as well if needed. + + +## Block Identification + +During manual memory management, we never need to identify whether +some block out there is currently serving one or another size class. + +Alloc and free are both given the size class explicitly. (Or a size +from which the class is derived.) For each size class, there will be +a pointer to the current block from which allocations are served, so +alloc just checks if there's still room there and otherwise requests +another block. Free just puts the pointer into the thread local free +cache for that size class, or transfers a chunk of free-list entries +to the shared free-list for that size class. No need to ever know +what some block out there currently holds. + +What about GC operations? We'll probably want to move objects from +sparsely populated blocks to blocks with few vacancies, as a form of +defragmentation, so we can then free emptied blocks. + +But even then, we can learn about blocks serving various size classes +during the mark phase. When you have a pointer to object of size K, +fitting into size class C, you know that the block from which that +pointer originates currently serves C. Finding the address of the +block itself is a trivial integer division by a power of 2, i.e. a +shift-right operation. + +So, I don't think we need to store any metadata anywhere to mark the +size class that's currently active for a block. + + +## Object Index + +This hasn't changed from the original design: We need either 4 bits +identifying which Meta Alloc slab a 32-bit index points into, or we +use 2 bits to identify which one of four categories the index falls +into, which use different index scaling: + +1. Tiny: Slabs 1 & 2 of Meta Alloc, 8-byte indexing + +2. Small: Slabs 3 & 4 of Meta Alloc, 8-byte indexing + +3. Medium: Slabs 5 to 8 with 16-byte indexing + +4. Large: Slabs 9 to 16 with 32-byte indexing + +Given that slab 5 uses 16-byte alignment, and it keeps doubling from +there, this strategy still works. + + +## Free-Lists + +I think I'll do something very similar to Meta Alloc itself here, but +there's one significant issue. + +With Meta Alloc, the smallest allocation is 128 bytes, which can fit +16 x 4-byte indexes, so the globally shared free-list for each size +class can hold a whole array of free-list entries that can be very +efficiently transferred to and from thread-local free caches. + +With the general-purpose alloc, the smallest allocation size will be +only 8 bytes, which fits only two 4-byte indexes. + +I think I'll split the logic between small and large sizes, and maybe +use some monomorphization to reduce branching within the code if the +size class for an allocation is statically known. (E.g. allocating a +specific managed object type, like a closure, represented by a struct +of a specific size; or a 128-bit complex number; and so on.) + +In the most extreme case there may be a bunch of functions for the +different small sizes, like alloc8, alloc16, alloc24, etc. up to 64, +and then one taking a dynamic size argument. Or maybe that's way too +overkill just to reduce a little branching? We'll see. + +In any case, the split in the logic is as follows: + +* For size classes 80 and up, we can do it just like Meta Alloc does, + because we can fit 16 x 4-byte indexes into 80 bytes, plus 16 more + bytes for the "next" pointer and inline index count. + +* For smaller classes, we actually need the globally shared linked + lists to be used like a more traditional free-list where one entry + points to the next. But I'll still apply some optimization here to + minimize the amount of pointer chasing and synchronization work. + +To minimize pointer chasing / memory access, we can use a structure +such as the following: + + Root{ head_idx: u32, aba_counter: u32 } + | + v + HeadNode{ next_head_idx: u32, idx1: u32, ... idxN: u32 } + / / + _____/ _________________________/ + | | + | v + | Node{ idx0: u32, ... idxN: u32 } + | / + | _________________/ + | | + | v + | Node{ idx0: u32, ... idxN: u32 } + | / + | _________________/ + | | + | v + | Node{ ... } + | + | + v + HeadNode{ ... } + +What the heck is this? OK so, in Meta Alloc each "head node" has a +pointer (index) to the next head, a count of inline indexes, and the +array of inline indexes. Here we can't have the count and array as +there's not enough room, so instead the "contents" of the head are +themselves a linked list. + +But those contents are not a simple linked list either; each node of +this sub-linked-list may directly contain up to N-1 payload indexes. +Only the last (Nth) index, if not NULL, is followed. (Also the head +can hold N-2 direct payload indexes.) + +In the case of 8-byte allocations, the head node only has the 4-byte +next head index, and a single 4-byte index pointing to the start of +the sub-list; each entry of the sub-list then contains one payload +index and one continuation index. (N = 2) + +In the case of 16-byte allocations, the head has the next head index, +two direct payload indexes, and the sub-list continuation index; each +sub-list node has three payloads and one continuation. (N = 4) + +N increases in steps of 2, and goes up to 16, for size class 64. + +If you know a little about SIMD and branch prediction and whatnot, it +may be apparent why monomorphization over N is attractive here, but +maybe it wouldn't offer a significant improvement given modern branch +predictors; I'm not sure. |