The problem with precise GC is usually the same problem with malloc/free - if you allocate in an inner loop you have to free in that inner loop and the bookkeeping kills throughput.
I don’t know Go. Is that the problem we are seeing here?
One of the realtime GC solutions that stuck with me is amortized GC, which might be appropriate to Go.
Instead of moving dead objects immediately to the free list you “just” need to stay ahead of allocation. You can accomplish that by freeing memory every time you allocate memory - but not a full GC, just finishing the free of a handful of dead objects.
That puts an upper bound on allocation time without a lower bound on reallocation time.
Precise means that on a GC cycle, only true pointers to heap allocated objects are identified as roots, which means that an unreferenced object cannot be kept alive by a value that happens to have a similar bit pattern as a heap pointer. This guarantees that unreferenced objects are eventually cleaned up, but not that this cleanup happens immediately, certainly not as part of a busy loop. (Unless the system runs out of memory, but in that case, a GC iteration is required anyway.)
Since reference counting is GC, isn't reference counting a form of precise GC? That's certainly the scenario I had in mind reading what OP wrote where deallocation within a hot loop would be possible.
Tracing is the technique to find all alive objects from roots. You dereference a pointer to find there some object, and then to recursively iterate over pointers in that object. But before that you need to choose what to use as roots, and here is a difference: you can be precise with choosing the roots, or to err on a conservative side, choosing more roots than you actually need.
This classification was invented decades ago. I think in 1970s or even earlier. Garbage collection is a large field with lots of ideas and research behind it. There are different approaches to structure the heap, to find roots, to trace living objects. These different approaches oftentimes (but not always) replaceable, you can change how you find roots while leaving other things intact.
GC is a large field, it has its own terminology, and instead of asking "why are we inventing terminology", I'd ask "who we are to change the existing terminology".
if you allocate in an inner loop you have to free in that inner loop and the bookkeeping kills throughput
I wonder if there's anything that automatically defers collection within a loop and collects the garbage after the loop is exited. Something like Obj-C's old @autoreleasepool but inserted automatically. Static analysis has gotten so fancy that that might not be a terrible idea once you work out all the nuances (e.g. what if the loop is too short, nested loops, what happens when your entire program is a loop like game loops, etc). Could be the best of both worlds.
But generally I think it turns out that in refcounted GC systems you end up just knowing to not allocate/free in your hot loop or if you're doing it in a loop then it's probably not the thing your hot loop is dominated by.
Generational GC - particularly with escape analysis - can make those temp objects just slightly more expensive than stack allocation.
The odd thing about GenGC is that it punishes you for trying to recycle old objects yourself. You create much more pressure to scan the old generation by doing so, which is expensive. If you have the available memory it’s often better to build a new object and swap it for the retained reference to the old one at the end when you’re done (poor man’s MVCC as well if the switch takes a couple context switches to finish)
Comments
The problem with precise GC is usually the same problem with malloc/free - if you allocate in an inner loop you have to free in that inner loop and the bookkeeping kills throughput.
I don’t know Go. Is that the problem we are seeing here?
One of the realtime GC solutions that stuck with me is amortized GC, which might be appropriate to Go.
Instead of moving dead objects immediately to the free list you “just” need to stay ahead of allocation. You can accomplish that by freeing memory every time you allocate memory - but not a full GC, just finishing the free of a handful of dead objects.
That puts an upper bound on allocation time without a lower bound on reallocation time.
That's not what precise GC means.
Precise means that on a GC cycle, only true pointers to heap allocated objects are identified as roots, which means that an unreferenced object cannot be kept alive by a value that happens to have a similar bit pattern as a heap pointer. This guarantees that unreferenced objects are eventually cleaned up, but not that this cleanup happens immediately, certainly not as part of a busy loop. (Unless the system runs out of memory, but in that case, a GC iteration is required anyway.)
Since reference counting is GC, isn't reference counting a form of precise GC? That's certainly the scenario I had in mind reading what OP wrote where deallocation within a hot loop would be possible.
No it’s usually called conservative unless you have loop detection.
Oof. We used to just call that tracing.
Tracing is the technique to find all alive objects from roots. You dereference a pointer to find there some object, and then to recursively iterate over pointers in that object. But before that you need to choose what to use as roots, and here is a difference: you can be precise with choosing the roots, or to err on a conservative side, choosing more roots than you actually need.
That is too subtle of a distinction. Tracing demands roots. Why are we inventing a new classification where we have accurate versus inaccurate roots?
This classification was invented decades ago. I think in 1970s or even earlier. Garbage collection is a large field with lots of ideas and research behind it. There are different approaches to structure the heap, to find roots, to trace living objects. These different approaches oftentimes (but not always) replaceable, you can change how you find roots while leaving other things intact.
GC is a large field, it has its own terminology, and instead of asking "why are we inventing terminology", I'd ask "who we are to change the existing terminology".
i think it is still tracing, it's just a matter of identifying possible roots versus actual roots and constraints that fall out from that.
I wonder if there's anything that automatically defers collection within a loop and collects the garbage after the loop is exited. Something like Obj-C's old @autoreleasepool but inserted automatically. Static analysis has gotten so fancy that that might not be a terrible idea once you work out all the nuances (e.g. what if the loop is too short, nested loops, what happens when your entire program is a loop like game loops, etc). Could be the best of both worlds.
But generally I think it turns out that in refcounted GC systems you end up just knowing to not allocate/free in your hot loop or if you're doing it in a loop then it's probably not the thing your hot loop is dominated by.
Generational GC - particularly with escape analysis - can make those temp objects just slightly more expensive than stack allocation.
The odd thing about GenGC is that it punishes you for trying to recycle old objects yourself. You create much more pressure to scan the old generation by doing so, which is expensive. If you have the available memory it’s often better to build a new object and swap it for the retained reference to the old one at the end when you’re done (poor man’s MVCC as well if the switch takes a couple context switches to finish)
Any tracing GC, conservative or precise, generational or not, already does this. Hinkley is wrong about what "conservative" and "precise" mean.