Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Reference count, don't garbage collect

kevinlawler.com

Post reply on HN
Print view View original

51–60 of 415 posts

Re: Reference count, don't garbage collect

#51

Post by mamcx »

kaba0 wrote: post #48
mamcx wrote: post #27

Earlier quoted context omitted.

> hits if you release any large data structures. Well, that depends in how is the RC done. This is key to understand because if you can control it, the RC become cheaper. You can see this way on http://sblom.github.io/openj-core/iojNoun.htm ie: If instead of `[Rc(1), Rc(2)]` you do `Rc([1, 2])` that work great.

How is that not the exact same for tracing GC?

Well, you don't need the GC. That is the point of this: Rc could be piece-meal. That is something that could be exploited very well making a interpreter, for example (that is what Array langs do under the hood)

Re: Reference count, don't garbage collect

#52

Post by hinkley »

kaba0 wrote: post #44
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 great example would be a C++ program that runs fast, and then just spends 10s of seconds doing “nothing” while it deallocates shared pointers’ huge object graphs at the end. They really are two sides of the same coin, with tracing GCs being actually correct (you need cycle detection for a correct RC implementation), and having much better throughput. It’s not an accident that runtimes with thousands dev hours are…

I don't know what the current state of the art is, but at one point the answer to GC in a realtime environment was to amortize free() across malloc(). Each allocation would clear up to 10 elements from queue of free-able memory locations. That gives a reasonably tight upper bound on worst case alloc time, and most workflows converge on a garbage-free heap. Big malloc after small free might still blow your deadlines, but big allocations after bootstrapping are generally frowned upon in realtime applications, so that's as much a social problem as a technical one.

Re: Reference count, don't garbage collect

#53

Post by hinkley »

code_runner wrote: post #21
jerf wrote: post #5

From what I can see, the myth that needs to be debunked isn't that garbage collection is super fast and easy with no consequences, it's the myth that garbage collection always automatically means your program is going to be spending 80% of its time doing it and freezing for a second every five seconds the instant you use a language with garbage collection. I see far more "I'm writing a web server that's going to hand…

The biggest GC issues I’ve personally seen manifest were arrays of historical data that grew to tens of millions of entries and due to array storage in .net, the array was placed in the large object heap. Swapping to a linked list actually fixed the issue and the team lived to fight another day. Like a lot of premature optimization, it isn’t a problem until it is… but solutions aren’t unattainable.

I still mostly remember the day a coworker convinced me that object pooling was dead because it tears the mature generation a new one over and over.

It's nice when the runtime solves a problem you've had to solve yourself, but it also takes a bit of your fun away, even if your coworkers are relieved not to have to deal with 'clever' code anymore.

Re: Reference count, don't garbage collect

#54

Post by hinkley »

PaulHoule wrote: post #13
nickbauman wrote: post #10

Earlier quoted context omitted.

Yes; I have a friend who is part of a small team that wrote a very successful stock market trading gateway in Java. Turns out the JVM's GC can be tuned in very specific ways based on your needs. And there are ways to avoid having to do JVM GC in critical areas of the code as well.

Generally Java has made a huge investment in the garbage collector over a long period of time to address the problems that people have in some use cases. JDK 17 is much better than JDK 8. If you were writing a GC from scratch you are not going to do as well.

To be fair, they definitely got into a rut in the JDK 6-7 timeframe. I maintain it's no accident that memcache came into its own during this period. That was a major pain point, and going out-of-process shouldn't have been necessary.

Re: Reference count, don't garbage collect

#55

Post by goodpoint »

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…

It's not always a tradeoff:

Nim switched from GC to RC and it even increased performance.

Re: Reference count, don't garbage collect

#56

Post by hinkley »

pclmulqdq wrote: post #7
habibur wrote: post #3

It's interesting how we have come full circle from "Reference counting is the worst of two worlds [manual and GC] and will always be slower" to now "Well, we all know it's actually faster." in like 10 years.

Its actually usually slower than both manual memory management and GC. It's only coming back now because people are finally learning how to make memory allocations large and rare. This blog post is an answer to: "Tell me you haven't learned about cache coherence without telling me you haven't learned about cache coherence."

Has anyone done a good paper on how memory bank affinity for processors affects these costs?

Re: Reference count, don't garbage collect

#57

Post by waterhouse »

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…

> Essentially, whereas tracing GC has pauses while tracing live data, reference counting has pauses while tracing garbage.

This is pretty trivial to avoid. When your thread finds itself freeing a big chain of garbage objects, you can have it stop at any arbitrary point and resume normal work, and find some way to schedule the work of freeing the rest of the chain (e.g. on another thread). It's much more complex and expensive to do this for tracing live data, because then you need to manage the scenario where the user program is modifying the graph of live objects while the GC is tracing it, using a write or read barrier; whereas for garbage, by definition you know the user can't touch the data, so a simple list of "objects to be freed" suffices.

"Reads become writes" (indeed, they become atomic read-modify-writes when multiple threads might be refcounting simultaneously) is a problem, though.

Re: Reference count, don't garbage collect

#58

Post by bitwize »

kaba0 wrote: post #49
bitwize wrote: post #24

Boy, I can't wait for theangeryemacsshibe (posts here as hayley-patton) to tear into this one. But yeah, the correct way to handle resources (not just memory!) is with value semantics and RAII. Because then you know the object will be cleaned up as soon as it goes out of scope with zero additional effort on your part. In places where this is not appropriate, a simple reference counting scheme may be used, but the ide…

Why not just write embedded programs with fixed size memory allocation then if we are that okay with restricting the programs we write?

Because maybe we're not okay with restricting the programs we write that much.

Re: Reference count, don't garbage collect

#59

Post by arcticbull »

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…

RC may turn reads into writes, but of course, GC ends up having to go through literally every piece of memory ever from bottom to top once in a while.

RC limits itself to modifying only relevant objects, whereas GC reads all objects in a super cache-unfriendly way. Yes, an atomic read-modify-write is worse than a read, but it's not worse than a linked-list traversal of all of memory all the time.

And of course, not all kinds of object lend themselves to garbage collection - for instance, file descriptors, since you can't guarantee when or if they'll ever close. So you have to build your own reference counting system on top of your garbage collected system to handle these edge cases.

There's trade-offs, yes, but the trade-off is simply that garbage collected languages refuse to provide the compiler and the runtime all the information they need to know in order to do their jobs - and a massive 30 year long effort kicked off to build a Rube Goldberg machine for closing that knowledge gap.

Re: Reference count, don't garbage collect

#60

Post by okennedy »

flohofwoe wrote: post #22

Such a claim really needs hard data to back it up. Reference counting can be very expensive, especially if the refcount update is an atomic operation. It's hard to capture in profiling tools because the performance overhead is smeared all over the code base instead of centralized in a few hot spots, so most of the time you don't actually know how much performance you're losing because of refcounting overhead. The mos…

This. Exactly this.

Garbage collection has a huge, and generally entirely unappreciated win when it comes to threaded code. As with most things, there are tradeoffs, but every reference counting implementation that I've used has turned any concurrent access to shared memory into a huge bottleneck.

Post reply on HN