Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Reference count, don't garbage collect

kevinlawler.com

Post reply on HN
Print view View original

31–40 of 415 posts

Re: Reference count, don't garbage collect

#31

Post by knome »

byefruit wrote: post #11

This article provides very little evidence for it's claims and seems to only have a superficial understanding of modern GCs. "Increments and decrements happen once and at a predictable time. The GC is running all the time and traversing the universe of GC objects. Probably with bad locality, polluting the cache, etc." This is only the case with a mark-sweep collector, usually most of your allocations die young in the…

>If GC is so good, why wouldn't Python just garbage collect everything, which they already did once and could trivially do

I don't think python ever did pure mark-and-sweep ( cpython, at least, I'm sure jython and other alternate implementations have ).

My understanding was that they did pure reference counting, and kludged on a sweep GC to do cycle breaking eventually, as manually breaking cycles in early versions of python was a pain point. A quick lookup seems to indicate python1 was pure reference counting, and they added the cycle breaking when they released python2.

Re: Reference count, don't garbage collect

#32

Post by adgjlsfhk1 »

OskarS wrote: post #15
pclmulqdq wrote: post #7

Earlier quoted context omitted.

Its actually usually slower than both manual memory management and GC. It's only coming back now because people are finally learning how to make memory allocations large and rare. This blog post is an answer to: "Tell me you haven't learned about cache coherence without telling me you haven't learned about cache coherence."

> Its actually usually slower than both manual memory management and GC [citation needed] You and the blog post are arguing opposite things, and neither of you have shown any evidence. I get that you're arguing that reference counted objects are bigger (to store the reference count) and/or might use double indirection (depending on implementation), which are both bad for caches. It's not a bad argument. But the count…

The blog post is largely incoherent for several reasons.

1. It recommends 8 byte counters. This implies making every object in your programming language 8 bytes bigger which is pretty much a non-starter. Almost everyone that actually uses reference counting uses more like 2-4 bits.

2. Reference counting can have arbitrarily long pauses as well. If you decrease the reference count of an object to zero, you have to decrease the reference count of all referenced objects, which can do significant amounts of work (specifically, it will do a lot of work in the cases where regular GC does almost no work).

3. The blog states that atomic writes are "basically free", but that ignores the fact that in multi-threaded code, atomic writes can actually be fairly expensive since each one requires communication between every thread (This is why python still has a GIL)

