Sometimes when you see an elegant algorithm, you think "looks great, Ijust need it to also do X". Perhaps you are able to build X directlyout of what the algorithm gives you; fantastic. Or, perhaps you canalter the algorithm a bit, and it works just as well while also doing X.Sometimes, though, you alter the algorithm and things go pear-shaped.

Tonight's little note builds on yesterday's semi-space collectorarticleand discusses an worse alternative to the Cheney scanning algorithm.

To recall, we had this visit\_field function that takes a edge in theobject graph, as the address of a field in memory containing a struct gc\_obj*. If the edge points to an object that was already copied,visit\_field updates it to the forwarded address. Otherwise it copies the object,thus computing the new address, and then updates the field.

struct gc\_obj* copy(struct gc\_heap *heap, struct gc\_obj *obj) { size\_t size = heap\_object\_size(obj); struct gc\_obj *new\_obj = (struct gc\_obj*)heap->hp; memcpy(new\_obj, obj, size); forward(obj, new\_obj); heap->hp += align\_size(size); return new\_obj;}void visit\_field(struct gc\_obj **field, struct gc\_heap *heap) { struct gc\_obj *from = *field; struct gc\_obj *to = is\_forwarded(from) ? forwarded(from) : copy(heap, from); *field = to;}

Although a newly copied object is in tospace, all of its fieldsstill point to fromspace. The Cheney scan algorithm later visits thefields in the newly copied object with visit\_field, which bothdiscovers new objects and updates the fields to point to tospace.

One disadvantage of this approach is that the order in which the objectsare copied is a bit random. Given a hierarchical memory system, it'sbetter if objects that are accessed together in time are close togetherin space. This is an impossible task without instrumenting the actualdata access in a program and then assuming future accesses will be like thepast. Instead, the generally-accepted solution is to ensure thatobjects that are allocated close together in time be adjacent inspace. The bump-pointer allocator in a semi-space collector providesthis property, but the evacuation algorithm above does not: it wouldneed to preserve allocation order, but instead its order is driven bygraph connectivity.

I say that the copying algorithm above is random but really it favors abreadth-first traversal; if you have a binary tree, first you will copythe left and the right nodes of the root, then the left and rightchildren of the left, then the left and right children of the right,then grandchildren, and so on. Maybe it would be better to keep parentand child nodes together? After all they are probably allocated thatway.

So, what if we change the algorithm:

struct gc\_obj* copy(struct gc\_heap *heap, struct gc\_obj *obj) { size\_t size = heap\_object\_size(obj); struct gc\_obj *new\_obj = (struct gc\_obj*)heap->hp; memcpy(new\_obj, obj, size); forward(obj, new\_obj); heap->hp += align\_size(size); trace\_heap\_object(new\_obj, heap, visit\_field); // * return new\_obj;}void visit\_field(struct gc\_obj **field, struct gc\_heap *heap) { struct gc\_obj *from = *field; struct gc\_obj *to = is\_forwarded(from) ? forwarded(from) : copy(heap, from); *field = to;}

Here we favor a depth-first traversal: we eagerly calltrace\_heap\_object within copy. No need for the Cheney scanalgorithm; tracing does it all.

void collect(struct gc\_heap *heap) { flip(heap); uintptr\_t scan = heap->hp; trace\_roots(heap, visit\_field);}

The thing is, this works! It might even have better performance forsome workloads, depending on access patterns. And yet, nobody doesthis. Why?

Well, consider a linked list with a million nodes; you'll end up with amillion recursive calls to copy, as visiting each link eagerlytraverses the next. While I am all about unboundedrecursion, aninfinitely extensible stack is something that a language runtime has toprovide to a user, and here we're deep intoimplementing-the-language-runtime territory. At some point a user'sdeep heap graph is going to cause a gnarly system failure via stackoverflow.

Ultimately stack space needed by a GC algorithm counts towards collectormemory overhead. In the case of a semi-space collector you already needtwice the amount memory as your live object graph, and if you recursedinstead of iterated this might balloon to 3x or more, depending on theheap graph shape.

Hey that's my note! All this has been context for some future article,so this will be on the final exam. Until then!