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

321–330 of 415 posts

Re: Reference count, don't garbage collect

#321

Post by catlifeonmars »

Starlevel001 wrote: post #247
kccqzy wrote: post #217

Earlier quoted context omitted.

If you are assuming GC does not need to stop the world, you can also assume that the freeing of memory (including the O(n) calls to free()) will not be done in a critical path; all memory could be handed off to a separate dedicated thread that actually calls free(). Or in a RPC or HTTP server all memory can be freed after the request has been served. It's very easy to make a reference counting scheme not stop the wor…

> all memory could be handed off to a separate dedicated thread that actually calls free(). You could go a bit further and have multiple concurrent threads mark the references, then sweep them up in a separate thread, too. Some sort of concurrent sweep and mark reference count system.

With concurrency you need atomics or locks to synchronize reference counts between cores, unless you can somehow guarantee that ref counts only decrement and can never increment.

Re: Reference count, don't garbage collect

#322

Post by garethrowlands »

arcticbull wrote: post #59
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 a…

Pointer chasing is expensive because fetching a random location defeats locality and therefore caches the the CPU's stream detection.

But a compacting GC copies the data it's scanned into a contiguous stream, dramatically improving locality, cache utility and stream detection. And this affects not only subsequent GCs but also the application itself, which may traverse its object graph far more often than the GC does.

Re: Reference count, don't garbage collect

#323

Post by rowanG077 »

pjmlp wrote: post #241
rowanG077 wrote: post #157

Earlier quoted context omitted.

I never understand why people refer to reference counting as garbage collection. It waters down the term so much it becomes essentially useless. Because under that assumptions basically every language has garbage collection in some shape or form.

Because we have studied the literature instead of what a random dude in tells at a coffee https://gchandbook.org/ https://www.sigplan.org/ https://ieeexplore.ieee.org/Xplore/home.jsp

Nice appeal to authority instead of trying to engage in a meaningful way.

Re: Reference count, don't garbage collect

#324

Post by adgjlsfhk1 »

OskarS wrote: post #50
kaba0 wrote: post #47

Earlier quoted context omitted.

> Deallocating can take arbitrarily long, but deallocation does not stop-the-world And modern GCs only have to stop the current thread to check for which thread-local objects are alive. The alice ones are moved to another generation, making the space reusable for free . And atomic writes need synchronization which is crazy expensive, I honestly don’t get why you think it isn’t. Also, just try writing rust/c++ code th…

> The alice ones are moved to another generation, making the space reusable for free. It's pretty hilarious to me that you first say "they have to move it to another generation" and then you say "it's free!" It's like saying "I paid for my dinner, and now I get to eat it for free!" Also: what do you think `free()` does? All modern memory allocators do this trick, keeping thread-local caches. This is not an advantage…

even ignoring the fact that this isn't counting contention, 18ns is still really high overhead since it's an operation you have to do twice to read any object. a read from l1 cache is about 3 cycles (1-3 ns), so 36 ns to increment and decrement a counter is far from trivial.

Re: Reference count, don't garbage collect

#325

Post by tuetuopay »

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.

This is one of the biggest misconception about RC. You need not to increase the refcount just to read the referred data because you already have a reference whose count has been increased when handed down to you. That’s a semantic that’s very well carried off by Rust’s Arc type: the count is inc’ when the Arc is cloned, and dec’ when the cloned Arc is dropped. But you can still get a regular ref to the data since the compiler will be able to enforce locally the borrow, ownership and lifetime rules.

For example, in a web server, you might have the app’s config behind an Arc. It gets cloned for each request (thus rc inc’d), read a lot during the req, then dropped (thus rc dec’d) at the end of the handler.

Re: Reference count, don't garbage collect

#326

Post by jefftk »

kaba0 wrote: post #219
jefftk wrote: post #136

Earlier quoted context omitted.

If you squint at it right you could say C works that way: you have many processes each with their own heap and they can pass messages, but if they want larger data that's too expensive to pass around you can use shared memory.

That’s just IPC, nothing inherent to C.

Sure, you can do this in a lot of languages. I gave C mainly because it's the "native language" of Unix.

Re: Reference count, don't garbage collect

#327

Post by Tozen »

pjmlp wrote: post #265
ahartmetz wrote: post #235

Earlier quoted context omitted.

Even the best "real world" garbage collectors pause the program for order of magnitude a hundred milliseconds, no? I was recently reading some blog posts of the V8 JS engine team. There is nothing to understand or not understand there, it's hard data.

And yet GC haters keep ignoring the hard data about languages like D, Oberon family, Modula-3,Nim, .NET, and plenty others where alongside the tracing GC, there are value types, stack, static global memory, manual memory allocation primitives and unsafe code blocks to perform as much C like coding as performance junkies might feel like doing.

Good point. Way too many people act like GC means an unremovable curse, versus it can be another option, among various memory management options of a language.

Re: Reference count, don't garbage collect

#328

Post by torginus »

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…

Considering that C# has a major role in desktop development, and interacts with platform APIs and objects a lot as a result, these kind of weird behaviors coming from conflicting ideas about object lifetimes happen a lot - it's weird they chose a GC for the language.

Re: Reference count, don't garbage collect

#329

Post by _gabe_ »

kaba0 wrote: post #218
_gabe_ wrote: post #200

Earlier quoted context omitted.

> trigger deallocation of a large object graph and it's not always clear by just looking at a code what will happen If you can't understand what's happening when an object gets freed, it may be a sign that your code is too tightly coupled and/or becoming spaghetti. I've found that the more graph-like my data structures become, the more inadvertent complexity I'm adding. That's the whole reason we talk about data norm…

Come on, object graphs are completely dynamic, noone can say where will “a variable go out of scope”, unless we literally have a hello world. Do you honestly claim that you know when deallocations happen in any codebase full of conditionals depending on outside effects (user input, network, etc)?

> Do you honestly claim that you know when deallocations happen in any codebase full of conditionals depending on outside effects (user input, network, etc)?

Yes. C programs have been doing this for over 40 years now. A leak free C program has an equivalent free for every malloc, which means they know exactly when everything gets allocated and freed.

Re: Reference count, don't garbage collect

#330

Post by origin_path »

ahartmetz wrote: post #235
klodolph wrote: post #81

Earlier quoted context omitted.

> 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. Having studied GC, implemented GC, and used it extensively (either as a dev or someone in operations) I'd say that there's just a lot of people out there who don't understand it. That's why people come to the wrong conclusion that it's somehow "inelegant" or "brute-force", w…

Even the best "real world" garbage collectors pause the program for order of magnitude a hundred milliseconds, no? I was recently reading some blog posts of the V8 JS engine team. There is nothing to understand or not understand there, it's hard data.

The best real world garbage collectors are like ZGC, Shenandoah or C4 which don't pause your program at all. They are fully concurrent.

Even if you go for a GC that is designed to balance throughput and latency, like G1, you can still configure what pause times it should target and those can easily be ~10-20msec if you want, with the vast majority of pauses being far less than that (less than 3 msec).

"I was recently reading some blog posts of the V8 JS engine team. There is nothing to understand or not understand there"

Look, if your knowledge of GC comes from reading V8 blog posts then you're proving the grandparent's point pretty nicely. You leaped from an extremely basic and remote understanding of GC to "there's nothing to understand or not understand here".

Post reply on HN