37 ms·

And yet, the reason tracing GCs are chosen by virtually all high-performance languages that heavily rely on GC is that they've been found to be faster in practi

by pron 3y ago

And yet, the reason tracing GCs are chosen by virtually all high-performance languages that heavily rely on GC is that they've been found to be faster in practice for the common workloads. One of the reasons why your intuition is not so straightforward is that a tracing GC needs to do no work whatsoever when the number of references is zero. One of the common ways to teach the basics of GC is by starting out as looking at tracing and refcounting as duals: refcounting needs to work to free objects, while tracing works to keep them alive. If you thinking in terms of what work needs to be done to promptly determine when an object becomes garbage, then you're already not thinking in terms of tracing, because tracing never actually needs to learn about when an object becomes garbage (this isn't actually true when they do reference processing, but that's another story). Or, if you want to think about it another way, in a tracing collector there are already only two cases no matter how many pointers there are to an object: reachable or not, i.e. the same one and zero as in your case, only there isn't even a need to ever set the counter to zero. However, in principle tracing and refcounting can be quite similar (https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/unified-theory-gc/ https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/unifie...) in their behaviour, but in practice most refcounting GCs in industry use are crude, and don't match the performance of tracing GCs in common use, which are quite sophisticated.

tomp 3y ago
> And yet, the reason tracing GCs are chosen by virtually all high-performance languages that heavily rely on GC is that they've been found to be faster in practice for the common workloads. I disagree. IMO the reason is simplicity, most languages don’t want to burden programmers with lifetimes and/or soft references. Rust and Swift, both high-performance languages targeting specific niches, chose differently. Both largely for reasons of predictability, lower latency, lower memory use (which you admitted above) as well as lower memory trashing.
- pron 3y ago
  > IMO the reason is simplicity, most languages don’t want to burden programmers with lifetimes and/or soft references. I'm talking about languages that already use a GC as the primary heap management mechanism. Any kind of GC algorithm, whether tracing or refcounting, frees developers from thinking about lifetimes, but languages that primarily rely on GC and care about performance almost always pick tracing. The only languages that choose a refcounting GC are either those that care little about performance (Python) or those that don't rely heavily on GC (Rust). > Both largely for reasons of predictability, lower latency, lower memory use Refcounting offers worse latency, worse predictability [1] (compared to modern low-latency tracing GCs, like ZGC), and worse throughput; it does offer a significantly lower memory footprint. The reason Rust chose refcounting is primarily because it doesn't rely on the GC heavily and so it might as well use a crude GC (and enjoy the lower effort of implementing it as well as the lower footprint), as a crude refcounting GC is usually better than a crude tracing GC. Furthermore, an sophisticated tracing GC is not a great fit for languages like Rust or C++ because it requires a more elaborate code generation and some "magical" mutator thread behaviour, when low-level languages like the generated code to be as close to the source code as possible. This isn't so much predictability of performance, but predictability of the generated code and the behaviour of mutators (in terms of lowering the surprise of "why is my thread doing _that_ now?" when observed at a low level). For example, with ZGC, a mutator thread may find itself moving an object when accessing it; this is surprising at a low level -- which may not be a good fit for a low-level language -- even though it ends up offering better performance predictability overall. On the other hand, a mutator thread doing work freeing memory with a refcounting GC when it's dropping a reference to it may offer worse latency and worse predictability overall, but it's not as surprising at a lower level in the sense that it's easy to understand why it's doing that. As for Swift, I think it picked a refcounting algorithm because it cares about memory footprint (most Swift applications run in memory-constrained environments) and because some unique language features allow to reduce the cost of refcounting sufficiently for a simple refcounting GC to be acceptable. [1]: Again, not in principle (as both refcounting and tracing can converge to a similar behaviour) but as practiced by most refcounting GCs in industry use.
  - pkolaczk 3y ago
    > The only languages that choose a refcounting GC are either those that care little about performance (Python) or those that don't rely heavily on GC (Rust). Not true. The creators of Swift chose RC exactly for performance reasons: low memory footprint AND low latency. //edit: ah, you actually admitted it at the end. So you’re contradicting yourself.
    - pron 3y ago
      Refcounting's latency is worse, not better than modern tracing. Swift chose refcounting not because it performs as well as tracing, but because they managed to get it to perform acceptably for their needs (with special language features), and they really care about footprint. If someday there's some advancement in refcounting that makes it better (or even as good but with significantly lower footprint), you'll see all languages that currenly use tracing switch quickly. For the time being, though, tracing is winning.
      - pkolaczk 3y ago
        Refcounting introduces zero latency into code that doesn't allocate / free. Tracing can pause such code. Zero latency is better than non-zero.
        pron 3y ago
        Modern concurrent collectors like ZGC only pause threads to synchronize state transitions -- there is no collection work done in STW pauses (or any work that grows with the size of the working set or total heap) -- and not for a longer duration than the OS does for various things. Certainly the average impact on latency is lower for concurrent tracing collectors. These days, tracing collectors offer better throughput, latency and predictability than refcounting, while refcounting offers better footprint. That's the main tradeoff, and I mentioned some secondary ones (re ease of implementation and low-level "surprises") before.
