5 ms·

Reference counting is great. I used to be skeptical but I'm a complete convert after using Objective-C. The old myth about GC was that it was slow. Nowadays th

Reference counting is great. I used to be skeptical but I'm a complete convert after using Objective-C. The old myth about GC was that it was slow. Nowadays that's usually false, but what is true that it wastes a lot of memory, or has long pauses, or both. The old myth about reference counting, on the other hand, is that uncollected cycles are a problem, but in practice they're usually not that hard to find and fix. Reference counting is a bit slower, but it doesn't waste memory and doesn't pause. So it's great for throughput. And throughput is very often more important than overall performance! For anything with a UI, you want maximum throughput. For anything on the server side that's realtime, or even indirectly user-facing, you want maximum throughput. The only time you want performance over throughput is batch jobs, which I reckon crop up less often than you expect. (Edit to add: on memory-constrained devices, you might not want the memory overhead of GC even for batch jobs.)

chadaustin 10y ago
You probably mean minimal latency, not maximum throughput. GC generally has higher throughput at the cost of latency and higher peak memory usage. :)
- z92 10y ago
  Parallel GC's throughput is limited by how hard the parallel thread is working as described in the article and which was the point.
  - chadaustin 10y ago
    But he's comparing to reference counting, where you pay a substantial throughput penalty round-tripping to RAM (especially if atomic) and don't get the benefit of a bump allocator.
- kartickv 10y ago
  I've seen it repeated many times that GC has higher latency, but is there a benchmark? Imagine writing a Mac app, once with refcounting, and once with GC, and seeing which one has the longer pause time. I can think of cases where GC has better latency, like deallocating a huge linked list. That will introduce a higher latency with refcounting and with manual deletion (like C) compared to GC, where the main thread doesn't need to block while traversing the list. Or does such a case not happen much in practice?
  - iainmerrick 10y ago
    You mainly notice it in mobile apps, since you want silky smooth 60fps scrolling there. A pause longer than 5 or 10ms can easily cause you to drop a frame.
    - kartickv 10y ago
      Hard to attribute that to GC.
      - iainmerrick 10y ago
        Why hard? On Android, the GC will print a log entry telling you how long it took! In my experience, aside from badly-written algorithms that just do too much work on the wrong thread, the main causes of momentary glitches are GC and I/O. Unfortunately you have limited control over those in application code (just using too much memory can cause some I/O churn). On mobile, the GPU drivers are often badly written and will give you random hiccups that can ultimately be traced back to I/O. Not to turn this into an Apple vs Android battle, I hope, but I think this is an important point that is often overlooked -- Apple's hardware and software designs are really well-targeted to minimize those kind of glitches. They don't use GC and they always use very fast (AKA expensive) flash memory. So whatever else their flaws, Apple devices tend to have smoothly-animated UIs.
- iainmerrick 10y ago
  Oops, you're right! I think I had in mind something like "guaranteed throughput" but "consistent low latency" is definitely a better way to put it.
cmrdporcupine 10y ago
There are cycle collecting reference counting algorithms, that due a limited trace within a subset of the object graph to detect and remove cycles. I am still not clear on why Apple didn't go that direction. Reference counting will still potentially pause though, when freeing large graphs of objects.
- dilap 10y ago
  Yeah, but the pause is completely deterministically in control of your program. Doing cycle collection basically ends up as hard as full GC right? Annotating with weak is not a big deal.
  - kartickv 10y ago
    > The pause is completely deterministically in control of your program. In theory. In practice, the programmer may not be able to reproduce the pause to diagnose and fix it, or it may not bubble up to the top of the priority list. Whereas with a GC, this problem may not occur at all in the first place. The question is whether such cases (large object graph or linked list) occur often enough in practice to be worth bothering about.
  - cmrdporcupine 10y ago
    > Doing cycle collection basically ends up as hard as full GC right? Not really. Yes you do need to have the ability to trace the object graph. But the actual algorithm isn't that bad. I implemented this in C++ (for "fun" for a pet language VM i wrote) 15 years ago: http://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon01Concurrent.pdf http://researcher.watson.ibm.com/researcher/files/us-bacon/B...
    - bjourne 10y ago
      That's interesting! I also implemented that algorithm for cycle collection (https://github.com/bjourne/c-examples/blob/master/libraries/collectors/ref-counting-cycles.c https://github.com/bjourne/c-examples/blob/master/libraries/...) and I found that like the GP states that it wasn't worth it. The problem was that there so many objects that were potentially part of garbage cycles that it required scanning a too large part of the heap. Cycle detection took about 70% as long a full mark and sweep collection so I didn't think it was worth it considering how complicated the algorithm was. Is your implementation open source? If so, I'd love to see it and compare results.
