Good evening, patient hackers :) Today finishes off my series onimplementing ephemerons in a garbagecollector.

Last time, we had a working solution for ephemerons, but it involvedrecursively visiting any pending ephemerons from within the copyroutine—the bit of a semi-space collector that is called whentraversing the object graph and we see an object that we hadn't seenyet. This recursive visit could itself recurse, and so we couldoverflow the control stack.

The solution, of course, is "don't do that": instead of visitingrecursively, enqueue the ephemeron for visiting later. Iterate, don'trecurse. But here we run into a funny problem: how do we add anephemeron to a queue or worklist? It's such a pedestrian question("just... enqueue it?") but I think it illustrates some of theparticular concerns of garbage collection hacking.

speak, memory

The issue is that we are in the land of "can't use my tools because Ibroke my tools with my tools". You can't make a standard List<T>because you can't allocate list nodes inside the tracing routine: if youhad memory in which you could allocate, you wouldn't be calling thegarbage collector.

If the collector needs a data structure whose size doesn't depend on theconnectivity of the object graph, you can pre-allocate it in a reservedpart of the heap. This adds memory overhead, of course; for a 1000 MBheap, say, you used to be able to make graphs 500 MB in size (for asemi-space collector), but now you can only do 475 MB because you haveto reserve 50 MB (say) for your data structures. Another way to look atit is, if you have a 400 MB live set and then you allocate 2GB ofgarbage, if your heap limit is 500 MB you will collect 20 times, but ifit's 475 MB you'll collect 26 times, which is more expensive. This ispart of why GC algorithms are so primitive; implementors have tobe stingy that we don't get to have nice things / data structures.

However in the case of ephemerons, we will potentially need one worklistentry per ephemeron in the object graph. There is no optimal fixed sizefor a worklist of ephemerons. Most object graphs will have no or fewephemerons. Some, though, will have practically the whole heap.

For data structure needs like this, the standard solution is to reservethe needed space for a GC-managed data structure in the object itself. Forexample, for concurrent copying collectors, the GC might reserve a wordin the object for a forwarding pointer, instead of just clobbering thefirst word. If you needed a GC-managed binary tree for a specific kindof object, you'd reserve two words. Again there are strong pressures tominimize this overhead, but in the case of ephemerons it seems sensibleto make them pay their way on a per-ephemeron basis.

so let's retake the thing

So sometimes we might need to put an ephemeron in a worklist. Let's adda member to the ephemeron structure:

struct gc\_ephemeron { struct gc\_obj header; int dead; struct gc\_obj *key; struct gc\_obj *value; struct gc\_ephemeron *gc\_link; // *};

Incidentally this also solves the problem of how to represent thestruct gc\_pending\_ephemeron\_table; just reserve 0.5% of the heap or soas a bucket array for a buckets-and-chains hash table, and use thegc\_link as the intrachain links.

struct gc\_pending\_ephemeron\_table { struct gc\_ephemeron *resolved; size\_t nbuckets; struct gc\_ephemeron buckets[0];};

An ephemeron can end up in three states, then:

1. Outside a collection: gc\_link can be whatever.

2. In a collection, the ephemeron is in the pending ephemeron table: gc\_link is part of a hash table.

3. In a collection, the ephemeron's key has been visited, and the ephemeron is on the to-visit worklist; gc\_link is part of the resolved singly-linked list.

Instead of phrasing the interface to ephemerons in terms of visitingedges in the graph, the verb is to resolve ephemerons. Resolving anephemeron adds it to a worklist instead of immediately visiting anyedge.

struct gc\_ephemeron **pending\_ephemeron\_bucket(struct gc\_pending\_ephemeron\_table *table, struct gc\_obj *key) { return &table->buckets[hash\_pointer(obj) % table->nbuckets];}void add\_pending\_ephemeron(struct gc\_pending\_ephemeron\_table *table, struct gc\_obj *key, struct gc\_ephemeron *ephemeron) { struct gc\_ephemeron **bucket = pending\_ephemeron\_bucket(table, key); ephemeron->gc\_link = *bucket; *bucket = ephemeron;}void resolve\_pending\_ephemerons(struct gc\_pending\_ephemeron\_table *table, struct gc\_obj *obj) { struct gc\_ephemeron **link = pending\_ephemeron\_bucket(table, obj); struct gc\_ephemeron *ephemeron; while ((ephemeron = *link)) { if (ephemeron->key == obj) { *link = ephemeron->gc\_link; add\_resolved\_ephemeron(table, ephemeron); } else { link = &ephemeron->gc\_link; } }}

Copying an object may add it to the set of pending ephemerons, if it isitself an ephemeron, and also may resolve other pending ephemerons.

void resolve\_ephemerons(struct gc\_heap *heap, struct gc\_obj *obj) { resolve\_pending\_ephemerons(heap->pending\_ephemerons, obj); struct gc\_ephemeron *ephemeron; if ((ephemeron = as\_ephemeron(forwarded(obj))) && !ephemeron->dead) { if (is\_forwarded(ephemeron->key)) add\_resolved\_ephemeron(heap->pending\_ephemerons, ephemeron); else add\_pending\_ephemeron(heap->pending\_ephemerons, ephemeron->key, ephemeron); }}struct gc\_obj* copy(struct gc\_heap *heap, struct gc\_obj *obj) { ... resolve\_ephemerons(heap, obj); // * return new\_obj;}

Finally, we need to add something to the core collector to scan resolvedephemerons:

int trace\_some\_ephemerons(struct gc\_heap *heap) { struct gc\_ephemeron *resolved = heap->pending\_ephemerons->resolved; if (!resolved) return 0; heap->pending\_ephemerons->resolved = NULL; while (resolved) { resolved->key = forwarded(resolved->key); visit\_field(&resolved->value, heap); resolved = resolved->gc\_link; } return 1;}void kill\_pending\_ephemerons(struct gc\_heap *heap) { struct gc\_ephemeron *ephemeron; struct gc\_pending\_ephemeron\_table *table = heap->pending\_ephemerons; for (size\_t i = 0; i < table->nbuckets; i++) { for (struct gc\_ephemeron *chain = table->buckets[i]; chain; chain = chain->gc\_link) chain->dead = 1; table->buckets[i] = NULL; }}void collect(struct gc\_heap *heap) { flip(heap); uintptr\_t scan = heap->hp; trace\_roots(heap, visit\_field); do { // * while(scan < heap->hp) { struct gc\_obj *obj = scan; scan += align\_size(trace\_heap\_object(obj, heap, visit\_field)); } } while (trace\_ephemerons(heap)); // * kill\_pending\_ephemerons(heap); // *}

The result is... not so bad? It makes sense to make ephemerons paytheir own way in terms of memory, having an internal field managed bythe GC. In fact I must confess that in the implementation I have beenwoodshedding, I actually have three of these damn things; perhaps moreon that in some other post. But the perturbation to the core algorithmis perhaps less than the original code. There are still someoptimizations to make, notably postponing hash-table lookups until thewhole strongly-reachable graph is discovered; but again, another day.

And with that, thanks for coming along with me for my journeys intoephemeron-space.

I would like to specifically thank Erik Corry and Steve Blackburn fortheir advice over the years, and patience with my ignorance; I can onlyimagine that it's quite amusing when you have experience ina domain to see someone new and eager come in and make many of theclassic mistakes. They have both had a kind of generous parsimony inthe sense of allowing me to make the necessary gaffes but also providinginsight where it can be helpful.

I'm thinking of many occasions but I especially appreciate the advice tostart with a semi-space collector when trying new things, be itbenchmarks or test cases or API design or new functionality, as it's asimple algorithm, hard to get wrong on the implementation side, andperfect for bringing out any bugs in other parts of the system. In thiscase the difference between fromspace and tospace pointers has amaterial difference to how you structure the ephemeron implementation;it's not something you can do just in a trace\_heap\_object function, asyou don't have the old pointers there, and the pending ephemeron tableis indexed by old object addresses.

Well, until some other time, gentle hackfolk, do accept my sincerest wastedisposal greetings. As always, yours in garbage, etc.,