4 ms·

> Think of a service that keeps a large cache in memory, or an index built out of millions of small objects that all point at each other. Every one of those poi

> Think of a service that keeps a large cache in memory, or an index built out of millions of small objects that all point at each other. Every one of those pointers has to be followed on every cycle, for as long as the process is up. That's a strange thing to assert, having acknowledged the existence of generational GC.

Someone 2mo ago
Similarly, the statement > 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 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.
- kazinator 2mo ago
  In 1990s C++ we did: void foo::method(const &smart_ptr<thing> x) { ... } The smart pointer passed reference isn't copy-constructed and so no refcount is bumped. It has a scoped lifetime. The calling function owns a reference (baseline correctness assumption or else we are screwed). That caller is suspended while the callee executes.
  - deathanatos 2mo ago
    It's still done. It's not uncommon to see that in Rust: fn foo(x: &Arc<T>) …quite literally borrows the count in the refcount-ed thing. I think you can find similar things in CPython, on the C side of things.
- pjmlp 2mo ago
  Only if reference counting is exposed in the type system, or the standard library types are blessed to the compiler, otherwise there is no way for the compiler to know what to elide.
- hinkley 2mo ago
  But you can also put generational GC on steroids by implementing escape analysis, which creates a separate category of allocations that don’t have to be marked and swept at all. Effectively they were marked the first time the code was run and never have to be marked again. 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.
deathanatos 2mo ago
It occurs to me that I have never seen any description of generational GC that actually notes how that works, though. 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.
- kazinator 2mo ago
  When you get it working, you will figure it out. (Or even well before then; the rest is just bugs.) 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.
shivanshuag 2mo ago
A generational GC might help with some part of the problem but does not solve it entirely. Major collection still happen which will scan everything, just with a reduced frequency. Long libed caches might still have pointers being mutated frequently (like an LRU cache), which will put objects in younger generation. Golang does not have a generational GC. There are examples where long lived caches have been a problem in golang. One example - https://discord.com/blog/why-discord-is-switching-from-go-to-rust https://discord.com/blog/why-discord-is-switching-from-go-to...

Someone 2mo ago

Similarly, the statement > 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 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.

kazinator 2mo ago
In 1990s C++ we did: void foo::method(const &smart_ptr<thing> x) { ... } The smart pointer passed reference isn't copy-constructed and so no refcount is bumped. It has a scoped lifetime. The calling function owns a reference (baseline correctness assumption or else we are screwed). That caller is suspended while the callee executes.
- deathanatos 2mo ago
  It's still done. It's not uncommon to see that in Rust: fn foo(x: &Arc<T>) …quite literally borrows the count in the refcount-ed thing. I think you can find similar things in CPython, on the C side of things.
pjmlp 2mo ago
Only if reference counting is exposed in the type system, or the standard library types are blessed to the compiler, otherwise there is no way for the compiler to know what to elide.
hinkley 2mo ago
But you can also put generational GC on steroids by implementing escape analysis, which creates a separate category of allocations that don’t have to be marked and swept at all. Effectively they were marked the first time the code was run and never have to be marked again. 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.

deathanatos 2mo ago

It occurs to me that I have never seen any description of generational GC that actually notes how that works, though. 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.

kazinator 2mo ago
When you get it working, you will figure it out. (Or even well before then; the rest is just bugs.) 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.

shivanshuag 2mo ago

A generational GC might help with some part of the problem but does not solve it entirely. Major collection still happen which will scan everything, just with a reduced frequency. Long libed caches might still have pointers being mutated frequently (like an LRU cache), which will put objects in younger generation. Golang does not have a generational GC. There are examples where long lived caches have been a problem in golang. One example - https://discord.com/blog/why-discord-is-switching-from-go-to-rust https://discord.com/blog/why-discord-is-switching-from-go-to...