imagist 10y ago
In practical terms, are there even many cases where cycles are desirable? The only case I can think of is threads (two threads communicating with each other). Most cycles I have seen even in GC'd languages were bad designs.
- mac01021 10y ago
  https://en.m.wikipedia.org/wiki/Dancing_Links https://en.m.wikipedia.org/wiki/Dancing_Links is one.
kartickv 10y ago
This is an insightful comment. Thanks. I wonder how things would change if a second core was sitting idle anyway, like in a mobile app that does everything on the main thread. Would it then make sense to utilise the second core for greater performance? Imagine memory isn't a problem — some phones have plenty of memory, like 6GB on a OnePlus. Unrelated to all the above, and related to your point about uncollected cycles not being a problem with refcounting, it does impose an overhead, like remember to use weak pointers to delegates in Objective-C. It's not as seamless to the programmer as GC. You can argue that it is (not) worth it, but there's no question it's more work for the programmer.
- iainmerrick 10y ago
  Apple's phones tend to have less memory, and fewer (but faster) cores. Along with Objective-C's reference counting, I think those are very smart choices for typical mobile app workloads. In principle having lots of cores available is great, but in practice it's hard to utilise them effectively without also using tons of memory and/or battery.
titzer 10y ago
Reference counting does not scale to multi-threaded programs well. Keeping reference counts up to date across multiple threads is maddeningly and frightenly hard to do efficiently. By the time you correctly solve the concurrent update problem for essentially every access the program does, you have a very complicated memory management system that incurs overhead on every single operation. Compare that with a GC that imposes overhead (usually) only on writes to objects, not "writes" to the stack or local variables going out of scope. Reference counting also incurs overhead for reading from objects. Empirical studies have shown that reads outnumber writes 10x to 1 usually. Why would you consider it to be just a _bit_ slower? And of course reference counting pauses. Killing one object (its count dropping to zero) may cause a chain reaction of objects whose reference counts to drop to zero and need to be cleaned up. The difference is that you now suffer work proportional to the _dead_ data of the program. In comparison, a tracing GC does work proportional to the _live_ objects.
- ngrilly 10y ago
  Great explanation! Thanks!
- staticassertion 10y ago
  > Reference counting does not scale to multi-threaded programs well. Keeping reference counts up to date across multiple threads is maddeningly and frightenly hard to do efficiently. Is this not just a matter of using an atomic reference count?
  - iainmerrick 10y ago
    Yes, but atomics are pretty slow.
    - staticassertion 10y ago
      I guess, but that doesn't seem that bad. > maddeningly and frightenly hard to do efficiently. It definitely doesn't seem maddening or frightening. I'm not saying a GC isn't stricly better (because I'm unsure either way) but arc doesn't seem like some awful thing.

chadaustin 10y ago

You probably mean minimal latency, not maximum throughput. GC generally has higher throughput at the cost of latency and higher peak memory usage. :)

z92 10y ago
Parallel GC's throughput is limited by how hard the parallel thread is working as described in the article and which was the point.
- chadaustin 10y ago
  But he's comparing to reference counting, where you pay a substantial throughput penalty round-tripping to RAM (especially if atomic) and don't get the benefit of a bump allocator.
kartickv 10y ago
I've seen it repeated many times that GC has higher latency, but is there a benchmark? Imagine writing a Mac app, once with refcounting, and once with GC, and seeing which one has the longer pause time. I can think of cases where GC has better latency, like deallocating a huge linked list. That will introduce a higher latency with refcounting and with manual deletion (like C) compared to GC, where the main thread doesn't need to block while traversing the list. Or does such a case not happen much in practice?
- iainmerrick 10y ago
  You mainly notice it in mobile apps, since you want silky smooth 60fps scrolling there. A pause longer than 5 or 10ms can easily cause you to drop a frame.
  - kartickv 10y ago
    Hard to attribute that to GC.
    - iainmerrick 10y ago
      Why hard? On Android, the GC will print a log entry telling you how long it took! In my experience, aside from badly-written algorithms that just do too much work on the wrong thread, the main causes of momentary glitches are GC and I/O. Unfortunately you have limited control over those in application code (just using too much memory can cause some I/O churn). On mobile, the GPU drivers are often badly written and will give you random hiccups that can ultimately be traced back to I/O. Not to turn this into an Apple vs Android battle, I hope, but I think this is an important point that is often overlooked -- Apple's hardware and software designs are really well-targeted to minimize those kind of glitches. They don't use GC and they always use very fast (AKA expensive) flash memory. So whatever else their flaws, Apple devices tend to have smoothly-animated UIs.
