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

241–250 of 415 posts

Re: Reference count, don't garbage collect

#241

Post by pjmlp »

rowanG077 wrote: post #157
cakoose wrote: post #140

Earlier quoted context omitted.

Re: "it's well understood reference counting is garbage collection". I think this might just be a terminology thing. There appear to be two ways the terms are categorized: 1. "reference counting" and "garbage collection" are two types of automatic memory management/reclamation. 2. "reference counting" and "tracing garbage collection" are two types of garbage collection. I think mbrodersen is using #1. (Back in the 90…

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

Re: Reference count, don't garbage collect

#242

Post by int_19h »

kgeist wrote: post #192
OskarS wrote: post #43

Earlier quoted context omitted.

> Almost everyone that actually uses reference counting uses more like 2-4 bits. Here is an incomplete list of languages which use 8 bytes for their reference count on 64-bit computers: 1. Rust, in Rc and Arc 2. C++, in std::shared_ptr 3. Objective-C, in NSObject's retainCount 4. Swift, because of Objective-C 5. Python, where reference count is Py_ssize_t These were literally the first languages i thought of, they al…

>C++, in std::shared_ptr In C++, every shared_ptr also allocates a separate "control block" in the heap, so performance is even worse than that.

std::shared_ptr is not meant to be used as the default memory management technique, hence why it's not that important.

But it does mean that C++ is not a good example here. I would argue that Rust isn't, either, since ARC is also an occasional opt-in there rather than the default.

Re: Reference count, don't garbage collect

#243

Post by chrisseaton »

thirdmunky wrote: post #138
mandevil wrote: post #112

Earlier quoted context omitted.

Not OP, but someone who has gotten paid to write Java for several years. I would say that isn't that Java's semantics are that verbose, it's that the way Java is traditionally written, with every line actually 3 lines on your screen of public function makeItalicTextBox(String actualTextIWantToBeItalic) { ItalicTextBox itb = italicTextBoxFactoryGenerator.GenerateFactory().buildItalicTextBox(actualTextIWantToBeItalic);…

Java idioms are one contributing factor. There's some inherent wordiness too - for example, Hello World in Java is wordier than in most other programming languages.

That's syntax not semantics though.

Re: Reference count, don't garbage collect

#244

Post by viktorcode »

nickbauman wrote: post #10
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…

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.

As I heard those guys write allocation-free Java code in critical paths. Nothing allocated, nothing to collect.

Re: Reference count, don't garbage collect

#245

Post by viktorcode »

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…

> 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.

Not 80%, but still annoying enough to dump it: https://discord.com/blog/why-discord-is-switching-from-go-to...

Re: Reference count, don't garbage collect

#246

Post by ribit »

ncmncm wrote: post #226
im3w1l wrote: post #77

Earlier quoted context omitted.

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.

This is the key. Using std::shared_ptr in a performance-sensitive context (e.g. after startup completes) is code smell. Using pointers as important elements of a data structure, such that cycles are possible at all, is itself code smell. A general graph is usually better kept as elements in a vector, deque, or even hash table, compactly, with indices instead of pointers, and favoring keeping elements used near one an…

> But the original article is completely, laughably wrong about one thing: an atomic increment or decrement is a remarkably slow operation on modern hardware, second only to pointer chasing.

Very true. No matter how one looks at it, GC imposes a non-trivial overhead. If I remember correctly, wasn’t there a study that demonstrated an average Swift application spending 40% of its time on RC?

But at the same time hardware can be improved. Apple CPUs are an obvious example. Uncontended atomics are extremely cheap and the memory prefetcher can detect and prefetch pointer chases.

Re: Reference count, don't garbage collect

#247

Post by Starlevel001 »

kccqzy wrote: post #217
tsimionescu wrote: post #211

Earlier quoted context omitted.

free() calls that have to run for a data-dependent amount of time are more or less equivalent to GC pauses (assuming a concurrent GC that doesn't need to stop the world, like Java's). The most typical example is free()-ing a a linked list, which takes O(n) free() calls to free with a simple RC mechanism.

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.

Re: Reference count, don't garbage collect

#248

Post by brabel »

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…

You've gone from claiming reference-counting is faster than tracing GC to claiming it's even faster than hand optimized C++, which is quite honestly unbelievable - whatever the reference counting algorithm is doing can be emulated by the hand-optimised C++ code so that's just literally impossible. But anyway, it's a completely fruitless discussion here unless you provide data that we can look at and scrutinize. OP hasn't provided any. You haven't provided any (and I do believe you may think you're right, but I've been in the position of being very confident of something just to be proven completely wrong by giving all my data to others to scrutinize... it's disheartening but necessary to get to the bottom of what's real). It's like the V language saying it can do memory management magically and it's much faster than Rust or whatever when they don't even have a working system yet.

Re: Reference count, don't garbage collect

#249

Post by viktorcode »

kgeist wrote: post #190
cmroanirgo wrote: post #123

Earlier quoted context omitted.

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…

>One reason you'd choose ref counting is because it's deterministic behavior Not sure if it's entirely deterministic. A variable going out of a scope can trigger deallocation of a large object graph and it's not always clear by just looking at a code what will happen (especially if objects have destructors with side effects, your object graph is highly mutable, and your code is on a hot path). A common trick is to de…

Deterministic means that running the same part of the program will take the same amount of time. Deallocating the same memory object graph is pretty much deterministic.

GC can throw a spanner in that by deciding that now is the time to do its thing.

Re: Reference count, don't garbage collect

#250

Post by Animats »

viktorcode wrote: post #236
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…

Putting both under the same term is meaningless. Reference counting and Garbage Collection have very clear difference: when the referenced objects are destroyed (not deallocated). In RC it happens when the count reaches zero. In GC it happens some time later. That difference is crucial for having or not having deterministic performance in your program.

> In GC it happens some time later.

Yes. In languages with destructors/finalizers called from the garbage collector, things can get very complicated. C# and Java have this problem.

Go avoids it by having scope-based "defer" rather than destructors.

Post reply on HN