Reference count, don't garbage collect • Hacker News Board

Re: Reference count, don't garbage collect

#201

Post by zozbot234 » Sat, Jul 30, 2022, 5:35 AM UTC

shwestrick wrote: post #12

This debate has gone round and round for decades. There are no hard lines; this is about performance tradeoffs, and always will be. Perhaps the biggest misconception about reference counting is that people believe it avoids GC pauses. That's not true. Essentially, whereas tracing GC has pauses while tracing live data, reference counting has pauses while tracing garbage. Reference counting is really just another kind…

> One of the biggest issues with reference counting, from a performance perspective, is that it turns reads into writes: if you read a heap-object out of a data structure, you have to increment the object's reference count.

You have to do this if you want deterministic deallocation, because your holding a read-only reference to that object might be exactly what keeps it around for longer. So you need to track that.

(Deterministic deallocation also means having to recursively free unreachable objects. That's often described as an arbitrary "pause" behavior in RC systems, but it's actually inherent in the requirement for deterministic behavior. If you don't care about determinism for some class of objects, you can amortize that pause by sending them to a separate cleanup thread.)

Re: Reference count, don't garbage collect

#202

Post by Matthias247 » Sat, Jul 30, 2022, 5:39 AM UTC

osigurdson wrote: post #191

shwestrick wrote: post #12

This debate has gone round and round for decades. There are no hard lines; this is about performance tradeoffs, and always will be. Perhaps the biggest misconception about reference counting is that people believe it avoids GC pauses. That's not true. Essentially, whereas tracing GC has pauses while tracing live data, reference counting has pauses while tracing garbage. Reference counting is really just another kind…

One thing that is particularly strange in C#, is objects can respond to events / delegates after they have gone out of scope. It can be quite a while before the object is actually collected - especially if it ends up on the large object (85K+) heap. This seems like an incredibly leaky abstraction to me. The whole "using" concept is a bit of an abomination as well = though getting better. The issue with GC is it is a…

I don't get that part. If it can receive an event/delegate, it means the object needs to be referenced by another object which invokes the event. If that is the case - how would be eligible for GC at all?

Re: Reference count, don't garbage collect

#203

Post by ayende » Sat, Jul 30, 2022, 5:43 AM UTC

wesnerm2 wrote: post #167

rdw wrote: post #152

Earlier quoted context omitted.

You're right, and it's got more layers than that. C# does have value types, which are not boxed, and using them judiciously can avoid garbage. However, they are a more recent addition to the language (which started as a lame Java clone), and so the standard library tends to not know about them. Really trivial operations will allocate hundreds of bytes of garbage for no good reason. Example: iterating over a Dictionar…

C# had value types and pointers from the very beginning. These are not a recent addition. The standard library does know about them. However, not until C# 2.0, which introduced generics, were collections able to avoid boxing value types. There are some cases where allocations are made when they could have been avoided. Iterating over a dictionary creates a single IEnumerator object. Async methods, tuples, delegates,…

And to put that in context, 2.0 was around 2003, iirc

Re: Reference count, don't garbage collect

#204

Post by btilly » Sat, Jul 30, 2022, 5:50 AM UTC

Matthias247 wrote: post #202

osigurdson wrote: post #191

Earlier quoted context omitted.

One thing that is particularly strange in C#, is objects can respond to events / delegates after they have gone out of scope. It can be quite a while before the object is actually collected - especially if it ends up on the large object (85K+) heap. This seems like an incredibly leaky abstraction to me. The whole "using" concept is a bit of an abomination as well = though getting better. The issue with GC is it is a…

I don't get that part. If it can receive an event/delegate, it means the object needs to be referenced by another object which invokes the event. If that is the case - how would be eligible for GC at all?

Consider an object referring to a network connection, say to a database. The object may be eligible for garbage collection but still have to respond to events from the network.

When it finally gets destroyed, its Destructor method would be called. At which point the thing at the other end of the network is told that it was talking to a zombie.

Note that network connections can be expensive for the other end, so this is a horrible design. We put a lot of work in to reliably get rid of connections when not needed. But you still need the fallback of being able to correctly handle programmer oversights.

Re: Reference count, don't garbage collect

#205

Post by KerrAvon » Sat, Jul 30, 2022, 5:53 AM UTC

yyyk wrote: post #73

Reference counting is garbage collection, just a different strategy - and all these strategies tend to blur to the same methods eventually, eventually offering a latency-optimized GC or a throughput-optimized GC. Swift is inferior here because it uses reference counting GC without much work towards mitigating its drawbacks like cycles (judging by some recent posts, some of its fans apparently aren't even aware RC has…

Your first paragraph is only true if malloc/free counts as GC. I have seen people try to claim that free() is just manual GC. You can say that if you want, but it renders the terminology meaningless.

Any true GC strategy (== one that collects cycles) will fundamentally touch and allocate more memory than malloc/free, where reference counting is pretty close to malloc/free performance; it doesn’t need to touch any memory not involved. At OS scale, that’s a huge performance advantage. You can scope down the memory involved in GC using advanced, modern GC techniques, but you’re still going to be behind malloc/free in overall efficiency — cache efficiency, memory maintenance overhead, and additional memory required for bookkeeping. And reference counting will be pretty darn close to malloc/free.

Re: Reference count, don't garbage collect

#206

Post by Thiez » Sat, Jul 30, 2022, 5:56 AM UTC

Matthias247 wrote: post #202

osigurdson wrote: post #191

Earlier quoted context omitted.

One thing that is particularly strange in C#, is objects can respond to events / delegates after they have gone out of scope. It can be quite a while before the object is actually collected - especially if it ends up on the large object (85K+) heap. This seems like an incredibly leaky abstraction to me. The whole "using" concept is a bit of an abomination as well = though getting better. The issue with GC is it is a…

I don't get that part. If it can receive an event/delegate, it means the object needs to be referenced by another object which invokes the event. If that is the case - how would be eligible for GC at all?

One far-fetched yet simple example would be an observer/observable pair, where the observable mutates observed properties inside its finalizer. The observable will usually contain a reference to the observer, but not the other way round. So when the observable is dead but the observer (optionally) still alive, when the observables finalizer runs it will send a message to the observer.

When our observer is also dead (so the pair is out of scope) it will be a dead object receiving events.

Re: Reference count, don't garbage collect

#207

Post by al_mandi » Sat, Jul 30, 2022, 6:02 AM UTC

nemothekid wrote: post #90

It's my theory that Java, unintentionally, did a lot of damage to P&L research. I write a lot of Rust, and while the borrow checker is great, I've come to really admire the work that was put in the Go GC even if it's not as fast Java. There is a whole generation of programmers that have come to equate GC with Java's 10 second pauses or generics/typed variables with Java's implementation of them. Even the return to ty…

Java (the JVM) doesn't really have 10 second pauses anymore. G1GC and ZGC and Shenandoah have been a thing for a while now.

Re: Reference count, don't garbage collect

#208

Post by kaba0 » Sat, Jul 30, 2022, 6:02 AM UTC

eru wrote: post #146

kaba0 wrote: post #78

Earlier quoted context omitted.

But reference counting is a GC-algorithm -- that does exactly the same thing: tries to infer the object graph at runtime. I really don't think it is a language problem, for several algorithms that one may want to write, GC is a necessity as object lifetime is not decidable at compile time. And it's not just some special parallel algorithm, I believe most business problems fall into this category - that's why we have…

I wouldn't call reference counting a hack. The paper mention elsewhere in the comments, https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-... "A Unifying Theory of Garbage Collection" put this in context. For example, a generational garbage collection essentially employs a hybrid approach between tracing and reference counting. Similarly, depending on your system's trade-offs, reference counting might be be…

I meant hack as in languages meant for primarily for manual memory can still have RC (rust, C++), but that will only be a conservative GC algorithm due to no cycle detection. My use of hack here was only to denote that library-only RC , while possible, may not be the best approach and is used as an escape hatch in rare cases.

Re: Reference count, don't garbage collect

#209

Post by al_mandi » Sat, Jul 30, 2022, 6:06 AM UTC

nemothekid wrote: post #142

forrestthewoods wrote: post #104

Earlier quoted context omitted.

> There is a whole generation of programmers that have come to equate GC with Java's 10 second pauses Anyone who has ever shipped a C# Unity game know the pain that is the garbage collector. It’s effectively impossible to avoid frame hitches with the GC. I’ve spent a LOT of time going way out of my way to avoid any and all garbage collects. Which somewhat defeats the purpose of using a GC-based language. I definitely…

I don't know much about the C# garbage collector; and it's likely that garbage collectors are a bad fit for programs that have hard deadlines. That said, it could also be a function of the same "problem" Java has in its design - Java by default boxes everything and so every memory allocation increases garbage collection pressure. Go, by using escape analysis and favoring stack allocations, doesn't have this problem a…

The JVM also does escape analysis. Java value types are in the works as well.

Re: Reference count, don't garbage collect

#210

Post by elcritch » Sat, Jul 30, 2022, 6:09 AM UTC

viraptor wrote: post #141

deterministic wrote: post #132

Earlier quoted context omitted.

I am the maintainer of a very high-performance JIT compiler for a Haskell like rules programming language used by large enterprises around the world. It uses reference counting + a global optimisation step to reduce the reference count updates to an absolute minimum. The result is compiled code that runs faster than C++ code carefully hand optimised by C++ experts over a 10 year period. There are zero GC pauses. Unle…

How do you collect cycles without a pause?

By requiring non-cyclic data structures or provide "weak" references. It's actually pretty easy to write most code without cycles. I program a lot in Nim and generally compile lots of programs with ARC and no cycle collector without issue.