iainmerrick 10y ago
Oops, you're right! I think I had in mind something like "guaranteed throughput" but "consistent low latency" is definitely a better way to put it.

cmrdporcupine 10y ago

There are cycle collecting reference counting algorithms, that due a limited trace within a subset of the object graph to detect and remove cycles. I am still not clear on why Apple didn't go that direction. Reference counting will still potentially pause though, when freeing large graphs of objects.

dilap 10y ago
Yeah, but the pause is completely deterministically in control of your program. Doing cycle collection basically ends up as hard as full GC right? Annotating with weak is not a big deal.
- kartickv 10y ago
  > The pause is completely deterministically in control of your program. In theory. In practice, the programmer may not be able to reproduce the pause to diagnose and fix it, or it may not bubble up to the top of the priority list. Whereas with a GC, this problem may not occur at all in the first place. The question is whether such cases (large object graph or linked list) occur often enough in practice to be worth bothering about.
- cmrdporcupine 10y ago
  > Doing cycle collection basically ends up as hard as full GC right? Not really. Yes you do need to have the ability to trace the object graph. But the actual algorithm isn't that bad. I implemented this in C++ (for "fun" for a pet language VM i wrote) 15 years ago: http://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon01Concurrent.pdf http://researcher.watson.ibm.com/researcher/files/us-bacon/B...
  - bjourne 10y ago
    That's interesting! I also implemented that algorithm for cycle collection (https://github.com/bjourne/c-examples/blob/master/libraries/collectors/ref-counting-cycles.c https://github.com/bjourne/c-examples/blob/master/libraries/...) and I found that like the GP states that it wasn't worth it. The problem was that there so many objects that were potentially part of garbage cycles that it required scanning a too large part of the heap. Cycle detection took about 70% as long a full mark and sweep collection so I didn't think it was worth it considering how complicated the algorithm was. Is your implementation open source? If so, I'd love to see it and compare results.

imagist 10y ago

In practical terms, are there even many cases where cycles are desirable? The only case I can think of is threads (two threads communicating with each other). Most cycles I have seen even in GC'd languages were bad designs.

mac01021 10y ago
https://en.m.wikipedia.org/wiki/Dancing_Links https://en.m.wikipedia.org/wiki/Dancing_Links is one.

kartickv 10y ago

This is an insightful comment. Thanks. I wonder how things would change if a second core was sitting idle anyway, like in a mobile app that does everything on the main thread. Would it then make sense to utilise the second core for greater performance? Imagine memory isn't a problem — some phones have plenty of memory, like 6GB on a OnePlus. Unrelated to all the above, and related to your point about uncollected cycles not being a problem with refcounting, it does impose an overhead, like remember to use weak pointers to delegates in Objective-C. It's not as seamless to the programmer as GC. You can argue that it is (not) worth it, but there's no question it's more work for the programmer.

iainmerrick 10y ago
Apple's phones tend to have less memory, and fewer (but faster) cores. Along with Objective-C's reference counting, I think those are very smart choices for typical mobile app workloads. In principle having lots of cores available is great, but in practice it's hard to utilise them effectively without also using tons of memory and/or battery.

titzer 10y ago

Reference counting does not scale to multi-threaded programs well. Keeping reference counts up to date across multiple threads is maddeningly and frightenly hard to do efficiently. By the time you correctly solve the concurrent update problem for essentially every access the program does, you have a very complicated memory management system that incurs overhead on every single operation. Compare that with a GC that imposes overhead (usually) only on writes to objects, not "writes" to the stack or local variables going out of scope. Reference counting also incurs overhead for reading from objects. Empirical studies have shown that reads outnumber writes 10x to 1 usually. Why would you consider it to be just a _bit_ slower? And of course reference counting pauses. Killing one object (its count dropping to zero) may cause a chain reaction of objects whose reference counts to drop to zero and need to be cleaned up. The difference is that you now suffer work proportional to the _dead_ data of the program. In comparison, a tracing GC does work proportional to the _live_ objects.

ngrilly 10y ago
Great explanation! Thanks!
staticassertion 10y ago
> Reference counting does not scale to multi-threaded programs well. Keeping reference counts up to date across multiple threads is maddeningly and frightenly hard to do efficiently. Is this not just a matter of using an atomic reference count?
- iainmerrick 10y ago
  Yes, but atomics are pretty slow.
  - staticassertion 10y ago
    I guess, but that doesn't seem that bad. > maddeningly and frightenly hard to do efficiently. It definitely doesn't seem maddening or frightening. I'm not saying a GC isn't stricly better (because I'm unsure either way) but arc doesn't seem like some awful thing.