anamax 3y ago
Not so fast. A tracing GC, by definition, traces. (Not to mention that tracing keeps the live objects alive.) My important-to-me application has a large amount of "live forever" memory and, at any one time, a fairly small amount of memory used by short-lived objects. However, it allocates and then discards those objects very frequently. Let's say that it has 100MB of "live-forever" and, at any one time, 1MB of transient objects. Moreover, the vast majority of the pointers in the 100MB are to other parts of "live-forever." A GC-based approach will allocate Nx1MB of transient objects and then trace the pointers in that 100MB to free all but the currently in use 1MB of transient objects. The vast majority of the traces are a waste of time, but GC can't know that. Moreover, it will tromp through the address space, trashing the cache. A ref-counting approach will have two RMWs for every pointer assignment and the objects modified will almost certainly be in the cache. It's not clear that those RMWs will cost more than tracing that 100MB. Note that the 1MB is probably in L3. If N is large enough to keep the number of traces down, the Nx1MB will cache-fault like crazy. (Remember that the 100MB is also subject to caching.) That 1MB won't use more pages than the Nx1MB.
- pron 3y ago
  > The vast majority of the traces are a waste of time, but GC can't know that It can, it does, and you've basically described generational collection. Generational GCs try to only trace through recently allocated objects, and only bother with old ones if they can't free enough memory. Not wasting time on unnecessary traces is much of the point of generational GCs. More modern GCs like OpenJDK's G1 go some steps further. They're region-based, and they keep track of inter-region pointers that tell them the likelihood that a region may benefit from compaction. > A ref-counting approach will have two RMWs for every pointer assignment and the objects modified will almost certainly be in the cache. A tracing GC does that without any bookkeeping. An object born and dead between young-gen collections will never even make its existence known to the GC (generational GCs usually only need to learn about an object's existence once it's promoted); it will never have been visited and traced. The old objects would not have been traced either (in that interim) if few enough young objects survive. In fact, in such ideal situation where some fixed number of objects live forever and some large number of objects are continuously allocated and die, a generational GC will effectively need to do nothing: the old objects will have been promoted into the old generation, and the GC won't have to ever look at them again if there's always sufficient RAM, while the young objects will be allocated by a pointer bump, and when it reaches the end the GC will wake up and want to start tracing, but will find that all the roots still point into the old generation, so the young generation will simply disappear (i.e. the allocation pointer will be reset to the beginning). The GC in this case requires zero operations (well, except for some fixed number required to notice it has nothing to do). > It's not clear that those RMWs will cost more than tracing that 100MB. It's clear that they cost more than not tracing it, which is what a generational GC won't do. > Note that the 1MB is probably in L3. If N is large enough to keep the number of traces down, the Nx1MB will cache-fault like crazy That prompt reclamation has some benefits on locality is true, but so does compaction. The problem isn't so much cache faults (because we're talking about writes, which fill up the write buffer, not reads that cause stalls) but exhausting the memory buffer. This can and does happen with super-high allocation rates (which makes it an interesting problem), and indeed the memory bus's bandwidth is sometimes the limiting factor on throughput, but we're talking about allocation rates that far exceed those that common refcounting GCs can deal with anyway. It's been well established by now that tracing GCs offer better performance than (crude) refcounting GCs, which is why they're the choice of every high-performance language that heavily relies on GC. The price you pay for modern tracing GCs is in memory footprint and in cost of implementation. There is, however, constant research in GC, and some advances in refcounting might make it more appealing, but we're talking about sophisticated implementations that are comparable in complexity to tracing.

