Hacker News Reader

Comment by bjourne | Hacker News Reader

The weak generational hypothesis states that most objects are short-lived. Therefore concentrating on collecting the youngest objects yields the most garbage/cpu cycle spent.

In the benchmark, all objects survive the same amount of time and it is the oldest objects that become garbage first. It is the opposite of the behavior the weak generational hypothesis presumes. So collectors optimized for that scenario is at a disadvantage. :)

For example, I ported the benchmark to Python 3 and got a max pause time of 0.05 ms. That's 40 times faster than OCaml but it doesn't mean Python is faster in general. It just "got lucky" because ref counting is an almost optimal fit for the benchmark. There is no strategy that fits all when it comes to memory management. :)

View on HN

Reference counting is great. I used to be skeptical but I'm a complete convert after using Objective-C.

The old myth about GC was that it was slow. Nowadays that's usually false, but what is true that it wastes a lot of memory, or has long pauses, or both.

The old myth about reference counting, on the other hand, is that uncollected cycles are a problem, but in practice they're usually not that hard to find and fix.

Reference counting is a bit slower, but it doesn't waste memory and doesn't pause. So it's great for throughput. And throughput is very often more important than overall performance!

For anything with a UI, you want maximum throughput. For anything on the server side that's realtime, or even indirectly user-facing, you want maximum throughput. The only time you want performance over throughput is batch jobs, which I reckon crop up less often than you expect.

(Edit to add: on memory-constrained devices, you might not want the memory overhead of GC even for batch jobs.)

Reference counting does not scale to multi-threaded programs well. Keeping reference counts up to date across multiple threads is maddeningly and frightenly hard to do efficiently. By the time you correctly solve the concurrent update problem for essentially every access the program does, you have a very complicated memory management system that incurs overhead on every single operation. Compare that with a GC that imposes overhead (usually) only on writes to objects, not "writes" to the stack or local variables going out of scope. Reference counting also incurs overhead for reading from objects. Empirical studies have shown that reads outnumber writes 10x to 1 usually. Why would you consider it to be just a _bit_ slower?

And of course reference counting pauses. Killing one object (its count dropping to zero) may cause a chain reaction of objects whose reference counts to drop to zero and need to be cleaned up. The difference is that you now suffer work proportional to the _dead_ data of the program. In comparison, a tracing GC does work proportional to the _live_ objects.

> Reference counting does not scale to multi-threaded programs well. Keeping reference counts up to date across multiple threads is maddeningly and frightenly hard to do efficiently.

Is this not just a matter of using an atomic reference count?

Yes, but atomics are pretty slow.

I guess, but that doesn't seem that bad.

> maddeningly and frightenly hard to do efficiently.

It definitely doesn't seem maddening or frightening. I'm not saying a GC isn't stricly better (because I'm unsure either way) but arc doesn't seem like some awful thing.

> Killing one object (its count dropping to zero) may cause a chain reaction of objects whose reference counts to drop to zero and need to be cleaned up.

That chain is trivial to interrupt and resume later. Compare that to interrupting any mark based GC.

Great explanation! Thanks!

You probably mean minimal latency, not maximum throughput. GC generally has higher throughput at the cost of latency and higher peak memory usage. :)

I've seen it repeated many times that GC has higher latency, but is there a benchmark? Imagine writing a Mac app, once with refcounting, and once with GC, and seeing which one has the longer pause time.

I can think of cases where GC has better latency, like deallocating a huge linked list. That will introduce a higher latency with refcounting and with manual deletion (like C) compared to GC, where the main thread doesn't need to block while traversing the list. Or does such a case not happen much in practice?

You mainly notice it in mobile apps, since you want silky smooth 60fps scrolling there. A pause longer than 5 or 10ms can easily cause you to drop a frame.

Hard to attribute that to GC.

Why hard? On Android, the GC will print a log entry telling you how long it took!

