In the Wikipedia article for “tracing garbage collection”, the following claim is made:
...most modern tracing garbage collectors implement some variant of the tri-color marking abstraction
In this abstraction, objects are grouped into three sets: white, black, and grey. The basic tracing algorithm enumerates all the elements of the grey set, marking each grey object as black until all the unreachable objects are white and can be deleted.
What the article doesn’t go into is how the grey set is implemented, which has clear implications for the overall performance of the GC algorithm. The most direct and obvious solution is to model the grey set as a data structure of pointers to objects (hash set, stack, queue, whatever), but (keep in mind I have no data on this) this seems quite expensive in terms of space, one pointer per object reference in the call stack.
How is the “grey list” implemented in modern garbage collectors to maximize efficiency in terms of time and space and what kind of overhead do these solutions incur?