That's a strange thing to assert, having acknowledged the existence of generational GC.
> Reference counting also has its own running cost, paid on every copy of a pointer you make and every time you drop one.
isn’t 100% true. It’s not necessarily on every copy or drop. Compilers can (and do) elide reference count updates if they can proof they aren’t needed, and can even skip allocating room for reference counts if they can proof it isn’t needed (example: a local object that doesn’t escape its scope)
I also find it a miss that the article doesn’t discuss memory usage. A garbage-collected program needs more memory to match the performance of the equivalent manually managed language.
https://dl.acm.org/doi/10.1145/1094811.1094836 says you need to give it 5 times the memory, but that’s from 2005 and likely outdated.
void foo::method(const &smart_ptr<thing> x) { ... }
fn foo(x: &Arc<T>)
I think you can find similar things in CPython, on the C side of things.
What people forget too is that new and destroy in C++ aren’t exactly cheap either. As far back as Java 5 the hotspot people were bragging on how new in Java was cheaper than new in C++, closer to stack allocation speed.
Of course if you look at any Java library other than ones intended for embedded or HFT systems, you will see Jevons’ Paradox at play. Made allocation cheap, and everyone allocates the hell out of everything, eating up the gains and then some.
But at the same time, the architectural simplicity of not having to worry about object lifetimes makes APIs simpler, which allows people to invest that brain power into making them more sophisticated in other dimensions. Watching Rust try to get itself doubly linked lists was strange to watch from the bleachers.
If we have two generations, young and old, we obviously can't simply "just collect in the young generation" — which I feel like is exactly what most generational GC descriptions say. If we only traced young objects, we could very well miss an old object pointing at a young one, collect the younger object, and now we've got a dangling pointer.
So there must be some book-keeping to avoid tracing everything (or what'd be the point of generations), but I have no idea of what that book-keeping is, or its cost.
> Show me your code and conceal your data structures, and I shall continue to be mystified. Show me your data structures, and I won't usually need your code; it'll be obvious.
I wrote one for TXR Lisp which there are no generation heaps; but objects have a generation. In the same heap, you can have adjacent (unrelated) objects that are in different generations. Objects never move from their heap; they keep their position in the same heap over their lifetime.
The allocator therefore records the new generations in a fresh log, which serves as the nursery. When that log gets full, a pass is triggered.
Implementations with separate heaps (typically copying collectors) allocate in a nursery heap and promote objects from there, but it is conceptually similar.
In the marking phase, we do not process this nursery. We start at the usual root pointers: stack, globals and proceed with normal marking, like in a pure mark-sweep collector (or a full pass), with a small modification: whenever we hit an old gen object, we skip it. We assume that the old gen object is reachable, and every object reachable through it is similarly an old-gen object. This is where the generational algorithm wins, chopping down the graph of objects to be marked, possibly drastically so.
Where the nursery/fresh log comes in is the sweep phase. Because we know that we did not traverse any old generation objects, it would be wasteful to do a full sweep. In the case of the fresh log, we sweep just through the fresh log. Anything in the fresh log that is reachable is promoted to the old generation. Anything not reachable is reclaimed: either immediately or through the finalization treadmill, if applicable. The fresh log is then reset to empty. In the case of a nursery, we similarly just sweep through the nursery heap and promote (by copying) reachable objects to the old generation, reclaiming the rest. The nursery is empty.
There may be additional structures. Note that we have the assumption that old objects only point to old. But what if (it is allowed that) the program mutates an old object to point to a newly allocated new one? That would break the assumption. We can make the program (code generated by compiler or whatever) report whenever that happens.
In the TXR Lisp implementation of generational GC, mutation of old objects is handled via two strategies. A single value assignment of a young object to a field in an old one will cause the young object to be appended to a "check" log. In some cases, this is not practical for various reasons. For instance, an operation mutates a large number of fields of the same object (e.g. array). In such cases we add the old objects to a "mutated" log. The objects added to both arrays have their generation field reset to -1: neither young (0) nor old (1).
Both the check log and mutated log are marked during marking. The check log contains only young objects and so sweeping those is already taken care of by the freshlog, it needs not be visited during the sweep phase.
The mutated log is processed during sweep in order to reset the generations from -1 back to 1.
When the check and mutated logs fill up, GC is not triggered immediately then, but the flag is set for the next GC to be a full one. What that does is turn off the mechanism: since we know a full GC is coming, we don't have to record mutations of old objects pointing to new.
Careful; just because you only collect in the new generation doesn't mean that you only trace the new generation. From my understanding a rudimentary generational GC design is to include the old generation in the GC roots so you don't need to examine everything in the new generation - if it's not reachable from the roots it's implicitly dead, and the latter category is assumed to apply to most objects in the new generation under the generational hypothesis.
Well, then I suppose you're saying the up-thread comment is wrong?
TFA:
> Every one of those pointers has to be followed on every cycle
The comment:
> That's a strange thing to assert, having acknowledged the existence of generational GC.
Which would imply that's not the case, i.e., that we're not considering every pointer in every GC sweep. (Which, again, I thought was largely the point of generational GCs: to make sweeps cheap by not considering every pointer.)
I guess if it's really the sweep that's the expensive part, then perhaps doing a full walk is fine.
> generational GC design is to include the old generation in the GC roots so you don't need to examine everything in the new generation
I'm assuming roots (stack references to objects) are separate from generations (which heap objects belong to).
I suppose if you added old objects to the set of roots, that'd also solve it, but that's the same as "every one of those pointers has to be followed on every cycle".
The sibling post thinks writes are made more expensive by tainting/young-ifying objects that get written to. In that way, we prevent an old object from ever pointing at a new one — at the cost of writes now being more than a write.
Edit: Yeah, here's [a note](https://chromium.googlesource.com/v8/v8/+/refs/heads/13.3.25...) about how Chrome implements it. There is additional book-keeping and cost to writes.
I think "every one of those pointers has to be followed on every cycle" as a blanket statement is not correct. It's true for some GC designs and not true for others.
> I'm assuming roots (stack references to objects) are separate from generations (which heap objects belong to).
Roots are just where you start tracing from. You can include older generations in them (or even subsets thereof), but you're by no means required to.
> but that's the same as "every one of those pointers has to be followed on every cycle".
Sure, but my point there was just that just collecting the new generation doesn't have to imply that you're only tracing the new generation. I guess I should have added a "necessarily" somewhere in my original comment.
> There is additional book-keeping and cost to writes.
From my understanding the bookkeeping there is effectively to be able to determine the set of roots to use when tracing/collecting the new generation.
Then if the language allows mutation of objects, special consideration has to be given to old objects that were mutated to point to new ones. You can treat those as additional roots; the graph of young objects reachable from a mutated old object is reachable. (Considered so on the assumption of the old object being reachable, which we can only disprove by doing a full scan.)