Hacker News Reader

Comment by shwestrick | Hacker News Reader

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 of GC. I'd highly recommend perusing this paper for more details: A Unifying Theory of Garbage Collection. https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-...

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. Modern memory architectures have much higher read bandwidth than write bandwidth, so reference counting typically has much lower throughput than tracing GC does.

View on HN

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. Unless you claim that a C++ alloc/feee call is “garbage collection”. Which is not common terminology. It also (BTW) scales linearly the more cores you throw at it.

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 90s and 2000s I feel like #1 was much more prevalent. But #2 seems to have gained popularity since then. My theory is that whoever started writing the Wikipedia content for this stuff picked #2.)

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.

C doesn't have garbage collection.

Furthermore, pretty much every language has I/O, but that doesn't make the term useless.

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.

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.

When one is open to learning, the best path to enlightenment is to use the same books as the Wizards on the tower of knowledge.

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

I would argue that what matters is the observable behavior. In Python, regardless of how the actual cleanup is distributed between ARC and GC, the behavior that programmer sees is that all unused memory gets cleaned up eventually. So, it makes sense to group it with languages that provide the same guarantee.

I think it's more of an industry vs. academia kind of thing. In the mid-90's before Java was released automatic memory management was mostly unknown to the unwashed masses. So garbage collection became synonymous to whatever Java was doing. However, The Garbage Collection Handbook originally published in 1996 defines garbage collection as: "All garbage collection schemes are based on one of four fundamental approaches; mark-sweep collection, copying collection, mark-compact collection or reference counting." So that's an example of terminology #2.

Yep. The compiler generates code that works the same way that an experienced C programmer would hand optimise alloc/free calls and manually keep track of shared data by increasing/reducing a reference counter. There is no separate mark/sweep or whatever step.

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.

Where can I read about Erlang’s magic?

Google suggests https://stackoverflow.com/questions/10221907/garbage-collect...

The comment claimed "There are zero GC pauses." Tbh, it's not clear how to interpret that. But real time simply means the pauses are guaranteed not to cross the realtime response budget. You still need to schedule the collection while the mutator is paused.

I'm gonna take a guess they dedicate a core to GC (or something along these lines).

That's not enough. Imagine a circular linked list. GC looks at an outside pointer to item A in it. Now another thread removes A from the list and moves the outside pointer to the next item. After that, GC would see all items in the list not referenced by anything (apart from the cycle).

Yeah, I didn't say it was sufficient. I just said it's probably one of the things they do.

No each thread does it’s own alloc/free. I reduce the locking to a minimum by using per-thread caching and memorisation. I had to implement that to make the code scale linearly with number of cores. Without per-thread caching it would only scale to about 3 cores. Now it scales very cleanly. Which is nice.

By requiring non-cyclic data structures or provide "weak" references. It's actually pretty easy to write most code without cycles. I program a lot in Nim and generally compile lots of programs with ARC and no cycle collector without issue.

Yep. The language doesnt allow data cycles. Nobody ever complained about that or even noticed it.

That seems a little hard to believe. I can't think of many complex pieces of software I've worked on that didn't have such cycles (e.g. any sort of tree structure where parents need to know about children and children need to know about parents - how does Nim handle that?)

You typically use a weak pointer from child to parent in those situations. So there are no ownership cycles. Languages without garbage collectors (C/C++) pretty much require you to not have ownership cycles or your code will crash during cleanup. Unless you add specific code to detect it and stop it from happening. So I assume you mostly work in GC languages and not C/C++?

