It's handled through the actual GC implementation, Cheney's Algorithm to be specific, it's mentioned in the blog post but I didn't write how it actually works there.
My git repo link at the end has an actual C implementation if you'd like to have a look.
The TL;DR is that the algorithm starts by going through the roots and copying each of them to a new Arena. Each time it does it updates the root pointer to the new location and writes out a "forwarding pointer" in the old allocation such that if 2 roots go to the same object, they can check if it's already been forwarded, and replace themselves with that pointer without copying.
Once all the roots are copied, the algorithm goes iteratively through every allocation in the new Arena, digging through their pointers, doing the same copy/update/forward/dance onto the same Arena, until it reaches a fixpoint (no new copies happen). Then it frees the old Arena.
It's a really simple algorithm, I strongly suggest having a look at the wikipedia page :)
tekknolagi|1 year ago
sirwhinesalot|1 year ago
It's handled through the actual GC implementation, Cheney's Algorithm to be specific, it's mentioned in the blog post but I didn't write how it actually works there.
My git repo link at the end has an actual C implementation if you'd like to have a look.
The TL;DR is that the algorithm starts by going through the roots and copying each of them to a new Arena. Each time it does it updates the root pointer to the new location and writes out a "forwarding pointer" in the old allocation such that if 2 roots go to the same object, they can check if it's already been forwarded, and replace themselves with that pointer without copying.
Once all the roots are copied, the algorithm goes iteratively through every allocation in the new Arena, digging through their pointers, doing the same copy/update/forward/dance onto the same Arena, until it reaches a fixpoint (no new copies happen). Then it frees the old Arena.
It's a really simple algorithm, I strongly suggest having a look at the wikipedia page :)