In my experience, aside from badly-written algorithms that just do too much work on the wrong thread, the main causes of momentary glitches are GC and I/O. Unfortunately you have limited control over those in application code (just using too much memory can cause some I/O churn). On mobile, the GPU drivers are often badly written and will give you random hiccups that can ultimately be traced back to I/O.

Not to turn this into an Apple vs Android battle, I hope, but I think this is an important point that is often overlooked -- Apple's hardware and software designs are really well-targeted to minimize those kind of glitches. They don't use GC and they always use very fast (AKA expensive) flash memory. So whatever else their flaws, Apple devices tend to have smoothly-animated UIs.

Oops, you're right! I think I had in mind something like "guaranteed throughput" but "consistent low latency" is definitely a better way to put it.

Parallel GC's throughput is limited by how hard the parallel thread is working as described in the article and which was the point.

But he's comparing to reference counting, where you pay a substantial throughput penalty round-tripping to RAM (especially if atomic) and don't get the benefit of a bump allocator.

This is an insightful comment. Thanks. I wonder how things would change if a second core was sitting idle anyway, like in a mobile app that does everything on the main thread. Would it then make sense to utilise the second core for greater performance? Imagine memory isn't a problem — some phones have plenty of memory, like 6GB on a OnePlus.

Unrelated to all the above, and related to your point about uncollected cycles not being a problem with refcounting, it does impose an overhead, like remember to use weak pointers to delegates in Objective-C. It's not as seamless to the programmer as GC. You can argue that it is (not) worth it, but there's no question it's more work for the programmer.

Apple's phones tend to have less memory, and fewer (but faster) cores. Along with Objective-C's reference counting, I think those are very smart choices for typical mobile app workloads.

In principle having lots of cores available is great, but in practice it's hard to utilise them effectively without also using tons of memory and/or battery.

There are cycle collecting reference counting algorithms, that due a limited trace within a subset of the object graph to detect and remove cycles.

I am still not clear on why Apple didn't go that direction.

Reference counting will still potentially pause though, when freeing large graphs of objects.

Yeah, but the pause is completely deterministically in control of your program.

Doing cycle collection basically ends up as hard as full GC right? Annotating with weak is not a big deal.

> Doing cycle collection basically ends up as hard as full GC right?

Not really. Yes you do need to have the ability to trace the object graph. But the actual algorithm isn't that bad.

I implemented this in C++ (for "fun" for a pet language VM i wrote) 15 years ago: http://researcher.watson.ibm.com/researcher/files/us-bacon/B...

That's interesting! I also implemented that algorithm for cycle collection (https://github.com/bjourne/c-examples/blob/master/libraries/...) and I found that like the GP states that it wasn't worth it. The problem was that there so many objects that were potentially part of garbage cycles that it required scanning a too large part of the heap.

Cycle detection took about 70% as long a full mark and sweep collection so I didn't think it was worth it considering how complicated the algorithm was. Is your implementation open source? If so, I'd love to see it and compare results.

I guess it's technically open source but it's old (15 year old C++) and based heavily on the pseudo-code in the paper and also tied heavily into the interpreter I was working on. I didn't do a lot of performance testing either.

The interpreter I was working on was for a language which was image-based and persistent, I guess much like a Smalltalk, etc. Reference counting was handy for aiding in determining when objects should be pages to/from the disk image and what should be in cache.

I think performance would depend a lot on the usage pattern of the object graph. My system also used a lot of immutable data. The only mutable structures were the objects that properties and methods hung off of, and hash tables.

> The pause is completely deterministically in control of your program.

In theory. In practice, the programmer may not be able to reproduce the pause to diagnose and fix it, or it may not bubble up to the top of the priority list. Whereas with a GC, this problem may not occur at all in the first place.

The question is whether such cases (large object graph or linked list) occur often enough in practice to be worth bothering about.

In practical terms, are there even many cases where cycles are desirable? The only case I can think of is threads (two threads communicating with each other). Most cycles I have seen even in GC'd languages were bad designs.

https://en.m.wikipedia.org/wiki/Dancing_Links is one.

The weak generational hypothesis states that most objects are short-lived.

