Hacker News Reader

Comment by sklogic | Hacker News Reader

What?

Of course reference counting is slower. Especially if you take loop handling into account. Imagine a degenerate scenario: using up all of your memory to allocate a single linked list, and then dropping it all at once.

Another, much more common scenario: allocating huge numbers of very short living objects. A generational GC handles this with nearly zero overhead, while reference counting plus a heap allocation sucks on an epic scale.

Also, do not forget about the compactification and cache locality implications.

View on HN

> Another, much more common scenario: allocating huge numbers of very short living objects

This is true in Java. Other languages (C++, Rust, D, etc) give the programmer the means to not allocate so much garbage instead.

Yes, but Eiffel, D (on your list), Modula-3, Oberon(-2), Component Pascal, C#, Go are all examples of GC languages with finer control over static vs dynamic allocation.

Something that most GC vs RC discussions seem to keep forgetting about.

In Modula-3 I can even make use of manual memory management in unsafe modules, if really required. And control storage layouts even in safe code.

Think of all the functional languages, this is the most common memory access pattern there.

And C++ and alikes are well known for facilitating hilarious levels of memory fragmentation, no matter how smart your custom allocators are.

> Imagine a degenerate scenario: using up all of your memory to allocate a single linked list, and then dropping it all at once.

Sorry, I am not sure I follow this example. I assume you create a list O(n) in size where n is the maximum allowed by memory (not sure memory matters).

For RC: You drop the single list, as you drop the head, you decrease reference counts to each member (one-by-one), check reference counts for 0, and free them. I.e. taking O(n) time.

For Tracing GC: You'll eventually sweep, then check if each members is unreachable as determined by the sweeper, and free each member. I.e. also taking O(n) time.

Am I overlooking something?

> You'll eventually sweep

That's the key here. Eventually. When it is convenient to do so. You have a very fine grained control over when sweeper process may do its dirty job.

It's far more complicated with RC to ensure that it only does a certain small amount of work once in a while.

And with a loop detection, you have to do everything at once.

Also, with mark&sweep you can keep your tags somewhere else altogether and avoid touching (and invalidating) the actual data at all, at no additional cost.

OK, it wasn't clear to me that we were talking about RC with cycle detection.

Tracing GC is not always faster. GC time is proportional to the size of the allocated memory, reference counting time is not.

Reference counting time is proportional to data structure sizes on deletion.

You can get a "stop the world" effect with a cascade set of references reaching zero.

> Reference counting time is proportional to data structure sizes on deletion.

The actual garbage collection in all collectors is proportional to the amount of data that needs to be deleted. There are plenty of implementations of refcounting where the data is pushed into a freelist or cleaned up deferred.

At which point you start making RC behave more like tracing collectors, so why not start with them in first place?

Also there are generational tracing compacting collectors with (almost) no pauses, so I doubt such approach wins over them when measuring performance and fragmentation across application usages.

> The actual garbage collection in all collectors is proportional to the amount of data that needs to be deleted.

This is false, copying GC is a simple counterexample

Why do you even care about the GC epoch length? It does not affect the mutator performance at all.

EDIT: actually, it does a bit: the longer the epoch, the better, because at the end of the epoch a short stop-the-world is required to collect the global roots from registers and stacks.

It doesn't affect mutator performance, until it does, and your program grinds to a halt for several seconds.

> until it does

How exactly?

> grinds to a halt for several seconds

What? Stop-the-world in the realtime collectors is always for a set duration, only to scan the registers and tops of the stacks (if there are any stacks at all, stackless implementations have even a better latency).

> How exactly?

Heap fills up, you need a full collection. During that collection your program is running and allocating, but runs out of space, so it grinds to a halt.

Look, there is a reason why Rust is a thing, why realtime collectors are only used in niche cases, why there are people whose sole job is to fix GC issues, why there are people programming in Java/C# very carefully to ensure that a full heap collection never happens, etc. GC isn't a magic bullet.

> During that collection your program is running and allocating, but runs out of space, so it grinds to a halt.

It's a marginal case that should never happen, just like the case of running out of memory altogether. And RC will behave even worse in such a case.

Also, all three parts are running concurrently - marker, sweeper and mutator. Sweeper is constantly supplying the mutator with the new free cells from the current epoch, so you don't need to wait for another epoch to start getting new free cells.

It's not about running out of memory altogether, it's about the heap filling up with dead objects while the GC doesn't yet know that they are dead. Of course things are great when they are great and the GC can keep up with the mutator. Yet failure does happen whether or not you think it should happen, hence all the efforts that I mentioned that are trying to fix the issues.

As I said, in such a case RC would behave even worse.

Yes, you made that assertion.

This is not an assertion, it is a practical observation.

Reply on news.ycombinator.com