diff options
| -rw-r--r-- | notes/260923-green-tea.md | 209 | ||||
| -rw-r--r-- | notes/index.md | 1 | ||||
| -rw-r--r-- | src/zisp/value.zig | 5 |
3 files changed, 214 insertions, 1 deletions
diff --git a/notes/260923-green-tea.md b/notes/260923-green-tea.md new file mode 100644 index 0000000..a2ba4ae --- /dev/null +++ b/notes/260923-green-tea.md @@ -0,0 +1,209 @@ +# Green Tea + +<!--TOC--> + +_2026 September_ + +I thought I could use Go's Green Tea GC optimization strategy for the +GC design I have in mind, but realized it won't work for two reasons: + +1. If I understand correctly, Go's bitmaps track 8-byte memory slots, + so it can mark individual memory slots that may contain pointers. + My bitmaps are more specialized, and only mark the position of an + object of a certain size class within a Meta Alloc slab; this cuts + down bitmap memory use substantially. Besides, Zisp object fields + may contain NaN-packed pointers as well as raw pointers, or other + representations of an object address, so I really need "layout" + information when scanning a heap object's memory. + +2. Zisp heap objects don't have a fully generic object header telling + you what type it is / what the memory layout of the object on the + heap is. Some types have a specific header format, like an array + header encoding its length among other things, but the NaN-packed + pointer to an object may already contain all its metadata, such + that there's no metadata whatsoever on the heap. + +So, unlike in Green Tea, the mark phase of the Zisp GC cannot simply +push memory spans onto the work stack. It has to push work objects +that consist of the object's address and type. + + +## Radix Bush + +The Meta Alloc heap's 256 GiB cap once again comes in handy, allowing +us to use an incredibly efficient radix-tree-like data structure for +the working set of the GC's tracing algorithm. + +Level 0: A 64-bit map where each bit represents a 4 GiB region of our +total heap space. (256 GiB / 64 = 4 GiB.) If a bit is set, it means +there's work to do in there. Use `LZCNT` to locate a bit, using the +index as an index into Level 1. + +Level 1: A 64 x 64 = 4096-bit map where each bit represents a 64 MiB +segments of the heap. (4 GiB / 64 = 64 MiB.) The index from Level 0 +already told us which 64-bit part of this map to use `LZCNT` on, to +get a Level 2 index. + +Level 2: A 64 x 64 x 64 = 262,144-bit map where each bit represents a +1 MiB span of the heap. (64 MiB / 64 = 1 MiB.) Use `LZCNT` and get +the Level 3 index. + +(Note: 262,144 bits is 32 KiB which is OK to allocate statically.) + +Level 3: A 64 x 64 x 64 = 262144-element array of Work Table Header +structs, which consist of a 64-bit pointer to a buffer of memory, and +a 64-bit summary bitmap indicating which portions of it contain valid +entries right now. + +Using 128 bits per Work Table Header means the Level 3 array is 4 MiB +in size. This could be allocated statically, or with mmap; static is +supposed to be fine because the `.bss` section of ELF merely declares +the required size, and the kernel then maps it in virtual memory and +pages it in on demand. But when in doubt, use mmap. + +Typically, the same parts of this array will be used over and over +again. For example, if we only ever touch the first 512 MiB of the +first 16 GiB Meta Alloc slab, then only the first 512 entries of the +first 1/16 of the array will be used. After that, there will be an +untouched gap, before entries corresponding to the next slab of Meta +Alloc begin. So, as usual, the kernel's demand paging helps us here. + + +## Work Table + +Given that each Work Table corresponds to a 1 MiB span of the heap, +and the smallest object size is 8 bytes, there can be at most 2^17 +(131,072) objects in a Work Table. + +For each object, we need to know its type; 16 bits are enough, with +headroom to represent "invalid" to indicate an unoccupied spot in the +work array. + +(In our NaN packing strategy, regular heap pointers use 8 bits for a +type tag, but there's also two special NaN tags for short strings and +arrays that use an 8-bit length tag instead. We won't ever actually +use all possible 8-bit values for the regular heap type tag; we can +reserve two for the special types that use another 8 bits for their +length, and another one to mean "invalid.") + +If Zisp supports fully static typing one day, such that every single +user-defined heap type needs a static type ID that the GC knows of, +then we could use 32 or 64 bits instead, doubling or quadrupling the +Work Table size in terms of memory use (but not entry count). + +In any case, remember that in Level 3 of the Radix Bush there was a +64-bit "summary bitmap." This specifies which portions of the full +Work Table actually contain any entries. Divide 2^17 by 2^6 and we +have 2^13 = 2048 possible entries per portion that will be scanned +linearly to find valid entries. (This is why we need the "invalid" +type tag.) + +When we locate a valid type tag, the index at which we found it is +implicitly the index of the heap object to work on, relative to the +start address of the span of memory we're on. + +Assuming 16-bit entries, that's 4096 bytes of memory to scan, in one +linear pass, which should be extremely efficient via SIMD and memory +prefetching. It's also a single page, which is neat because we won't +fault in an unneeded page. + +To be clear: We don't immediately populate the entire Work Table with +"invalid" entries upon allocation; only the portions that the summary +bitmap says are occupied. + +Heck, I'll just make sure that the type tag 0 stands for invalid, so +there's no need to do anything special at all. + +### Table Size + +Let's assume 16 bits per Work Table entry, meaning the entire table +needs `2^17 * 2 = 256 KiB` of memory at most; for larger object sizes +where there can be fewer objects per 1 MiB span, the size is smaller. + +The exact maximum size is a bit tricky to calculate for some classes. +For example, although the second slab hosts 16-byte objects, meaning +we can simply halve the buffer size, the third slab can host 24-byte +objects or 32-byte objects. So we can't just keep halving. + +The simplest solution is to just stagger the halving sequence by one +step after the second slab. In other words, the smallest size class +in a category is rounded down to a power of two. This feels off but +it's a consequence of the first few slabs being a bit special in the +size classes they support. + +| Slab | Size Classes | Min Alloc | Rounded | Buffer Size | +| 0 | 8 | 8 | 8 | 256 KiB | +| 1 | 16 | 16 | 16 | 128 KiB | +| 2 | 24, 32 | 24 | 16 | 128 KiB | +| 3 | 40 - 64 | 40 | 32 | 64 KiB | +| 4 | 80 - 128 | 80 | 64 | 32 KiB | +| ... | ... | ... | ... | ... | + +(Assuming 2-byte Work Table entries.) + + +## Slab Exhaustion? + +There's an interesting theoretical failure mode of the strategy. + +The fact that Level 3 of the Radix Bush has 256 Ki entries in total +means that for each slab (1/16) it has 16 Ki entries. + +As it turns out, Meta Alloc can only support 64 Ki slots of 256 KiB +(2-byte work entries), 32 Ki slots of 512 KiB (4-byte work entries), +or exactly 16 Ki slots of 1 MiB (8-byte work entries), due to the 16 +GiB per-slab limit. + +And remember that Meta Alloc is used for the actual application heap +as well, not just for GC and other runtime metadata. + +So, in theory, the GC could exhaust 25% of the 256 KiB slab, or with +large work entries (full static typing; bigger type tags), 50% of the +512 KiB slab or 100% of the 1 MiB slab. + +However, it seems extremely unlikely that this would actually happen, +given that the work-set of a tracing GC typically contains a small +fraction of the live object graph at any given moment. + +Still, imagine a humongous array of heterogeneous Zisp values, say a +billion, and every single one happens to point to an 8-byte object. +That's about half of all 8-byte objects that can be allocated (the +limit is exactly 2 Gi since a slab is 16 GiB) so when the GC traces +this array it would really use a substantial portion of a slab. + +Honestly, the short answer to this problem is: Don't do that, then. + +Just to put things in perspective: A billion 64-bit values (which is +what a heterogeneous Zisp array is) consumes 8 GiB of RAM. If you're +wondering where in Meta Alloc that would even fit: Nowhere, since the +Block Alloc / GC Alloc strategy will be to allocate any object beyond +256 KiB outside the Meta Alloc heap, and represent it with a handle. +So it *could* exist in Zisp, but if you're using 8 GiB just for that +array, and another 8 GiB for the billion 8-byte objects it will hold, +then hopefully your heap contains almost nothing else, and the GC can +use a large portion of the 256 KiB or 512 KiB slab? + +This is an interesting failure mode to keep in mind, but in practice +it's probably not something anyone would ever encounter unless they +completely abuse the runtime. This kind of crazy use-case is where +you should really stop relying on a GC and reach for manual `mmap()` +usage and whatnot. + + +## Thread Safety? + +I've been "discussing" this strategy with Google Gemini and it says +that thread safety shouldn't be an issue per se (as in, the way I've +designed it could lend itself to lockless thread-safe strategies via +atomic ops), but it may also be acceptable to have a single-threaded +concurrent GC unless you have highly aggressive allocation rates +across dozens of threads. + +Supposedly, a single GC thread not being able to catch up with many +allocating threads is a real and common problem in heavy networked +services, though I would question the architectural decisions they +make. + +When I actually get to implementing it, I'll have to think about the +cost of making the GC algorithm concurrent with itself, both in terms +of CPU throughput, and code complexity. diff --git a/notes/index.md b/notes/index.md index a9faf3d..1a8637b 100644 --- a/notes/index.md +++ b/notes/index.md @@ -44,3 +44,4 @@ * [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) +* [Green Tea](260923-green-tea.html) diff --git a/src/zisp/value.zig b/src/zisp/value.zig index aff05fe..413330c 100644 --- a/src/zisp/value.zig +++ b/src/zisp/value.zig @@ -75,8 +75,11 @@ pub const none = Value{ .misc = .{ .value = .none } }; /// A plain (unpacked, untagged, uncompressed) pointer into the main heap. pub const HeapPtr = *align(16) anyopaque; -/// Values for the 8 type bits on main heap pointers. +/// Values for the 8 type bits on regular heap pointers. pub const HeapType = enum(u8) { + /// Special "invalid" tag, equals zero + _invalid, + /// Pair (car, cdr) pair, |