Baby's Second Garbage Collector

The current version of the collector also compacts the heap and moves values around. All conservatively discovered values get pinned.

When asked such a question, the adepts of this "Linux" defend a thesis supported by archaeological expeditions which revealed the year of the oldest known mailing list scroll bearing that name: 1991. However, although it is heresy, I do know of the existence of an even older sect of powerful and wise sorcerers whose numerology includes the number you mention. They profess that this "Linux" was not the first. They speak of an age long forgotten where new kernel universes were not only routinely birthed from scratch but also diverged from one another, an age they call the Epoch. They say these galaxies exist out there to this day, unobservable to us, hidden away in corporate mainframes in lands far, far away...

> On 32-bit this was a genuine problem but on 64-bit with large virtual address spaces, the chance of an arbitrary integer being a valid heap pointer drops alot. Especially if your allocator isnt using the low addresses. So the false retention problem is probably less bad than you'd expect.

False retention could be a problem in spite of that. Lone has moved to an index-based tagged value representation. Heap values are now indexes into a large contiguous array of objects. Pointers are calculated on the fly from the heap base pointer.

I did this in order to support easy zero copy heap reallocation with mremap. Uncoupling the values from their addresses also paved the way for heap compaction. It did turn the pointers into small integers though which are probably extremely common everywhere. I could devise a scheme to XOR some constant into the value in order to randomize it a bit and just undo the operation before dereferencing the actual pointers. Not sure if it's worth the trouble though. I haven't measured anything so far.

> One thing id be curious about is how your stack depth reduction after removing the recursive evaluator affects pause time. Conservative GC pause time is often dominated by how much stack there is to scan, so getting rid of recursive eval might have already improved your worst-case pauses more than you realize.

Indeed! I expect the C stack to remain shallow throughout the entire program. It was one of the major wins of the new evaluator design.

I just used a debugger to trace garbage collection during lone's execution of my recursive (fibonacci 10) test program. The garbage collector fired four times. The conservative stack scanner worked up from the bottom of the stack to the top. The difference between top and bottom was always 1008 in all four cases. Accesses are 8 byte aligned so that means 126 iterations. It's scanning around 16 cache lines. Added a counter for conservatively discovered values and the results were: 40, 38, 37, 33. So around 26~31% of values scanned were hits. Not too bad I guess?

> One way is to inform the garbage collector of the locations of all roots [...] implicitly, in the form of a side table generated by the compiler associating code locations with root locations.

I wonder if there's a way to get GCC to do this.