diff options
Diffstat (limited to 'notes/260826-use-alloc.md')
| -rw-r--r-- | notes/260826-use-alloc.md | 207 |
1 files changed, 207 insertions, 0 deletions
diff --git a/notes/260826-use-alloc.md b/notes/260826-use-alloc.md new file mode 100644 index 0000000..5797f98 --- /dev/null +++ b/notes/260826-use-alloc.md @@ -0,0 +1,207 @@ +# Using Meta Alloc + +<!--TOC--> + +_2026 August_ + +The design and implementation of Meta Alloc is mostly complete. + +* [Documentation](/zisp/doc/0/A-meta_alloc.html) + +* [Implementation](https://git.tkammer.de/zisp/tree/src/zisp/gc/meta_alloc.zig) + +Some tweaks needed to make it work across operating systems, but the +basic principles, data structures, and algorithms, are all sound and +should offer peak performance for coarse allocations. + +The only problem is it's a bit too coarse. The smallest size class +being 128 bytes, and size classes going up in exact powers of two, +means you would suffer ridiculous amounts of internal fragmentation +from using it directly. + +Need a 16-byte heap object? Say hello to 112 bytes of padding. Want +to allocate an array of 300 bytes? Best I can do is 512, so there's +212 wasted bytes. Ridiculous. + +This is an intentional design strategy to offer extreme simplicity, +and efficiency, which you can use as a basis to implement various +other allocation strategies on top. Hence "Meta" Allocator. + + +## Block Alloc + +So here's an intermediate allocator based on Meta Alloc. This first +originated from thoughts about how to directly implement a GC on top +of Meta Alloc, but as I'm writing this, I realize it may be cleaner +having another intermediate layer. Or maybe not; we'll see. + +Block Alloc supports allocations of any size, with fairly reasonable +internal fragmentation limits. There are two things controlling the +amount of fragmentation: + +1. Alignment + + * Objects up to 64 bytes in size have 8-byte alignment. + + * Objects 65 to 1024 bytes in size have 16-byte alignment. + + * Objects 1025 bytes to 16 KiB in size have 32-byte alignment. + + * Finally, those up to 256 KiB in size have 64-byte alignment. + + Those are four-step jumps in powers of two, making it trivial to + calculate the alignment. + +2. Block placement + + * Meta Alloc slots are used as Blocks. + + * An object is put into the smallest Block size that can hold at + least 16 of those objects, taking into account its alignment. + + * E.g.: + + * up to 8 bytes -> 128-byte Block (smallest Meta Alloc class) + + * up to 16 bytes -> 256-byte Block + + * up to 32 bytes -> 512-byte Block + + * ... + + * up to 256 KiB -> 4 MiB Block (largest Meta Alloc class) + + * Objects beyond 256 KiB are served by direct `mmap()` calls. + +Maybe it's better to explain this with a table: + +<style> +td:first-child { font-weight: bold; } +td:not(:first-child) { font-family: mono; } +</style> + +| Slab | Block size | Max obj. size | Alignment | +|------|------------|---------------|-----------| +| 1 | 128 | 8 | 8 | +| 2 | 256 | 16 | 8 | +| 3 | 512 | 32 | 8 | +| 4 | 1024 | 64 | 8 | +| 5 | 2048 | 128 | 16 | +| 6 | 4096 | 256 | 16 | +| 7 | 8192 | 512 | 16 | +| 8 | 16 K | 1024 | 16 | +| 9 | 32 K | 2048 | 32 | +| 10 | 64 K | 4096 | 32 | +| 11 | 128 K | 8192 | 32 | +| 12 | 256 K | 16 K | 32 | +| 13 | 512 K | 32 K | 64 | +| 14 | 1024 K | 64 K | 64 | +| 15 | 2048 K | 128 K | 64 | +| 16 | 4096 K | 256 K | 64 | + + +## Occupancy bitmaps + +The occupancy status of a Block is tracked with a bitmap, which must +have granularity corresponding to the alignment of the size category +of objects. + +For example, blocks of size 128 to 1024, which contain object sizes 8 +to 64, with 8-byte alignment, need the occupancy of each 8-byte unit +tracked. That's from 16 bits for a 128-byte block up to 128 bits for +a 1024-byte block. Blocks of size 2 to 16 KiB need tracking in units +of 16 bytes, so that's from 128 bits for a 2 KiB block to 1024 bits +for a 16 KiB block. Repeat the math for the larger alignments. + +Allocating a new slot should of course not require scanning possible +huge numbers of bitmaps from start to end. We keep track of the last +acquired Block and try to fit the next allocation, acquiring a new +Block if it doesn't fit. Given that objects can only occupy up to +1/16 of a Block, this means we waste at most that about that much +space at the end of a Block due to the next object not fitting. + +(The maximum waste is *just under* 1/16, because if exactly 15/16 of +the block is full then another 1/16 sized object fits perfectly, but +anyhow; let's just say waste is capped to 1/16 of Block size.) + +So when do we know to reuse freed spots in previous Blocks? This is +the part where I'm questioning the wisdom of separating this from the +garbage collector. + +I suppose we could implement some free-list kind of system, with per +thread caches, just like Meta Alloc itself does. But before getting +too into the weeds about this without a clear bigger picture, let's +switch gears to another topic instead where I have a somewhat clear +picture of what to do. + + +## Object index + +Our NaN-packing strategy currently uses 32-bit index values for the +identification of various heap objects. + +Is that enough to every individual address that could be returned by +Block Alloc? No, it isn't. But there are solutions. + +Given that code will typically branch on the heap type tag of a NaN +anyway, we can give the 32-bit indexes different meanings. + +For example, any objects that we know to always need exactly 8 or 16 +bytes on the heap will be known to end up somewhere in the first two +slabs of Meta Alloc. And as it so happens, each slab only has up to +2^31 different "positions" (counted in 8-byte units), meaning that +within 32 bits we can perfectly fit an index spanning two slabs! + +So, heap types that fit into a small fixed size are solved. But what +about heap types with a huge span of possible sizes, like an array? + +This is where we will abuse the fact that heap type tags are 8 bits, +which is way more than what you'd typically need. We can use the 4 +high bits as a coarse type tag, and the lower 4 for some sub-type +shenanigans. + +A simple strategy would be using those 4 bits to identify which slab +of Meta Alloc an index points into. Given that there's exactly 16 +slabs, that works out to be perfect. + +If we're "strapped for bits" then we can use a smarter strategy too: +Two bits identify the Size Category of the array or other heap object +with highly variable size: + +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 + +In other words: + +* Tiny and Small correspond to objects up to size 64, which Block + Alloc uses 8-byte alignment for (hence 8-byte indexing works) and + allocates in the first four slabs; we just need to distinguish two + categories to know which two-slab region the 32-bit index is for. + +* The 16-byte indexing starting from Medium overlaps perfectly with + 16-byte alignment Block Alloc uses for sizes 65 to 1024, which are + allocated in the next four slabs. We can address all four of those + slabs with 32-bit indexes thanks to the 16-byte alignment! + +* For larger objects, Block Alloc uses a minimum of 32-byte alignment + so our 32-byte indexing works, and these are allocated in the last + eight slabs, which we can all address thanks to 32-byte indexing. + +We *don't* have a separate category for 64-byte aligned sizes, since +we blew two categories for 8-byte aligned sizes, but thankfully this +works out perfectly anyway since 32-byte index resolution works for +64-byte aligned objects too. + +This strategy is conceptually quite complicated, but I in terms of +implementation, it should just be a few CPU instructions to shift +integers left and right and select the correct slab base offset. + +Probably better to just go with the variant that uses 4 bits and a +uniform 8-byte address resolution, because it's simpler, but if we +ever end up needing to save two bits in our NaN-packing scheme, we +know where to find them! For some of the heap NaN tags anyway. |