We were talking about Nim, which is language I know next to nothing about (but very familiar with C/C++, Swift - which has weak pointers, as well as GC languages like JavaScript/Java/C# etc.)

Nim does allow cycles and the new GC is non-atomic RC + cycle collector.

Though I’ve been hacking on a UI framework written in Nim. Its ui nodes form a tree structure that only tracks parent => child. When it needs the parent info it makes a stack of parents during processing.

Essentially it moves the cycle collector / GC work to extra work during processing. But it’s cheaper since you’re already accessing the memory.

Not sure what you mean but Nim allows data cycles.

I just prefer to write cycle free code when I can and turn off the cycle collector. Though Nim’s cycle collector performs well and does some tricks using the RCs.

I simply don't do cycles. Software is simpler without them.

Agree. I can’t even come up with an example that couldn’t be done better without them.

The language has zero data cycles by design. It turns out that we didn’t need it. Thinking about it, I can’t remember even a single situation in my 30+ years career where I needed a data structure with data cycles. There are usually better ways to do it in my experience.

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.

What I understood from their comment (which may not be correct) is the following. Say you have something like this:

  extern void foo(T *p);   // some arbitrary function
  
  void bar1(bool cond)
  {
    ..
    auto p = std::make_unique<T, your_deleter>();
    if (cond) { return foo(p.release()); }
    ...
  }

This requires the compiler to call your_deleter::operator() regardless of whether cond is true or false, even though it's unnecessary (and can thus be slower) in the case where cond is true. Moreover, the obvious way to avoid it is to write it "C-style":

  void bar2(bool cond)
  {
    ..
    auto p = new T();
    if (cond) { return foo(p); }
    ...
    your_deleter()(p);
  }

which can up being faster when cond is true. But this isn't something an expert would generally want to do, as now the C++ code becomes unidiomatic, fragile, and unmaintainable.

In an ideal world, though, you could have an optimizer smart enough to do that transformation automatically. C++ compilers already do that in trivial cases, but they can't do it in general. My impression is that their Haskell compiler exploits the internal knowledge of what your_deleter does (i.e. reference counting) in order to optimize the code in various ways, like optimizing out such code, consolidating refcount updates, etc. And if I understand this correctly, there's no surprise at all that it can be faster than idiomatic C++ code written even by experts.

The question for me isn't the expertise of their programmers. Perhaps in their case they genuinely do need to have lots of objects on the heap, have (say) tight loops where they (for whatever reason) nevertheless cannot avoid the heap allocations, and don't have much of a use for finalizers besides freeing memory. In which case, I'm not surprised their solution clearly delivers better results than the C++ equivalent. The question from me, instead, is how well they think that generalizes, such as to (a) well-written Haskell programs in general, (b) well-written C++ programs in general, and/or (c) other domains. It would be one thing if their solution delivers better results in Haskell than C++ for their use case; it would be another thing if they could claim their solution delivers better results in Haskell than C++ for most use cases.

std::unique_ptr::release() resets the ptr to nullptr, which will be the first thing the deleter will check for and bail out.

This is a non-issue.

> which will be the first thing the deleter will check for and bail out.

The point is that check itself is an extra instruction (or two, rather) that would otherwise be skipped entirely.

I'm not saying this commonly makes a difference. I'm just saying this might be something that does make a difference for them in their particular use case.

Also note that I was trying to describe the general phenomenon with a simple example, but this obviously isn't limited to std::unique_ptr.

Yep you are quite right. The optimiser basically does what an experienced C++ optimisation experts would (tediously) do by hand: it carefully reduces the number of reference counter modifications to an absolute minimum by symbolically evaluating the full executing flow of the code. It is something that is doable in a pure functional language like this one. I am not sure if it is possible to do the same in C++ (because of the aliasing rules).

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

Which is a very good reason to develop an optimized GC algorithm, the domain experts can crank out code without having to optimize every single memory (de)allocation which sounds like a waste of their time.

It’s funny, people don’t usually doubt that a modern compiler can do a better optimization job than an expert but add a memory management algorithm and that’s a bridge too far.

Yep you are absolutely right. The business rules domain experts using the language are way more productive using a pure functional language that takes care of all the nitty gritty performance and memory issues for them. The code they write is 100% focused on solving customer problems.

Personally, I think non-GC languages are very much overused. If you are writing business logic, and not counting cycles (even worse - if you are never planning to count cycles), you should probably not use C++ or Rust.

However, a GC is a lot slower than manual memory management, which contrasts with the fact that most compiler activities are actually pretty low in overhead (now - it didn't used to be this way). Really, the only cost overhead left is the abstraction mismatch, and that is not too bad, when you compare to how bad humans are at writing assembly.

That said, this case looks like one where the C++ experts spent very little time optimizing (mostly writing business logic), and probably made a very poor choice of tools.

> However, a GC is a lot slower than manual memory management, which contrasts with the fact that most compiler activities are actually pretty low in overhead (now - it didn't used to be this way). Really, the only cost overhead left is the abstraction mismatch, and that is not too bad, when you compare to how bad humans are at writing assembly.

There is a triangle of GC performance; througput, latency (i.e. pause length), and memory overhead. Manual memory management will often be slower (in the throughput sense) than a throughput-tuned GC because:

1. Manual memory management typically precludes moving live data

2. Manual memory management often frees data as soon as it is dead

GC will often have faster allocations than manual memory management because #1 makes it possible to just use a pointer-increment for allocation. GC will often have faster freeing of data because of #2; in particular using a nursery with Cheney's algorithm makes it O(1) to free an arbitrary amount of data.

Where a throughput optimized GC falls down is in that any code that allocates may have an unpredictable amount of delay.

Also note that for video games, both typical GC and malloc/free are often too slow for per-frame data, so arena allocators are used, which sidestep #2, and allow a pointer-increment allocation without needing #1. This is specifically because there are a lot of objects with exactly the same bounds on their lifetime. Special-purpose algorithms will almost always trump general-purpose algorithms when run on the workload they are optimized for.

The C++ code I am referring to was hand optimised and maintained for 10+ years before the compiler I am maintaining was fast enough to take over. I never looked at the C++ code myself. I simply use it as the milestone to beat. When I took over the maintenance of the compiler it was 25x slower than the C++ code. It took a lot of work to finally make it faster. I also used the C++ code to compare the output of the compiler and the C++ code. I found quite a few bugs in the C++ code doing that by the way.

Just to clarify: it is not a framework. It is a whole program optimisation pass done by the compiler before lowering the intermediate code to LLVM and then generating machine code.

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.

> all memory could be handed off to a separate dedicated thread that actually calls free()

That only works when you have infinite memory (or infinite CPU resources).

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

Only if by "not stopping the world" you mean your previous suggestion (leaking unbounded amount of memory to free() everything at some later point). When your memory is bounded, you will eventually have to stop/crash once you have run out of it.

AFAIK, the best modern state of art garbage collectors have stop-the-world pauses, proportional to size of root set and/or thread count. I'd love to see an RC implementation, that does not have stop-the-world pauses at all, but that sounds as audacious as claims of perpetual motion machine.

I don't think the gp is describing the null garbage collector, rather one that can work incrementally and concurrently with the program doing its thing. Whereas a concurrent tracing gc has the problem of data changing while it runs and so special care has to be taken not to corrupt memory.

I don't think you understood my point. So let me give you a more concrete example.

The Linux kernel uses RCU to manage data structures that are concurrently read and updated. When an old value (after an update) is no longer needed, a thread can either:

(a) block for a while to make sure no other thread is using it using synchronize_rcu() and then free the memory (see https://www.kernel.org/doc/html/latest/core-api/kernel-api.h...)

(b) if the thread cannot block, it will use call_rcu to register a callback to free the memory at a later time (https://www.kernel.org/doc/html/latest/core-api/kernel-api.h...). That callback generally runs in some other thread to do the cleanup.

Now, moving the concepts to user space, a typical user space implementation will just launch a dedicated thread to free all memory that is no longer needed by any RCU data structures.

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

The compiler uses arrays for lists instead of linked lists. It is a performance improvement compared with how functional compilers usually do it. And the language is designed in such a way that rule writers manipulate whole lists at a time instead of one element at a time. A bit like array languages. It changes how the code is written compared with traditional functional code.

Pics or gtfo.

Yeah, GP's claim is completely bonkers. And they haven't provided any links or data to back up their nonsensical claim.

Yep the code is not open source so I can’t provide that. However I am happy to explain exactly how it works down to the lowest level details. Perhaps somebody gets inspired to implement it themselves as open source? That would be neat.

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.

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

There is nuance here. They claimed that their project is faster than a specific hand optimized project. Not faster than a theoretical peak performance c++ program.

I've run into similar situations where python reimplementation s are faster than java because python is easier to change and fixup algorithms. And %timeit in the ipython shell is way easier than the black magic involved in profiling and benchmarking java.

You also have people on rust subreddit or discourse asking for optimization help when their rust is not as fast as a Go example they wrote. Often you get buffered IO going and it's on par. But to melt faces like ripgrep and friends you often need to drop pretences and work on Vec<u8>s.

> And %timeit in the ipython shell is way easier than the black magic involved in profiling and benchmarking java

Unfair criciticm... first, Java has had a REPL for several years and you can time stuff like in Python as easily... second, profiling tools in Java are some of the best available, and are not blackmagic... quite simple to use, just attach them to the running process and hit "profile".

With that said: yes, I've also seen Java programs that run faster than the Rust or C counterpart. I suspect what OP saw falls into this category: a rare example that you take as a rule (maybe I misinterpreted the claim, I admit, but it does sound OP meant his Haskell program and, I assume, others which you write in the same style, cannot be beaten by the equivalent C++).

> Unfair criciticm... first, Java has had a REPL for several years and you can time stuff like in Python as easily... second, profiling tools in Java are some of the best available, and are not blackmagic... quite simple to use, just attach them to the running process and hit "profile".

You're right that the java tooling is powerful. But getting numbers out of the JVM is not the black magic. The dark arts are setting up an experiment, managing the JIT warm-up, and interpreting the results. In my experience it's just hell trying to turn those numbers into a convincing argument that we have confidence in our performance. Concrete example: convincing openjdk11 to use AES instructions Vs conscrypt using AES out of the box with no warm-up...

The whole song and dance means that we just don't take it as a priority because it's a tiring sink of effort. On the other hand %timeit is so easy and remains consistent that you can use it with unit tests and offer algorithm fixes in PRs.

> whatever the reference counting algorithm is doing can be emulated by the hand-optimised C++ code so that's just literally impossible.

shared_ptr and unique_ptr have pretty significant overhead and are common practice, even for optimized codebases, so I wouldn't say it's impossible at all.

unique_ptr is nearly overhead free compared to a bare pointer (except for argument passing... because of ABI concerns).

shared_ptr is expensive and easy to build leaks with, so a lot of code bases avoid it where possible. Though it's only expensive when you copy it, moving it is ~free.

This is just a more detailed version of my point lol you just listed the reasons they are not free.

You are 100% right. At some point I measured smart_ptr to be 25x slower than raw pointers. The compiler I am maintaining is not using C++ style smart pointers. It is using a global whole program optimisation pass to reduce reference manipulation to a minimum. Basically what a world class C++ programmer with years of experience optimising performance would do. It is just done automatically.

The code is not open source unfortunately so I can’t provide evidence. But I have nothing to sell or promote (unlike the V language guys who has a clear motivation to inflate what they are selling). What the compiler does differently is that it does a whole program optimisation pass where it minimises the code manipulating the reference counters to an absolute minimum. This is something you can’t do in a C++ compiler. Which is one of the reason why the resulting machine code is faster. Also, I am using LLVM as the backend. So I am getting the same low-level optimisations that C++ compilers get. However the most important optimisations are done before lowering the code to LLVM. Function specialisation for example is huge (generating multiple versions of the same function with the arguments unlined and optimised away). I am doing quite a few high level optimisations like that before even lowering it to LLVM.

> There are zero GC pauses. Unless you claim that a C++ alloc/feee call is “garbage collection”.

Alloc/free can introduce arbitrary pauses last I checked, so yes, there are pauses. Any time doing book keeping for resources rather than running your code counts as GC time.

> Any time doing book keeping for resources rather than running your code counts as GC time.

Perhaps a nitpick: memory management time, yes, but not GC time.

alloc/free is manual memory management, not garbage collection.

If you're using alloc/free in your GC, which is what was being implied, then that counts as GC time.

On any OS which is not hard realtime, there could be arbitrary pauses with any syscall. This is just nitpicking.

Nitpicking: arbitrary pauses can occur even without syscalls, when the OS preempts the program.

More nitpicking: on x86-64, SMI interrupts can cause arbitrary pauses even without any software control involved. Hard realtime on x86-64 is not possible.

More nitpicking: Your computer might turn off, cosmic rays might blow fuck up your RAM/CPU, Capital G God could reach down and pause the system, there's a universal quantum pause every 5.391247 × 10^-44 so that the universe can reboot, etc etc etc

Orrrrr, GC pause just means pauses caused by the GC as part of its implementation's work to manage memory.

This is not nitpicking. The OP was implying they were using alloc/free in their GC. Those calls can be doing all sorts of book keeping behind the scenes, including cascading destructor calls which could free a chain of objects the size of live memory. Suffice it to say, that would pause.

What happens in your language when a linked list is freed? Doesn't running its destructor (or its equivalent) take a linear amount of time relative to the length of the list?

My guess is that this could be done concurrently and/or in parallel.

It still take time linear in length, but dead nodes are by definition stable so it does not really matter when you free them.

So just like with tracing GCs. You do have a pause, which you may avoid with parallelism, or smear out incrementally. If you do it in parallel, your reference counting needs to be atomic, which adds further overhead. You still need to perform all the reference counting operations for each element of the list, not just free them, because part of the list may be shared. E.g. in SML:

  fun replace_head_with_1 (_::xs) = 1::xs;
  val a = [2, 3, 4];
  val b = replace_head_with_1 a;

Now a and b share the tail.

And a linked list is only a simple demonstration of a chain of pointers. It occurs spontaneously outside of containers, when you just write e.g. classes which have objects of other classes as their fields. In Haskell that would be records, or just an algebraic data type. Or just closures.

The compiler uses arrays not linked lists. One of the big mistakes that other functional compilers make (IMHO) is that they use linked lists. It is a huge performance problem. There is a reason why high-performance software written in C++ and C always use arrays and not linked lists. Memory access patterns is the #1 thing to optimise for on modern CPUs.

So, as I understand it, you avoid pauses by avoiding data structures with long chains of pointers. The same will work equally well in a language with a GC. It's also not the case that reference-counting itself doesn't result in pauses itself, but that the user is responsible for using such data structures that they do not result in pauses. Which I think is the only way when you care about performance, no matter whether you use manual memory management, reference counting or a tracing GC, so that's by no means a criticism of you or your language, I think it's very sensible. But I think that describing it as a no-pause memory management mechanism is a mischaracterisation.

So according to your logic no pause GC is impossible? In that case my claim is that it works as fast as what an expert in C/C++ optimisations would hand craft the compiled code to do by carefully minimising allocs/frees. This is what AAA games do to minimise stuttering. You can achieve the same with GC languages like Java. However you then have to manually keep a pool of objects and manually “alloc/free” objects from that pool. That is what games written in GC languages do to avoid random GC pauses.

No-pause GC is possible, when we're talking about concurrent GCs, but it also shouldn't be mistaken for a "no-overhead GC". And reference-counting, as long as the actual reference counting isn't done in a separate thread as well, instead of blocking in a destructor, which triggers other destructors, is not a no-pause GC. It's true that application developer can avoid pauses even then, but that's a different claim.

From what I've been told, C++ games do another thing and just use arena allocators, which make allocations cheap (just an integer addition, provided you know a reasonable upper bound on the size of an arena, and if you don't, you may reserve a large piece of virtual memory, and commit it later in reasonably small, but also not too large chunks) and free-s even cheaper (either reset the integer, so that the arena can be reused, or a single syscall to unmap the whole arena in one go). That's a different strategy than making a lot of little allocs and frees, and then trying to minimize them by reusing objects, which is also quite hairy.

For a unifying term I prefer Automatic Memory Management.

One reason is that GC is already universally used to mean only tracing garbage collection, and trying to defend its wider meaning is a pointless uphill battle.

Another is that is suits the job much better, because not every AMM technique works by producing garbage then collecting it, you know.

What are these other techniques and what can a technically-literate newcomer like myself read to get acquainted?

If you want to get even more precise, call it automatic dynamic memory management. Automatic static memory management would be something like Rust's scope-based memory reclamation via ownership.

Great to confuse more people instead of properly learning about affine type systems.

There's no confusion here? This is a perfectly natural classification, that satisfies many people's intuition about Rust as having "compile-time GC". If anything, bringing up affine type systems is more liable to confuse people in this context; just because a language has an affine type system doesn't necessarily mean it needs to use it for memory management.

I just keep feeding them the respective CS literature.

> not every AMM technique works by producing garbage then collecting it

And the confusing thing is that garbage collection (GC) doesn’t collect garbage, while reference counting (RC) does.

GC doesn’t look at every object to decide whether it’s garbage (how would it determine nothing points at it?); it collects the live objects, then discards all the non-live objects as garbage.

RC determines an object has become garbage when its reference count goes to zero, and then collects it.

That difference also is one way GC can be better than RC: if there are L live objects and G garbage objects, GC has to visit L objects, and RC G. Even if GC spends more time per object visited than RC, it still can come out faster if L ≪ G.

That also means that GC gets faster if you give it more memory so that it runs with a smaller L/G ratio (the large difference in speed in modern memory cache hierarchies makes that not quite true, but I think it still holds, ballpark)

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 polishing their GC solutions instead of using a much more trivial RC.

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.

This is normal today inside malloc implementations.

I think that’s been normal in malloc for some time. I maintain that we should all thank Java, and the hype train around it, for forcing operating systems to implement more robust threading support. Everyone wanted to be able to say they did Java well, and nearly every OS had capital ‘I’ Issues, including Solaris. Boy I bet those closed room arguments were epic.

Where GCed languages pulled ahead for a while, particularly Java, was that they had mature concurrent memory allocation before most OSes did, so many people found on early two and four core hardware that malloc started to show up as a bottleneck.

Fun fact: if you dont do anything important in the destructors you can avoid that delay by intentionally leaking the memory. The os will clean it up when the program exits and it does a better job since it frees the pages rather than looking at your objects one by one.

Most GCs do exactly that -- they only "work" when absolutely necessary, and their heuristics says that they are getting behind the created garbage. If the program exits shortly after it will just leak the memory.

The problem with that in the case of C++ is that you likely only want to leak things used in the end from the main thread, but not "recursively" - the distinction is hard to do.

It actually wouldn't surprise me that's the main reason GC often outperforms ARC in real- life software - simply because it's only necessary to actually bother doing GC once memory usage is high and there's a known need to allocate further memory. But couldn't ARC do the same thing in principle - i.e. only bother incrementing/decrementing reference counts when there's likely to be a need to reclaim memory? Even an infinitely running service can just accept it will increase its memory footprint up to a certain threshold then only bother with memory management at that point (I actually suspect SQL server works exactly like this!). For most short-running tools, no MM is required - the OS handles everything.

As mentioned elsewhere in the thread, the actual reclamation can be done asynchronously, but the most problematic part, namely decrementing a counter atomically is the most problematic part and it can’t just be done later willy-nilly.

It's not marketed as a GC, but exit(2) is fast and effective when used as one.

Now you've pushed the job of cleaning up page tables to the OS.

But that’s extremely easy - you go through a linear list once and free them all. You don’t even need to bring the contents from main memory to do it.

(Exception is shared pages, not used for heap memory often.)

It's definitely easier, because you don't have interior pointers. But it's still work :)

The OS would have that job anyway.

It's optimized for that, so just let it do its job.

https://devblogs.microsoft.com/oldnewthing/20120105-00/?p=86...

I wouldn't call it a GC. It's more like an arena allocator, with the arenas managed by the OS :)

Saying that both have pauses is a false equivalence to me.

It overlooks the difference in how likely this can occur (without large enough object graphs freed from the top it may never be an issue), when this occurs (any time vs on cleanup that may not be latency sensitive), and how much control the programmer has over RC costs (determinism allows to profile this and apply mitigations).

RC with borrow checking can avoid a lot of refcount increments.

Tracking GC typically needs write barriers, so it’s not free either.

> and how much control the programmer has over RC costs (determinism allows to profile this and apply mitigations).

I fail to see how would it be deterministic in a highly dynamic program. Like, imagine a game for example where the user can drag'n'drop different things to a "parent" object. Observability is imo an entirely different axis.

> RC with borrow checking can avoid a lot of refcount increments.

That's the same thing as escape analysis - with language support many many objects could be effectively "removed" from the guidance of the GC, decreasing load and greatly improving performance. It is a language-level feature, not inherent in the form of GC we do (RC vs tracing)

> Like, imagine a game for example where the user can drag'n'drop different things to a "parent" object.

Where is the reference count going to 0 here? Presumably the object you dragged from one parent to another parent just swapped the reference and no ref count ever went to 0 which would have triggered a free.

I'm guessing OP meant deterministic as in, "oh when I profile my code and it hits that big lag spike, this occurs in my particle system. Let's swap that to a fixed size static memory allocation instead of RC". Whereas with GC you say, "oh my program has a big lag spike. I wish I could tell why that is, but the code executing at that time may or may not have been the reason GC was collecting then". The only experience I've had trying to get accurate profiling data on memory usage in Java/C# was aggravating to say the least.

Also, most games these days (and probably since the beginning of gaming) don't allocate and free stuff randomly. They're most likely using RC on big blocks of memory that are shared among several other game objects. Or RC on several fixed size pools that get used for different components like in an ECS. Or they use RC for things like long living assets that have difficult lifetime management.

Honestly, RC and garbage collection are unnecessary in most instances. Most of the time all you need is a unique pointer because you know exactly where the ownership of the object lies. For the edge cases, RC works fine.

I guess my biggest complaint is, why rely on a magical algorithm that you have no control over? I've had so many "fun" times trying to force GC to collect at specific points. It's really nice when you can say, "at this point in the program, this ref count will go to 0 and it will free and I don't have to worry about it lagging anything". Rather than "please GC.collect(), actually do something when I call you right here and don't wait another 5 minutes and ignore my pleading".

> I've had so many "fun" times trying to force GC to collect at specific points

Because that's not the type of application for which a non-deterministic GC is suited. The vast majority of applications don't need that determinism. Right tool for the job.

Even in a highly dynamic program you can know all the places where releases happen. If you find a slow case, you can reproduce it, and mitigate (e.g. send object to a background thread to avoid lag on the ui thread). This is different from tracing GC that may fire on any allocation, on a timer, and workload depends on heuristics and other things in the program.

Escape analysis is hard, and GC is typically used to free programmers from assisting it with extra syntax or unsafety. This is why GC languages tend to use generational GC instead of having precise analysis.

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.

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 another in the same cache line. Overuse of pointers to organize data tends to pointer-chasing, among the slowest of operations on modern systems.

Typical GC passes consist of little else but pointer chasing.

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.

Systems are made fast by avoiding expensive operations not dictated by the actual problem. Reference counting, or any other sort of GC, counts as overhead: wasting time on secondary activity in preference to making forward progress on the actual reason for the computation.

Almost invariably neglected or concealed in promotion of non-RC GC schemes is overhead imposed by touching large parts of otherwise idle data, cycling it all through CPU caches. This overhead is hard to see in profiles, because it is imposed incrementally throughout the runtime, showing up as 200-cycle pauses waiting on memory bus transactions that could have been satisfied from cache if caches had not been trashed.

If a core is devoted to GC, then sweeps would seem to cycle everything through just that core's cache, avoiding trashing other cores' caches. But the L3 cache used by that core is typically shared with 3 or 7 other cores', so it is hard to isolate that activity to one core without wastefully idling those others. Furthermore, that memory bus activity competes with algorithmic use of the bus, slowing those operations.

Another way GC-dependence slows programs is by making it harder, or even impossible, to localize cost to specific operations, so that reasoning about perforce becomes arbitrarily hard. You lose the ability to count and thus minimize expensive operations, because the cost is dispersed throughout everything else.

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

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

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.

> RC may turn reads into writes, but of course, GC ends up having to go through literally every piece of memory ever from time to time.

Depends on the GC algorithm used. Various GC algorithms only trace reachable objects, not unreachable ones.

Reference counting does the opposite, more or less. When you deallocate something, it's tracing unreachable objects.

One of the problems with this is that reference counting touches all the memory right before you're done with it.

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

This is not a typical solution.

Java threw finalizers into the mix and everyone overused them at first before they realized that finalizers suck. This is bad enough that, in response to "too many files open" in your Java program, you might invoke the GC. Other languages designed since then typically use some kind of scoped system for closing file descriptors. This includes C# and Go.

Garbage collection does not need to be used to collect all objects.

> 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 rube goldberg machine was built around closing that gap.

When I hear rhetoric like this, all I think is, "Oh, this person really hates GC, and thinks everyone else should hate GC."

Embedded in this statement are usually some assumptions which should be challenged. For example, "memory should be freed as soon as it is no longer needed".

> 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 object graph. Instead, we continue to improve on a giant linked-list traversal through all of live memory to try and infer the object graph at runtime. Without sufficient information to do it efficiently. The fundamental issue is that we don't have languages that express our goals in a way that allows memory management to be elided efficiently.

That doesn't mean I have some particular affinity for reference counting, though. It has its own issues as you rightly point out. I prefer it for its determinism, nothing more.

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 basically "hacks" like RC, shared ptr, etc in low level languages to let us fake a partial GC (not collecting cycles).

On the plus side of GC, it has been one of the biggest productivity boosters the field has seen since the first non-assembly PL.

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

I meant hack as in languages meant for primarily for manual memory can still have RC (rust, C++), but that will only be a conservative GC algorithm due to no cycle detection. My use of hack here was only to denote that library-only RC , while possible, may not be the best approach and is used as an escape hatch in rare cases.

Oh, ok. That makes sense. Though I would count the Boehm Garbage Collector as a hack then, too?

Apropos hacks, have a look at this memory management 'thing' that doesn't move, but manages to compact: https://github.com/plasma-umass/Mesh

> 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", when it is definitely neither of those.

There's also a lot of people who formed their opinions on GC from, say, what the JVM was like in the 1990s.

And there's a lot of people who only have a vague idea of how GC works in theory, but no knowledge of deeper theory and no practical knowledge of how real-world GC algorithms work.

> And there's a lot of people who only have a vague idea of how GC works in theory

I agree. To better understand garbage collection, nothing better than implementation. This article is such a joy to read:

https://journal.stuffwithstuff.com/2013/12/08/babys-first-ga...

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.

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

Serious questions: if these garbage collectors are so good, why aren't they widely used? My guess is that they have downsides such as low throughput, high CPU usage, high memory usage, etc... You can't import a JVM GC into V8, to stay with my example, but you can reimplement the ideas if you have quasi-infinite money like Google.

For ZGC/Shenandoah because they're new, and they're new because they're extremely hard to implement well. For C4 because it is expensive and requires kernel patches. Also there isn't a whole lot of need for them in many use cases. Web servers for example have far bigger latency problems than GC, normally. Pauseless GC was historically driven by the HFT/finance sector for that reason.

Also yes, pauseless GC tends to have higher overheads than GC that pauses for longer. Whether that matters or not depends a lot on the use cases and actual size of the overheads. For example ZGC is pauseless but not yet generational. Generational ZGC when it launches will improve throughput significantly.

Google haven't done pauseless GC for V8. I don't know why not because they have done one for Android. ART uses a fully concurrent collector iirc. At any rate, although you can't import a JVM GC to V8, you can run JavaScript on the JVM using GraalJS and use the GCs that way. Though I don't recall off hand if Graal supports ZGC yet. There's no deep reason why it couldn't.

Thank you. I didn't know that one GC that I regularly use (as a user) - the one in Android - is so advanced these days. Interesting!

ART is a pretty astoundingly advanced JVM which gets nearly no publicity. It's a real shame. I bet a properly supported desktop version would be quite competitive with HotSpot!

https://source.android.com/devices/tech/dalvik/gc-debug#art_...

It also does mixed AOT / JITC, amongst other tricks.

> Even the best "real world" garbage collectors pause the program for order of magnitude a hundred milliseconds, no?

If you think GC pauses are measured in milliseconds, and not microseconds, then you're reading horribly outdated material. You're off by three orders of magnitude for an off-the-shelf GC with no tuning.

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

Most GC implementations that I can think of know which bits in memory are pointers and which aren't, and only scan the pointers.

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

This is patently untrue. Contemporary GCs have had card marking/scanning for 10+ years now.

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.

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

> It's much more complex and expensive to do this for tracing live data

But this is what happens in a modern state-of-the-art tracing GC implementation, isn't it?

And so it becomes a simple tracing GC implementation, while one keeps calling it RC to feel good.

You have to do this if you want deterministic deallocation, because your holding a read-only reference to that object might be exactly what keeps it around for longer. So you need to track that.

(Deterministic deallocation also means having to recursively free unreachable objects. That's often described as an arbitrary "pause" behavior in RC systems, but it's actually inherent in the requirement for deterministic behavior. If you don't care about determinism for some class of objects, you can amortize that pause by sending them to a separate cleanup thread.)

Pausing a single thread to release memory is not what is considered a "pause". Even if pausing a single thread could be a problem, you can trivially offload releasing to another thread. A pause is when all application threads get paused. Hence, reference counting does not have a problem of pauses, and tracing often does.

What is your read on the lack of discussion of escape analysis?

My own read on this is that it blurs the line with deferred collection/counting, because you could either use it to complement deferral making it cheaper, or avoid deferral because you're getting enough of the benefits of deferral by proving objects dead instead of discovering that they are dead.

Likewise it means that heap allocation on a tracing GC never took place and the object was allocated on the stack, or if small enough, on registers.

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 fluid implementation detail that is often necessary to understand deeply.

On the other hand such behavior can be a blessing in some situations. Maybe I do just want to hang an object off of some pubsub without having to decide the one true "owner" of the object.

If you're used to objects being destructed when they go out of scope ala C++ then yeah adapting to the lifecycle of objects in Java/C# takes some doing. But I think there's benefit to be had.

That doesn't sound quite right. When a object attaches a handler to an event, that creates a reference from the event source to the event listener. Until the handler is unattached, the event listener shouldn't be collected by GC, since it is technically still alive.

This lead to one of the more entertaining C# memory leak stories, where Princeton's entry to the DARPA Grand Challenge ended up failing because every frame they detected obstacles, created a class for each, and subscribed each obstacle object to an event. They missed that the event subscription was keeping those objects alive, and every piece of tumbleweed in the desert helped leak memory until the car just stopped! https://www.codeproject.com/Articles/21253/If-Only-We-d-Used...

I don't get that part. If it can receive an event/delegate, it means the object needs to be referenced by another object which invokes the event. If that is the case - how would be eligible for GC at all?

Consider an object referring to a network connection, say to a database. The object may be eligible for garbage collection but still have to respond to events from the network.

When it finally gets destroyed, its Destructor method would be called. At which point the thing at the other end of the network is told that it was talking to a zombie.

Note that network connections can be expensive for the other end, so this is a horrible design. We put a lot of work in to reliably get rid of connections when not needed. But you still need the fallback of being able to correctly handle programmer oversights.

Yeah you can't apply C++ style resource management (specifically, calling close() in destructors or expecting cascading destructors to trigger in sequence) to GC languages. Object lifetime in a GC languages does not generally align with desired resource lifetimes. You have to be explicit. This often means creating your own public close methods when wrapping a resource in a class.

One far-fetched yet simple example would be an observer/observable pair, where the observable mutates observed properties inside its finalizer. The observable will usually contain a reference to the observer, but not the other way round. So when the observable is dead but the observer (optionally) still alive, when the observables finalizer runs it will send a message to the observer.

When our observer is also dead (so the pair is out of scope) it will be a dead object receiving events.

It's a "feature" on the language, like others said below.

The codebase I work with has had many pathological crashes due to this behavior.

So basically in C# when you use += to subscribe to events, in a big system where lifetimes of objects are independent of each other, you're back to a C/C++ mindset where you should check you have a -= call for the subscribed object when the subscribing object is about to run out of scope. Else you get random crashes, when you get events delivered to an object that should have been dead.

This is one of the reasons I don't like "event" and += in C#. It's a leaky abstraction, like you said.

There's WeakEventManager [0] but that's available only in "classic" dotnet framework (and in "new" dotnet but only if you're targeting Windows) since it lives in the WPF namespace. It can be used outside of it, but you still take a dependency on System.Windows.

There are some other bespoke solutions too.

There's an open issue on the dotnet repo to add a weak event manager to the standard libs [1]. It's very well worth reading through it, it also has links to the other bespoke solutions available.

[0] https://docs.microsoft.com/en-us/dotnet/api/system.windows.w...

[1] https://github.com/dotnet/runtime/issues/18645

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.

> reference counting has pauses while tracing garbage.

Which pauses you are meaning?

Reference counting is not free, but there are no long pauses (long compare to GC, e. g. in JVM under certain workloads you can get 100ms pauses).

It's not always a tradeoff:

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

I disagree with the statement that modern memory architectures have much higher read bandwidth vs write bandwidth.

Benchmarks show they are within 30 percent of each other: https://www.techspot.com/images2/news/bigimage/2021/03/2021-...

https://www.anandtech.com/show/2525/5

While perhaps true, what needs to be compared here is read, vs read + write, no? Just writing isnt enough. And then we are at a factor above 2, assuming no thread contention. If there is contention, it can be a lot higher.

While "write bandwidth" is probably not the right term, writes are more expensive because you need to update caches. If you forked you might need to copy-on-write the page before you can write to it.

> Perhaps the biggest misconception about reference counting is that people believe it avoids GC pauses. That's not true.

When I can easily replace the deallocator (thus excluding most non-RC production GCs), I can (re)write the code to avoid GC pauses (e.g. by amortizing deallocation, destructors, etc. over several frames - perhaps in a way that returning ownership of some type and its allocations to the type's originating thread, and thus reducing contention while I'm at it!) I have done this a few times. By "coincidence", garbage generation storms causing noticable delays are suprisingly uncommon IME.

As programs scale up and consume more memory, "live data" outscales "garbage" - clever generational optimizations aside, I'd argue the former gets expensive more quickly, and is harder to mitigate.

It's also been my experience that tracing or profiling any 'ole bog standard refcounted system to find performance problems is way more easy and straightforward than dealing with the utter vulgarity of deferred, ambiguously scheduled, likely on a different thread, frequently opaque garbage collection - as found in non-refcounted garbage collection systems.

So, at best, you're technically correct here - which, to be fair, is the best kind of correct. But in practice, I think it's no coincidence that refcounting systems tend to automatically and implicitly amortize their costs and avoid GC storms in just about every workload I've ever touched, and at bare minimum, reference counting avoids GC pauses... in the code I've written... by allowing me easier opportunities to fix them when they do occur. Indirectly causal rather than directly causal.

> if you read a heap-object out of a data structure, you have to increment the object's reference count.

This isn't universal. Merely accessing and dereferencing a shared_ptr in C++ won't touch the refcount, for example - you need to copy the shared_ptr to cause that. Rust's Arc/Rc need to be clone()d to touch the refcount, and the borrow checker reduces much of the need to do such a thing defensively, "in case the heap object is removed out from under me".

Of course, it can be a problem if you bake refcounting directly into language semantics and constantly churn refcounts for basic stack variables while failing to optimize said churn away. There's a reason why many GCed languages don't use reference counting to optimize the common "no cycles" case, after all - often, someone tried it out as an obvious and low hanging "optimization", and found it was a pessimization that made overall performance worse!

And even without being baked into the language, there are of course niches where heavy manipulation of long-term storage of references will be a thing, or cases where the garbage collected version can become lock-free in a context where such things actually matter - so I'll 100% agree with you on this:

> There are no hard lines; this is about performance tradeoffs, and always will be.

Reply on news.ycombinator.com