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

Re: Reference count, don't garbage collect

#211

Post by tsimionescu » Sat, Jul 30, 2022, 6:17 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…

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.

Re: Reference count, don't garbage collect

#212

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

musicale wrote: post #125

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…

Maybe Apple just hires mediocre developers (I certainly have lots of complaints about their software and UI issues, but I would probably suspect management/priorities/schedules rather than the technical staff) but they implemented GC and Automatic Reference Counting for ObjC and found that the latter resulted in better and more consistent responsiveness, which is probably what most users care about in apps. (Apps sti…

And RC might be the correct choice for their devices (due to them not having much RAM, and latency being more important than throughput). But that is not true everywhere, I would even say that a good tracing GC is a better default.

Re: Reference count, don't garbage collect

#213

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

chrisseaton wrote: post #116

lumost wrote: post #113

Earlier quoted context omitted.

It’s gotten better over the years. Java originally did not have generics, then there was the factory/uml everything crowd. Recently modern Java has been evolving towards ergonomics with streams/loom/guice/Lombok etc. However we still don’t have something like auto/let from cpp/rust.

> However we still don’t have something like auto/let from cpp/rust. But things like auto are more verbose semantics, not less! And isn’t var in Java like auto in C++?

There is type inference for local variables indeed with var in java for a few versions now (from the top of my head it is available since 14?)

Re: Reference count, don't garbage collect

#214

Post by tsimionescu » Sat, Jul 30, 2022, 6:22 AM UTC

cakoose wrote: post #140

refulgentis wrote: post #134

Earlier quoted context omitted.

I'm not sure whats being asserted here, could you explain more? This sounds like you're describing a non-stopping GC, and its well understood reference counting is garbage collection. I'm not sure how the rest applies, you're correct, it is possible to write software with just malloc and free.

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 think this is actually common in the literature, it has nothing to do with Wikipedia. Consider that Python is commonly described as a GC language, though it has always mostly relied on automatic reference counting to free objects (it does have a tracing GC as well to handle cycles, but I'm not sure if it always did).

Re: Reference count, don't garbage collect

#215

Post by tsimionescu » Sat, Jul 30, 2022, 6:25 AM UTC

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.

They do it because they serve the same purpose, though with different trade-offs.

Note that this mostly reflects automatic reference counting, like you have in Python or Swift, not so much manual reference counting like std::shared_ptr or Rc.

Re: Reference count, don't garbage collect

#216

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

deterministic wrote: post #133

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…

Not my experience at all. I am maintaining a very high performance JIT compiler for a Haskell like programming language used in production at large enterprises around the world. So I am used to very carefully analyse performance. And reference counting is never the bottleneck. You might be right in theory but not in practice.

Well, it won’t be the bottleneck itself, but it has an overhead on basically every operation, which likely won’t show up during profiling.

Also, I fail to see the advantage of RC in case of a presumably mostly immutable language - a tracing GC is even faster there due to no changes to the object graph after allocation, making a generational approach scale very well and be almost completely done in parallel.

Re: Reference count, don't garbage collect

#217

Post by kccqzy » Sat, Jul 30, 2022, 6:28 AM UTC

tsimionescu wrote: post #211

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…

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 world. It's a bit more difficult to make a GC implementation so.

Re: Reference count, don't garbage collect

#218

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

_gabe_ wrote: post #200

kgeist wrote: post #190

Earlier quoted context omitted.

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

> 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)?

Re: Reference count, don't garbage collect

#219

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

jefftk wrote: post #136

Waterluvian wrote: post #131

Earlier quoted context omitted.

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?

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.

Re: Reference count, don't garbage collect

#220

Post by tsimionescu » Sat, Jul 30, 2022, 6:37 AM UTC

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…

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

All tracing GC algorithms scan only live memory, and they typically do so in an array-like scan (writing some bits in the object header when a pointer to that object is discovered), not in linked-list order.