Comment by NobleExpress
3 years ago
I will say that you seem to be stating "smearing that over total execution time tends to give better results" without proof as well. I certainly don't think using atomic operations everywhere and converting every pointer read operation into a write operation is efficient. Yes RC has smaller minheap sizes than tracing GC, but garbage collection is fundamentally a time-space tradeoff and RC is highly optimized for memory efficiency. Also most naive RC implementations don't copy objects so you get heap fragmentation.
Comparing naive RC to tracing GC is non-trivial. In order to have a fair comparison, you'd have to implement naive RC and tracing GC in the same system and then compare them across a set of benchmarks. I personally have never come across a great performance study which compared naive RC to tracing GC.
As I’ve stated repeatedly, RC is super cheap. Seriously. You can do about several billion of them per second. Your malloc/free call is going to be more expensive.
Sure. Atomic counters are relatively expensive. But I’m good designs there’s very few of them. And they easily show up in hotspots if they’re a problem and you fix your object model. The problem with tracing GC is that you have no way to fix it. Most languages that use RC actually avoid most memory allocations/frees by leveraging value composition instead of referential ownership.
I did actually provide proof by the way. Apple’s phones use half the RAM as Android and are at least as equally fast even if you discount better HW. Similarly, any big hyperscaler is unlikely to be using Java for their core performance-critical infrastructure. To me those are pretty clear performance advantages.
> I certainly don't think using atomic operations everywhere and converting every pointer read operation into a write operation is efficient.
I’m unaware of anyone using RC properly is doing this. You only do this when you need to share ownership but you should be doing this exceedingly sparingly. Unique ownership and referential sharing is by far the most common. If you’re passing RC into a function that doesn’t retain ownership beyond its call scope you’re not using RC properly.
> Also most naive RC implementations don't copy objects so you get heap fragmentation.
That’s only kind of true. Good allocators seem to mitigate this problem quite effectively (glibc’s is notably not good at this as compared with the mimalloc and new tcmalloc). But sure, that is kind of a problem. It can be mitigated though by optimizing your allocation patterns once you know that’s the problem (noticing it is by far the hardest bit). And because it’s more manual you can customize your allocator.
Look. I’m not disagreeing about the developer benefits being significant. I’m just saying that good memory management (made fairly easy in Rust) is always going to outperform tracing GC the same way optimized assembly will outperform the compiler. It’s possible that a tracing GC can provide better performance out the gate with minimal optimization vs needing to spend more time optimizing your allocation strategies if you make design mistakes. But remember. A tracing garbage collector still needs to do atomic reads of data structures which potentially requires cross cpu shoot downs. And you still generally need to stop the world (I think that may not be true in some advanced Java Gc algorithms but that’s the exception rather than the rule and you trade off even lower throughput). And I can’t belabor this point enough - languages with RC use it rarely as shared ownership is rarely needed and you can typically minimize where you use it.
Let me give you a real world example. When I was working on the indoor positioning in iOS, I ported our original Java codebase verbatim where I used shared_ptr for almost every Java allocation across the board where I might even potentially be sharing ownership as I wanted to start with safety and optimize later. Not only was the initial version faster than the equivalent Java code (not surprising since c++ will outperform due to no auto boxing, at least at the time), when I got rid of shared_ptr in the particle filter which is a core hot path, it only showed a 5-10% improvement in perf (using Accelerate for the core linear algebra code was way more impactful). The vast majority of it actually came from the fact that all the particles were now living continuously within the vector rather than the overhead of the atomic counting. Just saying. People really overestimate the cost of RC because GC is rarely needed in the first place / when it is ownership shouldn’t be being modified in your hot path. When I worked on Oculus on Link, we used shared_ptr liberally in places because, again, ownership is actually rarely shared - most allocations are unique_ptr.
Edit: note that I’m explicitly distinguish RC (single threaded) from ARC (atomic multi thread RC). Confusingly ARC stands for automatic RC in Apple land although it’s atomic there too. Automatic RC is trickier but again, as Swift and ObjC demonstrate, it’s generally good enough without any serious performance implications (throughput or otherwise).
> As I’ve stated repeatedly, RC is super cheap. Seriously. You can do about several billion of them per second. Your malloc/free call is going to be more expensive.
But that's the whole point. Tracing GC doesn't do malloc/free, and that's where the performance advantages come from. Instead of a complex allocator that has to do lots of work on every free() as well, you get a bump-pointer allocator and move some complexity over to the tracing thread.
And this is especially true if you tend to have large linked data structures.
With all due respect, you are talking about everything, but never had any objective comparison where the RC-tracing GC were the culprit.
> RC is super cheap. Seriously. You can do about several billion of them per second. Your malloc/free call is going to be more expensive.
Yes, and it is completely irrelevant. Good tracing GCs can use a thread local bump allocator, and it can even defragment it automatically later.
> Sure. Atomic counters are relatively expensive. But I’m good designs there’s very few of them. And they easily show up in hotspot
That’s just false, unless you are using something like cachgrind or so — any sane compiler will inline the 2-3 instructions of counter increment/decrements. It is the stereotypical “death by thousands cuts”, never showing up in profiling.
> Most languages that use RC actually avoid most memory allocations/frees by leveraging value composition instead of referential ownership.
I’m sorry but this has absolutely nothing to do with the topic here, there are plenty of tracing GCd languages that can do that as well, like D, Go, C#, Nim just from the top of my head. That’s just a completely different axis.
> I did actually provide proof by the way. Apple’s phones use half the RAM as Android and are at least as equally fast even if you discount better HW
That only proves that RCs use less memory, which as has been pointed out in the thread many times is one of its few positives — it does make sense to use in a mobile phone, but then you finish off with “ big hyperscaler is unlikely to be using Java for their core performance-critical infrastructure” which is just bad logic, and straight up false. Half of the internet literally runs on Java, with heap sizes going up to the terabytes range. Alibaba, many part of Google, Apple’s literally every backend system, Twitter, whole cloud providers(!) all run on the JVM.
> You only do this when you need to share ownership
That’s like.. the point of garbage collection algorithms? Otherwise you why don’t you just randomly increment a counter here and there?!
> Not only was the initial version faster than the equivalent Java code (not surprising since c++ will outperform due to no auto boxing, at least at the time
You literally give the reason why it was faster — you are comparing a sequentially laid out data structure to one of pointers. The effect size of that will trump any concern about which GC algorithm is used, so your point doesn’t apply here at all.
> RC is super cheap. Seriously. You can do about several billion of them per second.
Right. You bump allocate faster, however. RC is an additional operation to the allocation request. Given naive RC can't move objects, it necessarily needs a free-list allocator. Free-list allocators can allocate pretty fast (for the most common object sizes), but can't reach the speeds of bump allocators. Furthermore, bump allocators have better locality of reference than free-list allocators.
Also I've never questioned you can't do non-atomic increments/decrements efficiently. They are exceptionally fast. However you are still converting every pointer read operation into a pointer write operation. The rule of thumb is that there are generally 10x more pointer read operations in a program than pointer write operations. This is why read barriers are also considered more costly than write barriers.
> I did actually provide proof by the way. Apple’s phones use half the RAM as Android and are at least as equally fast even if you discount better HW.
I don't really agree with this statement. There are way too many unknown/unaccounted variables. It could be better hardware, maybe Android has a terrible architecture, and could just be as you said that Swift RC is genuinely better than ART GC or it can be whatever. Point is that it's not a scientific comparison. We don't know if the benefits in iOS come from RC. And we wont be able to know unless we have two systems where all parameters are the exact same _except_ one is using RC and another is using tracing GC, with both systems ran on the same hardware and on the same set of benchmarks.
> That’s only kind of true. Good allocators seem to mitigate this problem quite effectively
Yes. Note that mimalloc literally has a concept of "deferred frees" effectively emulating GC as otherwise freeing an object can result in an unbounded recursive free call (for example, dropping a large linked list).
> I’m just saying that good memory management (made fairly easy in Rust) is always going to outperform tracing GC the same way optimized assembly will outperform the compiler.
Sure. The perfect memory manager is omniscient and knows exactly when an object is not required and will free it. But unfortunately we don't have perfect memory managers yet. So yes I agree in principle, but we have to be pragmatic.
> And I can’t belabor this point enough - languages with RC use it rarely as shared ownership is rarely needed and you can typically minimize where you use it.
I feel like that entirely depends on the problem domain? I don't know where you're getting the "shared ownership is rarely needed" from? Maybe this is true for your problem domain but may not be for others. And if it's true for yours, then great! You can use RC and optimize your programs that way.
> A tracing garbage collector still needs to do atomic reads of data structures which potentially requires cross cpu shoot downs.
Sure. GC metadata needs to be accessed and updated atomically. 100% agree with you. The order of magnitude of those operations is likely much less than what you would get with naive RC though.
> as Swift and ObjC demonstrate, it’s generally good enough without any serious performance implications (throughput or otherwise).
In one of my comments about Swift in this thread, the two papers I linked see up to 80% of the benchmark execution time being dominated by ARC operations! I will note that the papers are around 6-7 years old so the situation might have drastically changed since then, but I haven't personally found many new/contemporary evaluations of Swift RC.