Purpose of gray color in mark & sweep GC

Quote from “Real World OCaml” on color in value header:

Gray     Reachable, but its fields have not been scanned 
Black    Reachable, and its fields have been scanned

However, it seems that the gray color is only used in compact.c:

- Gray words are the encoding of pointers in inverted lists.

For instance, in major_gc.c, mark_slice_darken never even checks for gray values, it just blackens the white values immediately and pushes it onto stack.

In fact, I’ve always wondered why a gray color is needed in the implementation of a mark & sweep GC, if we are pushing the gray values onto a stack/worklist already. (I think it’s conceptually helpful but redundant in practice)

Thus my question: is it correct to say that the gray color in the OCaml GC is used for compaction only?

1 Like

If I remember correctly, the gray color is also important in the event of a mark stack overflow. See mark_stack_prune in major_gc.c.

1 Like

Thanks for the pointer, although I don’t seem to see any reference to the gray color there either…

It seems that this function sets things up for redarken_chunk (seems to be about lazily pushing gray values onto stack), but still the gray color is never used there explicitly, and with my limited understanding of GC internals, I can’t think of a reason to use it there…

What is making things a bit complicated is that the gray colour in the GC was actually removed in 4.12: https://github.com/ocaml/ocaml/pull/9756 . The PR has a well written explanation (cough) of why we made the change.

RWO has an issue for updating the GC chapter now that 4.12 is released: runtime: update GC colours section · Issue #3373 · realworldocaml/book · GitHub

Grey still remains as a value due to it’s use in the compactor but that is a different to what it used to represent in marking.


Thank you so much for the explanation!

On a side note, am I correct in thinking that mark & sweep GC implementations don’t really require a gray color in general? (it bothers me a bit because all online materials I’ve found just restate the textbook definition…)

Aha! Sorry for misdirecting you. My knowledge of the major GC is obsoleted by the change @sadiq pointed you to :slight_smile:

Not at all! Thank you all the same:).