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

Re: Reference count, don't garbage collect

#141

Post by viraptor » Sat, Jul 30, 2022, 2:10 AM UTC

deterministic wrote: post #132

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…

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?

Re: Reference count, don't garbage collect

#142

Post by nemothekid » Sat, Jul 30, 2022, 2:14 AM UTC

forrestthewoods wrote: post #104

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…

> 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 and has had sub-millisecond pauses for years now.

You rarely hear people complain about Go's GC despite it being much less mature than the JVMs. But due to actual language design, Go's GC does much less work. I wouldn't say “GC used to be bad but now it’s good”, but that "the design of languages like C# and Java were too dependent on using the GC for memory allocations, and there are other GC languaged out there that utilize the GC less which can lead to greater performance"

Re: Reference count, don't garbage collect

#143

Post by eru » Sat, Jul 30, 2022, 2:22 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?

There are solutions to this one. Real time garbage collectors are a thing. You just might not be able to collect the cycle in one GC run.

Or you can do what Erlang does: Erlang has neither mutation nor laziness, so you can't create cycles. The GC also lays out object in topological order in memory, so that you can detect garbage without tracing every life object.

Re: Reference count, don't garbage collect

#144

Post by eru » Sat, Jul 30, 2022, 2:26 AM UTC

im3w1l wrote: post #77

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…

If you use refcounted pointers for everything then you'd be better off with a proper gc. But at least in the programs I see, 99% of objects are not refcounted , and that is reserved for a tiny majority of objects with especially tricky lifetimes.

Nowadays good compilers can handle many of these non-tricky lifetimes statically, too.

Re: Reference count, don't garbage collect

#145

Post by jeffmurphy » Sat, Jul 30, 2022, 2:27 AM UTC

Waterluvian wrote: post #131

imtringued wrote: post #130

Not only does the author ignore the huge progress in conventional garbage collected languages like Java, he also dismisses GC as inherently flawed despite the fact that the common strategy of only having one heap per application has nothing to do with garbage collection. In Pony each actor has its own isolated heap which means the garbage collector will only interrupt a tiny portion of the program for a much shorter…

I’m out of my league so this may be dumb, but does any language or VM or whatnot have a combined system where each thread has its own heap, and you can talk by passing messages, but they also have a common heap for larger data that’s too expensive to pass around, but at the cost that you have to be much more careful with lifetimes or have to manage it manually or something?

I believe Erlang works this way.

Re: Reference count, don't garbage collect

#146

Post by eru » Sat, Jul 30, 2022, 2:30 AM UTC

kaba0 wrote: post #78

arcticbull wrote: post #67

Earlier quoted context omitted.

> When I hear rhetoric like this, all I think is, "Oh, this person really hates GC, and thinks everyone else should hate GC." Yeah, I think it's an inelegant, brute-force solution to a language problem - and that we continue to throw good money after bad improving it. We should be investing in removing the need for GC through smarter compilers and through languages that allow us to better express our intent - and our…

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 better. Eg tracing garbage collection works really great for main memory, but for filesystems we typically use reference counting to decide whether to retire an inode. (The paper explains this in more detail.)

Re: Reference count, don't garbage collect

#147

Post by pclmulqdq » Sat, Jul 30, 2022, 2:33 AM UTC

deterministic wrote: post #132

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…

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…

The global optimization step is often what people commonly refer to as "garbage collection." Putting it inside a framework to RC as few times as possible is pretty cool.

However, I doubt the efficacy of your C++ experts: most of the people I know who write C++ are actually really bad at optimizing code. They mostly use it for legacy reasons. If you get a team of experienced (and expensive) systems programmers, you will likely get a slightly better result than your GC algorithm.

Re: Reference count, don't garbage collect

#148

Post by eru » Sat, Jul 30, 2022, 2:36 AM UTC

cmroanirgo wrote: post #123

smasher164 wrote: post #108

For how strongly worded this article is, you'd think the author would provide some substance in their reasoning. Reference counting, even atomic, is quite expensive. Not only because it can invalidate the cache line, but depending on the architecture (looking at you x86), the memory model will deter reordering of instructions. On top of this, reference counting has a cascading effect, where one destructor causes anot…

One reason you'd choose ref counting is because it's deterministic behavior, whereas you lose that granularity with gc, even if you did a gc cleanup. I see great reasons for both systems being useful, but both systems also bring their own warts. Yes, ref counting affects cache and branch prediction, but gc is a whole complete subsystem running in parallel with your main code, constantly cleaning up after you. It will…

> Scripting with ref counting would be a nightmare, [...]

Why? Old version of Python used ref counting only, and Python still largely relies on reference counting (but has a GC to detect cycles).

Re: Reference count, don't garbage collect

#149

Post by tkhattra » Sat, Jul 30, 2022, 2:37 AM UTC

Waterluvian wrote: post #131

imtringued wrote: post #130

Not only does the author ignore the huge progress in conventional garbage collected languages like Java, he also dismisses GC as inherently flawed despite the fact that the common strategy of only having one heap per application has nothing to do with garbage collection. In Pony each actor has its own isolated heap which means the garbage collector will only interrupt a tiny portion of the program for a much shorter…

I’m out of my league so this may be dumb, but does any language or VM or whatnot have a combined system where each thread has its own heap, and you can talk by passing messages, but they also have a common heap for larger data that’s too expensive to pass around, but at the cost that you have to be much more careful with lifetimes or have to manage it manually or something?

In the Erlang VM, each Erlang "process" has its own garbage collected heap [1]. There's also an ETS module for more efficiently storing and sharing large amounts of data, but data stored in ETS is not automatically garbage collected [2].

[1] https://www.erlang.org/doc/apps/erts/garbagecollection [2] https://www.erlang.org/doc/man/ets.html

Re: Reference count, don't garbage collect

#150

Post by eru » Sat, Jul 30, 2022, 2:43 AM UTC

jsnell wrote: post #19

> Basically, you attach the reference to the object graph once, and then free it when you're done with it. So reference counting works by the programmer knowing the lifetime of each object allowing them to only increment / decrement the refcount once, and trusting that the raw uncounted pointers they use elsewhere are always valid? There's another word we have for this: manual memory management. It's unsafe and unerg…

Yes.

In Python reference counting precedes tracing garbage collection.

So they didn't 'go through the hassle of implementing reference counting' after they already had tracing garbage collection. Instead they went through the hassle of implementing tracing garbage collection after they already had reference counting.

(And as you say for backwards compatibility reasons, they can't get rid of reference counting.)