4. Because no one uses 8 bytes for the count (since you don't want to double your memory consumption), you still need a GC anyway to deal with objects that get too many references.

Re: Reference count, don't garbage collect

#33

Post by cogman10 »

titzer wrote: post #30

I read most the article and it's just a lot of the same tired old arguments and an extremely simplified worldview of both GC and reference counting. I wish I had the author's address, because I'd like to mail them a copy of the Garbage Collection Handbook. They clearly have a very naive view of both garbage collection and reference counting. And there isn't a single dang measurement anywhere, so this can be completel…

Agreed. What I particularly disliked is how absent of nuance it is. RC is a form of GC and all GC algorithms make tradeoffs. RC trades throughput for latency. Compacting mark and sweep trade latency (and usually memory) for throughput.

The rant at the end can be boiled down to "I use confirmation bias [1] to make my engineering decisions". The OP has already decided that "GC" is slow, so I'm sure every time a runtime with it misbehaves it's "Well, that darn GC, I knew it was bad!" and every time RC misbehaves it's likely "Oh, well you should have nulled out your link here to break the cycle dummy!"

I really don't like such absolutist thinking in software dev. All of software dev is about making tradeoffs. RC and GC aren't superior or inferior to each other, they are just different and either (or both) could be valid depending on the circumstance.

[1] https://en.wikipedia.org/wiki/Confirmation_bias

Re: Reference count, don't garbage collect

#34

Post by cogman10 »

knome wrote: post #31
byefruit wrote: post #11

This article provides very little evidence for it's claims and seems to only have a superficial understanding of modern GCs. "Increments and decrements happen once and at a predictable time. The GC is running all the time and traversing the universe of GC objects. Probably with bad locality, polluting the cache, etc." This is only the case with a mark-sweep collector, usually most of your allocations die young in the…

>If GC is so good, why wouldn't Python just garbage collect everything, which they already did once and could trivially do I don't think python ever did pure mark-and-sweep ( cpython, at least, I'm sure jython and other alternate implementations have ). My understanding was that they did pure reference counting, and kludged on a sweep GC to do cycle breaking eventually, as manually breaking cycles in early versions o…

That's my recollection as well (though I've not found evidence to support it). In fact, IIRC, as part of the python performance thing one of the topics was adding a proper generational GC into python for objects that don't refer to pinned memory.

Re: Reference count, don't garbage collect

#35

Post by marginalia_nu »

OskarS wrote: post #15
pclmulqdq wrote: post #7

Earlier quoted context omitted.

Its actually usually slower than both manual memory management and GC. It's only coming back now because people are finally learning how to make memory allocations large and rare. This blog post is an answer to: "Tell me you haven't learned about cache coherence without telling me you haven't learned about cache coherence."

> Its actually usually slower than both manual memory management and GC [citation needed] You and the blog post are arguing opposite things, and neither of you have shown any evidence. I get that you're arguing that reference counted objects are bigger (to store the reference count) and/or might use double indirection (depending on implementation), which are both bad for caches. It's not a bad argument. But the count…

Eh, the GC you are describing sounds like something out of 1994. Modern concurrent algorithms do not need to stop execution. This type of code may paradoxically be slower in benchmarks when there isn't any memory churn, as it necessarily introduces barrier instructions at key points to ensure the GC has a consistent view of the memory (although memory consistency is also a concern for reference counting).

Re: Reference count, don't garbage collect

#36

Post by titzer »

cogman10 wrote: post #33
titzer wrote: post #30

I read most the article and it's just a lot of the same tired old arguments and an extremely simplified worldview of both GC and reference counting. I wish I had the author's address, because I'd like to mail them a copy of the Garbage Collection Handbook. They clearly have a very naive view of both garbage collection and reference counting. And there isn't a single dang measurement anywhere, so this can be completel…

Agreed. What I particularly disliked is how absent of nuance it is. RC is a form of GC and all GC algorithms make tradeoffs. RC trades throughput for latency. Compacting mark and sweep trade latency (and usually memory) for throughput. The rant at the end can be boiled down to "I use confirmation bias [1] to make my engineering decisions". The OP has already decided that "GC" is slow, so I'm sure every time a runtime…

> absent of nuance

Yes, this is a good point. It makes overly general claims.

E.g. a GC proponent could claim "well, tracing collectors do no work for dead objects, so they have no overhead!" Which is a good point, but not the whole story. Tracing collectors may need to repeatedly traverse live objects. Sure. But then generational collectors only traverse modified live objects that point to new objects. True. And concurrent collectors can trace using spare CPU resources, incremental collectors can break marking work up into small pauses, on and on. There are zillions of engineering tradeoffs and the GC Handbook covers most of them really well.

Re: Reference count, don't garbage collect

#37

Post by adgjlsfhk1 »

marginalia_nu wrote: post #35
OskarS wrote: post #15

Earlier quoted context omitted.

> Its actually usually slower than both manual memory management and GC [citation needed] You and the blog post are arguing opposite things, and neither of you have shown any evidence. I get that you're arguing that reference counted objects are bigger (to store the reference count) and/or might use double indirection (depending on implementation), which are both bad for caches. It's not a bad argument. But the count…

Eh, the GC you are describing sounds like something out of 1994. Modern concurrent algorithms do not need to stop execution. This type of code may paradoxically be slower in benchmarks when there isn't any memory churn, as it necessarily introduces barrier instructions at key points to ensure the GC has a consistent view of the memory (although memory consistency is also a concern for reference counting).

Note that if you can afford stop the world pauses, GCs that use them are much more efficient. Parallel stop the world garbage collectors are by far the best for minimizing runtime, while concurrent GCs have higher overhead, but can guarantee no significant pauses.

Re: Reference count, don't garbage collect

#38

Post by cosmotic »

> This is about as minimal as you can get short of nothing at all.

With GC, you can do nothing at all. In a system with lots of garbage, you can do a GC by copying everything accessible from the GC root, then de-allocating all the garbage in a single free.

Re: Reference count, don't garbage collect

#39

Post by marginalia_nu »

adgjlsfhk1 wrote: post #37
marginalia_nu wrote: post #35

Earlier quoted context omitted.

Eh, the GC you are describing sounds like something out of 1994. Modern concurrent algorithms do not need to stop execution. This type of code may paradoxically be slower in benchmarks when there isn't any memory churn, as it necessarily introduces barrier instructions at key points to ensure the GC has a consistent view of the memory (although memory consistency is also a concern for reference counting).

Note that if you can afford stop the world pauses, GCs that use them are much more efficient. Parallel stop the world garbage collectors are by far the best for minimizing runtime, while concurrent GCs have higher overhead, but can guarantee no significant pauses.

Yeah, that's true, but it shouldn't be held against GC that it interrupts the execution, since it really doesn't have to.

Re: Reference count, don't garbage collect

#40

Post by pclmulqdq »

OskarS wrote: post #15
pclmulqdq wrote: post #7

Earlier quoted context omitted.

Its actually usually slower than both manual memory management and GC. It's only coming back now because people are finally learning how to make memory allocations large and rare. This blog post is an answer to: "Tell me you haven't learned about cache coherence without telling me you haven't learned about cache coherence."

> Its actually usually slower than both manual memory management and GC [citation needed] You and the blog post are arguing opposite things, and neither of you have shown any evidence. I get that you're arguing that reference counted objects are bigger (to store the reference count) and/or might use double indirection (depending on implementation), which are both bad for caches. It's not a bad argument. But the count…

The blog post about this is pretty much incoherent, and comes from a bad understanding of performance, atomic, GC algorithms, and reference counting.

The ONLY reason to reference count is when you need GC-like behavior on a few objects, but do not want to impose a GC on all objects. It is a very valuable tool in performance code not because it is fast, but because it allows you to make other things fast. Suggesting that you should reference count the world is patently ridiculous. This is the reason for Rust's Arc and C++ shared_ptr, not that they are faster than a GC.

The blog post completely brushes aside the costs of _atomic_ counter increments and decrements, calling them "just increments." The "atomic" is the key performance problem, not the increment.

Reference counting also makes objects larger so small objects cannot fit inside a machine register.

Modern GC algorithms are very efficient. They do not need to pause the world, and they do not need to be jittery. However, someone who doesn't understand how expensive atomic ops are probably wouldn't understand this either.

Post reply on HN