4 ms·
This is quite cool. I love seeing new research into reference counting systems since they seem to have fallen out of favor vs mark/sweep and such (ARC notwithst
by kstenerud 7y ago
This is quite cool. I love seeing new research into reference counting systems since they seem to have fallen out of favor vs mark/sweep and such (ARC notwithstanding).
- pjmlp 7y agoThey were never in favor, because any reference counting implementation that matches tracing GC in performance, specially on multi-core machines, ends up being a tracing GC in disguise.
- DagAgren 7y agoOne of the biggest OSes today is running nearly entirely on reference counting, so I think it's safe to say they are actually in favour.
- pjmlp 7y agoIf you mean iOS, it is more a side effect of the project failure to add GC to Objective-C than anything else. Also reference counting only applies to a tiny subset of Objective-C data structures, classes derived from NSObject using Cocoa retain/release patterns. If you add Swift to the soup, there is still quite some work to do regarding performance, https://github.com/ixy-languages/ixy.swift/blob/master/performance/README.md https://github.com/ixy-languages/ixy.swift/blob/master/perfo... The other, even bigger OS, is running on tracing GCs. And Windows is running on a mix of reference counting and tracing GC.
- tomp 7y agoIsn’t one of the benefits of RC better (lower and more predictable) latency than with GC? Basically, you can presict when (and how much) garbage will be collected, and if it turns out that’s too much, you can fix your code... good luck doingthat with GC. The downside is, of course, that it requires much more care (to avoid cycles)
- pjmlp 7y agoOn single core without threading. If you add multi-threading and multi-core, there is lock contention for every single memory access to update the related counter. Additionally, if there is a big data structure in use, reaching zero will trigger a cascade deletion events reaching stop-the-world like effect. Which, depending on how the deletion was implemented, might trigger a stack overflow in very deep structures. Herb Sutter has a very interesting talk about the bad issues of reference counting and how to work around them. CppCon 2016: Herb Sutter “Leak-Freedom in C++... By Default.” https://www.youtube.com/watch?v=JfmTagWcqoE https://www.youtube.com/watch?v=JfmTagWcqoE There are multiple ways to optimize reference counting, like deferred counting, cycle collectors and a couple of others, which when you are done with all them, ends up being quite similar to having a tracing GC anyway.
- zozbot234 7y ago> If you add multi-threading and multi-core, there is lock contention for every single memory access to update the related counter. You only have to update the counter when creating (or destroying) new "owning" references that might outlive any other reference to the object. This is a rare operation, and doing it potentially from multiple threads in a way that requires atomic update is even rarer. > Additionally, if there is a big data structure in use, reaching zero will trigger a cascade deletion events reaching stop-the-world like effect. This is a side effect of deterministic disposal, of course. And it only happens when freeing up large object subgraphs, not just any and all "large data structures". Yes, C++ implements reference counting in a non-ideal way. Swift is also quite bad. But one can do better.
- MrBuddyCasino 7y agoOh wow, thanks for that link. I knew ARC was slow, I didn’t know it was THAT slow. Swift code reviewed by three programmers, no dynamic dispatch, no low-hanging fruit to optimize, and still much slower than even Golang.
- andreareina 7y agoAre you talking about linux? I thought the kernel used refcounting?
- pjmlp 7y agoAndroid
- bitwize 7y agoApple didn't fail to add GC. They successfully added it and then took it out again. Why? Because ARC gets you 99% of the way there while consuming less CPU and being strictly deterministic -- and the biggest Objective-C platform in the world has to run without a hitch or glitch on tiny, battery-powered devices. Adding GC to the Android platform was a stupid move. The Android UI is still janky compared to iOS, and GC is not the only reason why, but it's a significant reason. Android devices also eat battery like it's going out of style compared to iPhones and iPads. Again, GC is not the only reason for this but it factors in.
- wbl 7y agoPausless GCs are real and exist.
- pjmlp 7y agoOh they did fail indeed, Objective-C libraries were crashing left and right due to underlying C semantics and mixing frameworks compiled with and without GC enabled. So they did the only possible exit, automate the manual retain / release Cocoa patterns on the compiler, and sell a marketing story about ARC and how GC is bad. Pity that Borland and Microsoft haven't done the same about their compiler support for COM RC, done years before. Android UI is janky due to bad coding practices, specially doing too much on UI thread. Our phones are super computers compared with Lisp Machines. If you want to start counting devices sold, it is pretty clear that tracing GC has won, specially when we had any kind of device with a web browser on it.
- Someone 7y agoI don’t feel like investigating that, nor do I have the hardware, but I think spending ¾ of time in reference count updates is really high. https://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf https://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf has 42% on average, and halves that using their modification.
- zozbot234 7y agoReference counting may have flexibility advantages compared to tracing GC. Obligate reference counting (ala ObjC/Swift) vs. obligate tracing GC is not the only relevant comparison.
- pjmlp 7y agoThe only flexibility is that is easier to implement, whence why it is usually the first GC algorithm one learns, and among the initial chapters of GC algorithms overview books.
- ckok 7y agoThe algorithm used here is a combination of both rc and tracing, it's not simple.
- pjmlp 7y agoThus making the point that in the end it always ends up being some form of tracing GC when performance matters.
- ckok 7y agoRight. To make RC work like a tracing GC (performant and without failing on circular references); it's going to be a combination. That said, there are a lot of interesting ideas in this that might be quite worth it. Like the article referenced, doesn't do a full heap scan, but makes a note of what is worth looking at.
- kstenerud 7y agoHas this been proven? If not, there's room for more research.
- pjmlp 7y agoMultiple times, you just need to search for a couple of CS papers, including one I link below.
- jashmatthews 7y agoYup. Discussed here before! https://news.ycombinator.com/item?id=14823054 https://news.ycombinator.com/item?id=14823054