# Pointer Color Bits _2026 September_ Here is an idea to optimize the design of our GC. Our NaN packing scheme has 8 bits reserved for GC purposes because I thought I'd implement something like ZGC, and yet this Mark & Sweep design I landed on doesn't require a single bit on pointers. However, we could use them to optimize some things, I think. This is a bit tricky to reason about because it's easy to forget that the aforementioned bits are *on the pointer* to the object, not in a header inside the object. ## Trace loop During the trace loop for marking, there would no benefit to be had from these bits if our GC were non-concurrent, because: * You start out scanning the roots; each pointer will only be touched once here and not scanned again, so there's no benefit to be had from checking any bits on the scanned pointers. * The Grey set is implicitly deduplicating, so each object's content will only be scanned once during any iteration of the trace loop. So again, nothing to be gained. * During subsequent trace iterations, we may find additional pointers to previously scanned (Black) objects. They will not be added to the Grey set again, so once again, bits that were set on pointers they contain are not helpful. (In short: Every pointer in memory is only encountered once, because the object containing the pointer won't be visited a second time.) However, given that the object graph may be mutated under our feet, color bits on pointers can be useful. If we scanned a big number of pointers, then while we were busy tracing and scanning other objects, some mutator wrote all those pointers into some big array that is yet to be scanned; then once we get to that array, we may end up doing a lot of redundant work: For each pointer, we check the Marked Bitmap telling us whether the pointed-to object is Black, and if it isn't, add the pointer to the Work Set to Grey it. If instead we had set some bit on the pointer the moment it was first scanned (the object added to the Grey set) then we could immediately skip the pointer on subsequent scans of that pointer. (The Marked Bitmap would say Black if our trace loop happens to have already processed the pointer and removed it from the Work Set; else it's still in the Work Set which is auto-deduplicating, so we add the pointer again for no reason. It should be noted that both operations --checking the Marked Bitmap, and adding to the Work Set-- are highly efficient under our design, but still require memory loads, which may increase L1 pressure to a meaningful degree.) In summary, what we want so far is a Grey bit on pointers, which our trace loop can check when scanning a pointer. The bit should not be unset when the object becomes Black, so we only need to test one bit: If it's set, it means the object is Grey *or* Black, which means we can skip it while scanning the object containing it, without needing external lookups. I said the bit shouldn't be unset; we actually can't do that anyway, since the *target* of the pointer will be added to the Work Set, and by the time we get to work on that item, we not only miss information about where the original pointer was (which field of which object, or more explicitly, which memory location); we can not even know whether that pointer even exists anymore, as it could have been overwritten. So, we *can* only communicate "Grey or Black" to Mutator threads via pointer coloring, from GC threads anyway. ## Store barriers We might get some use out of the color bits here as well. Our store barrier is conceptually this: function pre_store_barrier(object, field, new_value): // Dijkstra if (stack is Grey // stack not yet scanned and object is Black and new_value is a Pointer and new_value is White) { shade_grey(new_value); } // Yuasa if (object is not Black) { // elide unnecessary load() old_value = load(object, field); if (old_value is a Pointer and old_value is White) { shade_grey(old_value); } } } (This is written to take dynamic typing into account; under static typing, the "is Pointer" checks fall away.) (Under static typing, pointers could still be tagged. On AArch64, we could use Top Bit Ignore to make it cost nothing. On x86-64, it adds some cost to mask or shift off the tag bit every time we want to use the pointer, which may be too much, or be paid off by the additional efficiency of barriers; I'm not sure.) (If this is a write to a global/static variable, then `object` could just be a pointer to the memory of the variable itself, masquerading as an object, and implicitly colored Black. The handling of globals altogether is an interesting topic; they could alternatively be seen as implicitly Grey and re-scanned by every Mutator thread during its transition into the MARK state. Or we could simply forbid mutable global variables, forcing indirection through a "Box" heap object.) Normally, for the sake of Mutator efficiency, some conditionals might be skipped and pointers indiscriminately written into an efficient local buffer that's frequently drained by a GC thread. (There would still need to be a conditional branch to make sure the buffer isn't full, though.) That's because checking the color of a heap object is non-trivial: It requires a load from the Marked bitmap, and the part of it we need to load from may not be hot in the caches of the CPU core executing the Mutator thread. (Actually, I'm not sure about the trade-offs between checking if the object is Black vs. doing an unconditional write; either option seems quite wasteful for what needs to be an ultra-efficient operation.) With color bits on pointers, we may be able to avoid some redundant work more easily. Interjection: Given that the GC is concurrent, and we don't want to litter our code with ordered atomic operations, we can never actually know, from a Mutator perspective, whether an object hasn't advanced into the next color. If we *think* it's White, it could actually be White, Grey, or Black. If we *think* it's Grey, it could be Grey or Black. If we think it's Black, it actually is. It's important to keep this in mind, because it means a Mutator can never rely on a check such as: "Is the object white?" Based on that wisdom, let's strip down our barrier pseudo-code, and also simplify it by ignoring the whole dynamic type situation since it's hopefully irrelevant right now: function pre_store_barrier(object, field, new_ptr) { // Dijkstra if (stack is Grey and new_ptr not Grey) shade_grey(new_ptr); // Yuasa if (object not Black) { old_ptr = load(object, field); if (old_ptr not Grey) shade_grey(old_ptr); } } (We can't ask "object is Black" because it could concurrently become Black after the check.) In short: The Dijkstra barrier can test the Grey bit to realize it's safe to skip the shade; the Yuasa barrier can test the Black bit on the container object's pointer to realize it's safe to skip even the load operation for the old pointer (very nice!) and otherwise it can still test the Grey bit on the loaded pointer to realize it can skip the shade. I think that's as good as it gets. Oh, one more thing: The Dijkstra barrier should set the Grey bit on the pointer it's writing. That's one more instruction, which should be fine... Though it will become two instructions in a bit; read on. The Yuasa barrier doesn't need to do anything, since it's there to catch pointers that are being deleted from the object graph anyway. ## Clearing color bits How to clear the color bits on pointers after a GC cycle is complete? There's a few possible approaches: * Another trace of the entire object graph. Yuck. * Cycling back and forth between the meanings of 0 and 1: During one GC cycle they mean the usual, during the next they are inverted, then normal again, etc.; can be implemented with an XOR operation with a mask we set at the start of each GC cycle... Not so bad, although it adds overhead to barriers due to the additional XOR. * Use 2 more bits, and have the GC cycle back and forth between which pair of bits are tested, simply by updating global mask values at the start of each GC cycle. Tracing the entire object graph means every pointer is visited, meaning we can make sure to clear both color bits for the next cycle during the current one. This unfortunately adds one more instruction to the Dijkstra barrier --one to set current Grey bit, one to clear next-- but hopefully that should be fine, given that this barrier is only active in the brief time window where stacks are being scanned. It should be better than the XOR option that adds an instruction to every color *check* rather than just the store barriers. ## Data races Given that the GC must clear some bits (colors for next cycle) while setting others (Grey bit for this cycle), we cannot use an atomic RMW to read and update a pointer in an object without races. Thankfully, there's an easy safe alternative: Read the current value, create the modified new value, then perform an atomic CAS expecting the original as the pre-swap value. The field of the object containing that pointer could actually have been concurrently modified in between, and then the same pointer put back again, but that simply doesn't matter in this case; it's safe. Mutators don't need to do anything special in practice, since x86-64 and AArch64 write aligned 64-bit values atomically anyway; though in LLVM concurrency semantics, the correct choice would be an Unordered atomic store operation, just to communicate our precise intent. ## Black allocation When doing black allocation, the Black *and* Grey bits must be set. ## Summary In our NaN scheme, 4 out of 8 bits reserved for GC purposes are used for coloring: * During odd GC cycles, bits 1 and 2 mean Grey and Black. * During even GC cycles, bits 3 and 4 mean Grey and Black. * At the start of each cycle, the GC sets a pair of global variables to appropriate bit masks for single-instruction testing of Grey and Black color on a pointer. A third variable is set to a mask value that can be used to clear the bits for the *next* GC cycle. * During stack scanning, pointers can be colored Grey non-atomically, since a stack cannot be scanned concurrently. * Stack scanning *may* simply ignore color checking for a minor boost in speed, since few if any pointers will be colored at this point inside stacks. (It is technically possible though.) * During concurrent marking, GC threads use CAS to update color bits on pointers; RMW not possible, since some bits must be cleared and others set. We *don't* loop on a failed CAS; we just move on, as the new pointer isn't our responsibility. Also, if a pointer is deleted and re-inserted during the brief time window in which we modify its color bits in a register, the CAS will succeed, and that's completely fine and safe. * Mutators use Unordered atomic stores for all pointer writes; this will compile to plain non-atomic store operations on common 64-bit architectures anyway; it just communicates intend. (GCC doesn't even have this, by the way; just an LLVM semantics concept.) * The Dijkstra barrier can safely modify color bits in a register before writing the new pointer. * The Yuasa barrier handles pointers that are about to be deleted, so it doesn't need to do anything special here. * Black allocation sets the Grey and Black bits on freshly returned pointers, using the current values of the global mask variables.