by pron 3y ago

tomp 3y ago

> And yet, the reason tracing GCs are chosen by virtually all high-performance languages that heavily rely on GC is that they've been found to be faster in practice for the common workloads. I disagree. IMO the reason is simplicity, most languages don’t want to burden programmers with lifetimes and/or soft references. Rust and Swift, both high-performance languages targeting specific niches, chose differently. Both largely for reasons of predictability, lower latency, lower memory use (which you admitted above) as well as lower memory trashing.

pron 3y ago
> IMO the reason is simplicity, most languages don’t want to burden programmers with lifetimes and/or soft references. I'm talking about languages that already use a GC as the primary heap management mechanism. Any kind of GC algorithm, whether tracing or refcounting, frees developers from thinking about lifetimes, but languages that primarily rely on GC and care about performance almost always pick tracing. The only languages that choose a refcounting GC are either those that care little about performance (Python) or those that don't rely heavily on GC (Rust). > Both largely for reasons of predictability, lower latency, lower memory use Refcounting offers worse latency, worse predictability [1] (compared to modern low-latency tracing GCs, like ZGC), and worse throughput; it does offer a significantly lower memory footprint. The reason Rust chose refcounting is primarily because it doesn't rely on the GC heavily and so it might as well use a crude GC (and enjoy the lower effort of implementing it as well as the lower footprint), as a crude refcounting GC is usually better than a crude tracing GC. Furthermore, an sophisticated tracing GC is not a great fit for languages like Rust or C++ because it requires a more elaborate code generation and some "magical" mutator thread behaviour, when low-level languages like the generated code to be as close to the source code as possible. This isn't so much predictability of performance, but predictability of the generated code and the behaviour of mutators (in terms of lowering the surprise of "why is my thread doing _that_ now?" when observed at a low level). For example, with ZGC, a mutator thread may find itself moving an object when accessing it; this is surprising at a low level -- which may not be a good fit for a low-level language -- even though it ends up offering better performance predictability overall. On the other hand, a mutator thread doing work freeing memory with a refcounting GC when it's dropping a reference to it may offer worse latency and worse predictability overall, but it's not as surprising at a lower level in the sense that it's easy to understand why it's doing that. As for Swift, I think it picked a refcounting algorithm because it cares about memory footprint (most Swift applications run in memory-constrained environments) and because some unique language features allow to reduce the cost of refcounting sufficiently for a simple refcounting GC to be acceptable. [1]: Again, not in principle (as both refcounting and tracing can converge to a similar behaviour) but as practiced by most refcounting GCs in industry use.
- pkolaczk 3y ago
  > The only languages that choose a refcounting GC are either those that care little about performance (Python) or those that don't rely heavily on GC (Rust). Not true. The creators of Swift chose RC exactly for performance reasons: low memory footprint AND low latency. //edit: ah, you actually admitted it at the end. So you’re contradicting yourself.
  - pron 3y ago
    Refcounting's latency is worse, not better than modern tracing. Swift chose refcounting not because it performs as well as tracing, but because they managed to get it to perform acceptably for their needs (with special language features), and they really care about footprint. If someday there's some advancement in refcounting that makes it better (or even as good but with significantly lower footprint), you'll see all languages that currenly use tracing switch quickly. For the time being, though, tracing is winning.
    - pkolaczk 3y ago
      Refcounting introduces zero latency into code that doesn't allocate / free. Tracing can pause such code. Zero latency is better than non-zero.
      - pron 3y ago
        Modern concurrent collectors like ZGC only pause threads to synchronize state transitions -- there is no collection work done in STW pauses (or any work that grows with the size of the working set or total heap) -- and not for a longer duration than the OS does for various things. Certainly the average impact on latency is lower for concurrent tracing collectors. These days, tracing collectors offer better throughput, latency and predictability than refcounting, while refcounting offers better footprint. That's the main tradeoff, and I mentioned some secondary ones (re ease of implementation and low-level "surprises") before.

