https://verdagon.dev/grimoire/grimoire
I've nothing against the post, it just irks me to see a big unorganized list like a pile of christmas tree lights.
It's an interesting blog post with comprehensive references, but it's also like a travel brochure with a list of destinations. In practice you want something more like a route map: A rough overview of how different approaches complement each other, or overlap each other. A jigzaw puzzle is much easier to solve when there's a picture on the front of the box.
Here's a modest propsoal for a better table of contents:
-
Automatic memory management at runtime / Managed Heaps
Here, we'd cover these two approaches:
- Reference counting (2)
- Tracing garbage collection (11)
The key idea here is that these two approaches are more than complementary, they're duals: A tracing collector walks over the set of live elements in the heap, a reference counting collector walks over the set of dead elements.
Reference counting introduces pauses too. Deleting a long chain of elements with a single owner can easily interrupt processing.
If you then start deferring reference count increment and decrements to fix it, you've built a tracing garbage collector, just one that keeps exact reference counts, rather than the usual approximation of "no references" and "zero or more"
Bacon's derivation of a concurrent collector paper demonstrates this with a singular algorithm for collection that's specialised into tracing only and refcount only versions.
Either way, these two approaches shouldn't ever be listed apart. They're best buddies.
-
Automatic memory management at compile time / Inferring Regions & Lifetimes
First introduced by "Mads Tofte and Jean-Pierre Talpin" in Region based memory management", a region is a chunk of memory that has the following properties:
- Every object lives in exactly one region
- Regions can contain pointers to other regions, but without cycles
- Regions form a stack like first-in last-out allocation style
- Regions get deallocated as a whole
A region is a little bit more fancy than an arena, and there's several versions of it in the list.
- Borrow checking (3, what's that? a region of memory that has a parent etc)
- Arena-only programming (4, cyclone has region inference)
- Ada/SPARK (5, as the stack dicipline is enforced through pointer address)
The key thing here is that "form a directed graph over the heap to enforce a filo allocation and deallocation ordering" can be implmented in several ways.
The author has chosen to use "Regions" to mean a particular form of "Unique pointers" but that's just how names work out.
-
Manually managed Heaps, Arenas, and Regions
What if we did the whole "form a directed graph over the heap to enforce a filo allocation and deallocation ordering" thing but at runtime? Or maybe just the "Deallocate in bulk bit?"
- Move-only programming (1, aka linear and affine types, or uniqueness typing)
- Manual Regions (6, aka uniqueness again)
- Arena-only programming (manual regions, but it includes languages with region inference)
- Stack arenas (7, arena only but we mean it this time!?)
- Neverfree (17, the program is one large arena)
The only thing to note here is that keeping a process pool is a form of 'never free' memory management.
-
The grab bag of things the author finds neat
I think some of these are neat too, I just can't think of a better name.
- Generational References (8)
- MMM++ (10 aka using a free list and a type segmented allocation pool)
- Constraint references (13, effectively ref counting weak references)
- CHERI (16)
- Linear reference counting (4)
It could have done with a nod to Mercury's compile time garbage collection, or noting that a borrow checker effectively does reference counting at compile time, just with very tightly bounded counts.
That's it. I only have time for a short post about this, so forgive me for the comparative brevity and lack of flavor text. That and "Every array resize and hash map resize also causes non determinstic pauses, you can stop blaming garbage collection for it."