path: root/notes/260929-color-bits.md

# 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.

Oh, and by the way, having metadata bits on object pointers means you
need to mask them off when comparing pointers:

    equal(p1, p2) = (p1 & ~COLOR_BITS) == (p2 & ~COLOR_BITS)

Probably not a big deal.

Unpacking a NaN-packed pointer shouldn't need to do anything special;
you just don't mind the GC bits.

If we add static typing, it's more annoying, since we need to strip
off bits on every dereference.  However, AArch64 has Top Byte Ignore.
Intel and AMD are lagging far behind, but seem to have started adding
similar features, like Intel LAM48/LAM57 and AMD UAI.  Hopefully, by
the time Zisp is implemented, these will be universally available!