# Green Tea _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 segment 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 = 262,144-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 | | 5 | 160 - 256 | 160 | 128 | 16 KiB | | 6 | 320 - 512 | 320 | 256 | 8 KiB | | 7 | 640 - 1024 | 640 | 512 | 4 KiB | | ... | ... | ... | ... | ... | (Assuming 2-byte Work Table entries.) ### Occupancy Bitmap *This entire sub-section is a correction to the design after I was done writing all the above; too lazy to edit original.* Above I said it would be extremely fast to scan 4 KiB of memory, to look for 16-bit values in it. That was a bit naive, and we should improve on that. The Work Table Header, instead of being a 64-bit buffer pointer and 64-bit summary bitmap, could instead be: u32: buffer_ptr u32: bitmap_ptr u64: summary_map The 32-bit "pointers" would be indexes into specific Meta Alloc slabs as implied by the buffer size. For example, for the first 1/16 part of the Work Table Header array, we know the entries are for 8-byte objects, meaning the Work Table needs to be 256 KiB, meaning it's in the Meta Alloc slab for 256 KiB slots. (Actually, we may also get it from Block Alloc; doesn't matter much I think.) The `bitmap_ptr` would point to a buffer that's 1/16 the size of the Work Table buffer, indicating which 16-bit entries have a value. For example, for the 8-byte size class, the Work Table buffer is 256 KiB so the bitmap buffer would be 16 KiB. The 64-bit summary tells us which 1/64 portion to check for occupancy, so we only scan 256 bytes worth of bits, and thus we get indices into the Work Table itself. If the Work Table buffer is so small that the 64-bit summary already provides enough granularity, then the `bitmap_ptr` can be the Meta Alloc index equivalent of NULL. | Slab | Buffer Size | Bitmap Buffer | Scan Size | |------|-------------|---------------|-----------| | 0 | 256 KiB | 16 KiB | 256 | | 1 | 128 KiB | 8 KiB | 128 | | 2 | 128 KiB | 8 KiB | 128 | | 3 | 64 KiB | 4 KiB | 64 | | 4 | 32 KiB | 2 KiB | 32 | | 5 | 16 KiB | 1 KiB | 16 | | 6 | 8 KiB | 512 B | 8 | | 7 | 4 KiB | 256 B | 4 | | 8 | 2 KiB | 128 B | 2 | | 9 | 1 KiB | 64 B | 1 | | 10 | 512 B | - | 8 | | 11 | 256 B | - | 4 | | 12 | 128 B | - | 2 | | 13 | 64 B | - | 1 | | 14 | 32 B | - | 1 | | 15 | 16 B | - | 1 | As we can see, by the time we reach Slab 9, we only need to scan a single byte of the occupancy bitmap. After that, we stop using an additional bitmap buffer, using only the 64-bit summary bitmap. ## 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.