diff options
| -rw-r--r-- | notes/260929-color-bits.md | 276 | ||||
| -rw-r--r-- | notes/index.md | 1 |
2 files changed, 277 insertions, 0 deletions
diff --git a/notes/260929-color-bits.md b/notes/260929-color-bits.md new file mode 100644 index 0000000..47dfcef --- /dev/null +++ b/notes/260929-color-bits.md @@ -0,0 +1,276 @@ +# Pointer Color Bits + +<!--TOC--> + +_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. diff --git a/notes/index.md b/notes/index.md index 45655b1..de4675a 100644 --- a/notes/index.md +++ b/notes/index.md @@ -2,6 +2,7 @@ ## 2026 Q3 +* [2026-09-29: Pointer Color Bits](260929-color-bits.html) * [2026-09-25: No-STW SATB](260925-gc.html) * [2026-09-23: Green Tea](260923-green-tea.html) * [2026-09-22: Using Meta Alloc, Attempt 3](260922-use-alloc-3.html) |