anamax 3y ago

Not so fast. A tracing GC, by definition, traces. (Not to mention that tracing keeps the live objects alive.) My important-to-me application has a large amount of "live forever" memory and, at any one time, a fairly small amount of memory used by short-lived objects. However, it allocates and then discards those objects very frequently. Let's say that it has 100MB of "live-forever" and, at any one time, 1MB of transient objects. Moreover, the vast majority of the pointers in the 100MB are to other parts of "live-forever." A GC-based approach will allocate Nx1MB of transient objects and then trace the pointers in that 100MB to free all but the currently in use 1MB of transient objects. The vast majority of the traces are a waste of time, but GC can't know that. Moreover, it will tromp through the address space, trashing the cache. A ref-counting approach will have two RMWs for every pointer assignment and the objects modified will almost certainly be in the cache. It's not clear that those RMWs will cost more than tracing that 100MB. Note that the 1MB is probably in L3. If N is large enough to keep the number of traces down, the Nx1MB will cache-fault like crazy. (Remember that the 100MB is also subject to caching.) That 1MB won't use more pages than the Nx1MB.

pron 3y ago
> The vast majority of the traces are a waste of time, but GC can't know that It can, it does, and you've basically described generational collection. Generational GCs try to only trace through recently allocated objects, and only bother with old ones if they can't free enough memory. Not wasting time on unnecessary traces is much of the point of generational GCs. More modern GCs like OpenJDK's G1 go some steps further. They're region-based, and they keep track of inter-region pointers that tell them the likelihood that a region may benefit from compaction. > A ref-counting approach will have two RMWs for every pointer assignment and the objects modified will almost certainly be in the cache. A tracing GC does that without any bookkeeping. An object born and dead between young-gen collections will never even make its existence known to the GC (generational GCs usually only need to learn about an object's existence once it's promoted); it will never have been visited and traced. The old objects would not have been traced either (in that interim) if few enough young objects survive. In fact, in such ideal situation where some fixed number of objects live forever and some large number of objects are continuously allocated and die, a generational GC will effectively need to do nothing: the old objects will have been promoted into the old generation, and the GC won't have to ever look at them again if there's always sufficient RAM, while the young objects will be allocated by a pointer bump, and when it reaches the end the GC will wake up and want to start tracing, but will find that all the roots still point into the old generation, so the young generation will simply disappear (i.e. the allocation pointer will be reset to the beginning). The GC in this case requires zero operations (well, except for some fixed number required to notice it has nothing to do). > It's not clear that those RMWs will cost more than tracing that 100MB. It's clear that they cost more than not tracing it, which is what a generational GC won't do. > Note that the 1MB is probably in L3. If N is large enough to keep the number of traces down, the Nx1MB will cache-fault like crazy That prompt reclamation has some benefits on locality is true, but so does compaction. The problem isn't so much cache faults (because we're talking about writes, which fill up the write buffer, not reads that cause stalls) but exhausting the memory buffer. This can and does happen with super-high allocation rates (which makes it an interesting problem), and indeed the memory bus's bandwidth is sometimes the limiting factor on throughput, but we're talking about allocation rates that far exceed those that common refcounting GCs can deal with anyway. It's been well established by now that tracing GCs offer better performance than (crude) refcounting GCs, which is why they're the choice of every high-performance language that heavily relies on GC. The price you pay for modern tracing GCs is in memory footprint and in cost of implementation. There is, however, constant research in GC, and some advances in refcounting might make it more appealing, but we're talking about sophisticated implementations that are comparable in complexity to tracing.