Doesn't this mostly apply to the classical OO style of coding that developed in Smalltalk and early Java? More recently, there have been styles of coding which emphasize pass by value in order to have better cache locality in generated code. The old style of "composition/organization by indirection" resulted lots of followed pointers, resulting in more cache misses, resulting in slower execution.

There is no strategy that fits all when it comes to memory management. :)

There is a nice overall strategy being followed by the Go community here. The emphasis in golang seems to be on pass by value when feasible, and keeping an eye out for reducing GC pressure. This is synergistic with GC optimized for concurrency and short pause times and also synergistic with good profiling tools for identifying the source of allocations.

This strategy makes it fairly easy to first make applications that work, then optimize them. The amount of mental effort is far less than that required to manage memory. The consequences for making a mistake are far less harsh, and correcting mistakes is fairly easy.

Well, it is an hypothesis and not a theorem so it hasn't been proven. But the tendency of most objects to be short-lived is universal and doesn't vary depending on programming language.

I believe you are thinking of objects which are allocated on the stack as not being objects. But they are just as much objects all objects allocated on the heap.

The difference is that stack-allocated objects have a very limited lifetime as they go out of scope when the procedure in which they are allocated returns. That makes allocating them extremely cheap. In fact, modern compilers perform optimizations called escape analysis to determine if the object allocated is only being used in the procedure. If so, it doesn't "escape" it and it can be allocated on the stack instead.

Go's value types means they are putting the burden on choosing whether to allocate on the stack or on the heap on the programmer. Often the programmer does a much better job at deciding those things than the compiler, which is good for performance. But it adds one extra thing that the programmer has to think about.

It's a classic engineering trade-off between language complexity and performance. I prefer languages that sacrifices performance for simplicity, but there is nothing wrong with Go's choice either.

I believe you are thinking of objects which are allocated on the stack as not being objects.

Of course they are still objects. However, those are objects that don't have to be collected, though they are still involved as "roots" or starting places for GC scan.

The difference is that stack-allocated objects have a very limited lifetime as they go out of scope when the procedure in which they are allocated returns. That makes allocating them extremely cheap.

Which is the whole point of styles that emphasize pass by value and allocating on the stack. Thanks for repeating the basics for 3rd parties that might find it useful.

Good paraphrase of what I said. Thinking about those things as one codes is kind of optional, in that the program will still be correct and will still run. It's probably best left to a later optimization stage, though there will still be some burden on the programmer to avoid pathological performance. In any case, it's less burden than outright memory management.

From my understanding, the weak generational hypothesis holds for the majority of programs in general. In fact, it is particularly true of language that encourage immutable data ( because new data is created rather than existing data updated). I don't see why it would apply particularly to OO languages, in fact, I would assume that passing pointers around would result in less short-lived objects due to less copying.

From my understanding, the weak generational hypothesis holds for the majority of programs in general.

But in Smalltalk like languages, the GC has to deal with "all of it," including objects that were allocated "on the stack." Because in most cases, outside of optimized cases like SmallInteger, my understanding is that objects allocated on the heap no matter what, and only that pointer reference was allocated on the stack.

It applied very well to Smalltalk. But there was a tendency to have objects for everything, and even a stack allocation meant a heap allocation.

I don't see why it would apply particularly to OO languages, in fact, I would assume that passing pointers around would result in less short-lived objects due to less copying.

Composition facilitated by object reference can result in styles where the granularity is small, so there are lots of objects. When a new user defined Object mans a new allocation on the heap, this means a lot throughput for the GC.

That is the crux of the issue. I think the interesting thing about this benchmark is the degree to which different GCs assume the weak generational hypothesis to be true. For example, the Haskell/GHC GC seems to very much assume it, with its STW copying collector for all generations. On the other hand you have languages like Ocaml and Go which still have a lot of pointer chasing to do in the old generation, but have optimisations (concurrent/incremental GC) which prevent the pauses getting too long in the case that the hypothesis is broken.

It's interesting to hear about the Python results. Ref counting makes absolute sense in this case!

Reply on news.ycombinator.com