9 ms·

I think it’s better to view reference counting and gc as two kinds of garbage collection: https://courses.cs.washington.edu/courses/cse590p/05au/p50-bacon.pdf h

I think it’s better to view reference counting and gc as two kinds of garbage collection: https://courses.cs.washington.edu/courses/cse590p/05au/p50-bacon.pdf https://courses.cs.washington.edu/courses/cse590p/05au/p50-b...

jdougan 2y ago
That is an excellent paper. One of those things that is obvious in hindsight, but no one wrote it down clearly before.
- _a_a_a_ 2y ago
  IMO it's not remotely obvious. Not to me anyway.
  - vlovich123 2y ago
    It’s obvious that is the same problem. It’s not obvious that it’s a more continuous linear tradeoff between the approaches
dataflow 2y ago
I have to disagree? Lumping them together is like lumping together formal verification with machine learning... Two fundamental characteristics of garbage collection (in pretty much every programmer's experience) are that (a) it can handle cycles (read: more general programs), and (b) it does not provide hard performance guarantees in the general case. Reference counting is literally the opposite, and that's exactly what people love about it.
- wbl 2y ago
  Reference counting does not provide hard performance guarantees. If you disagree consider what happens when a large tree is freed at the root.
  - dataflow 2y ago
    > Reference counting does not provide hard performance guarantees. If you disagree consider what happens when a large tree is freed at the root. Sure it does. One hard guarantee in that case is that freeing M objects (out of N total that are alive) takes O(M) time. (Another is that you can access all the other objects in parallel without any impact. Etc.)
    - hashmash 2y ago
      There's no hard guarantee that freeing an object runs in constant time. Reference counting tends to provide more predictable performance, but I don't think the phrase "hard guarantee" is appropriate.
      - dataflow 2y ago
        You're conflating a bunch of things, but the biggest one here is that "hard performance guarantee" is not a synonym for "constant-time performance". Nevertheless, feel free to substitute your own preferred vocabulary. I'm just trying to get the underlying point across about how different GC and RC fundamentally are.
        pulse7 2y ago
        With optimized RC (which deffer deallocation) you have no "constant-time performance guarantee", because you don't know at which time the deffered deallocation will happen... And all modern RC implementations are heavily optimized - especially in Apple's ecosystem...
        camgunz 2y ago
        Yeah I think generally what people mean here is, "if I'm aware that freeing objects takes time, I expect to spend that time when I free the objects, not at some undetermined point in the future". That's not the case if you do any kind of deferring, at which point you're pretty close to a "classic" GC system.
- rbehrends 2y ago
  First of all, I recommend giving the paper a read, because I think you're misunderstanding the claim (plus, it is a very good paper). The claim is not that they are equivalent, but that tracing GC and reference counting are dual solutions to the same problem, two ends of the same spectrum if you will, with hybrid solutions existing in between. Second, what you seem to consider to be fundamental characteristics of tracing GC and RC is not in fact so fundamental. For starters, RC absolutely can handle cycles (e.g. through trial deletion). Such implementations may be difficult or impossible to implement as pure library solutions, but there is nothing that says it can't be done. The most prominent example of a programming language that uses such an approach is probably Python. Nor does the claim that tracing GC cannot provide hard performance guarantees in the general case (while RC does) hold up under closer examination. Leaving aside the problem that it's already non-trivial to provide hard real time performance guarantees for malloc()/free() and ignoring the issue of cascading deletions, it doesn't hold under the more relaxed assumptions discussed downthread. For starters, we have such predictability only for the single-threaded case, not for arbitrary multi-threaded situations. And even in the single-threaded case, there are real use cases where predicting performance becomes functionally intractable. Examples are implementations of binary decision diagrams or certain persistent data structures, where the presence of shared subgraphs of arbitrary size make predicting performance of individual deallocations impractical. In contrast, in the single-threaded case we can absolutely bound individual operations of a tracing GC by either a constant or (in the case of arbitrarily sized allocations) make them linear in the number of bytes allocated (e.g. Baker's treadmill). What is true is that in the absence of cycles, (naive) reference counting will free memory at the earliest opportunity, which is not something we can say for tracing GC.
  - dataflow 2y ago
    > First of all, I recommend giving the paper a read I'll put it on my list, thanks for the recommendation, but it really has no impact on my point (see next point). > because I think you're misunderstanding the claim (plus, it is a very good paper) Note: I wasn't criticizing the paper. I was criticizing the comment, which claimed "it’s better" to view these as special cases. If it's not obvious what I mean, here's an analogy: it's the difference between having a great paper that reduces ~everything to category theory, vs. claiming "it's better" for the audience I'm talking to to view everything in terms of category theory. I can be impressed by the former while still vehemently disagreeing with the latter. > For starters, RC absolutely can handle cycles (e.g. through trial deletion). "Can handle" is quite the hedge. You "can" walk across the continent too, but at what cost? > The most prominent example of a programming language that uses such an approach is probably Python. You're saying Python uses RC to handle reference cycles, and doesn't need a GC for that? If so please ask them to update the documentation, because right now it specifically says "you can disable the collector if you are sure your program does not create reference cycles". https://docs.python.org/3/library/gc.html https://docs.python.org/3/library/gc.html > [...] hard real time [...] Nobody said "real time". I just said "hard guarantee".
- pulse7 2y ago
  The more optimized RC is, the more similar it is to GC - and this includes properties like cycle handling and performance guarantees.
  - pebal 2y ago
    RC is and will be slower than GC. Even in C++ I can have pointers managed by GC that are faster than shared_ptr.
thyecust 2y ago
This paper is referenced in this post too. As "a whole spectrum between the two." (RC and tracing GC)
stefanos82 2y ago
Reference Counting is one way of GC and you can clearly read in great detail about it in the book "The Garbage Collection Handbook", chapter 5 [1] [1] https://gchandbook.org/contents.html https://gchandbook.org/contents.html

jdougan 2y ago

That is an excellent paper. One of those things that is obvious in hindsight, but no one wrote it down clearly before.

_a_a_a_ 2y ago
IMO it's not remotely obvious. Not to me anyway.
- vlovich123 2y ago
  It’s obvious that is the same problem. It’s not obvious that it’s a more continuous linear tradeoff between the approaches

dataflow 2y ago

I have to disagree? Lumping them together is like lumping together formal verification with machine learning... Two fundamental characteristics of garbage collection (in pretty much every programmer's experience) are that (a) it can handle cycles (read: more general programs), and (b) it does not provide hard performance guarantees in the general case. Reference counting is literally the opposite, and that's exactly what people love about it.

wbl 2y ago
Reference counting does not provide hard performance guarantees. If you disagree consider what happens when a large tree is freed at the root.
- dataflow 2y ago
  > Reference counting does not provide hard performance guarantees. If you disagree consider what happens when a large tree is freed at the root. Sure it does. One hard guarantee in that case is that freeing M objects (out of N total that are alive) takes O(M) time. (Another is that you can access all the other objects in parallel without any impact. Etc.)
  - hashmash 2y ago
    There's no hard guarantee that freeing an object runs in constant time. Reference counting tends to provide more predictable performance, but I don't think the phrase "hard guarantee" is appropriate.
    - dataflow 2y ago
      You're conflating a bunch of things, but the biggest one here is that "hard performance guarantee" is not a synonym for "constant-time performance". Nevertheless, feel free to substitute your own preferred vocabulary. I'm just trying to get the underlying point across about how different GC and RC fundamentally are.
      - pulse7 2y ago
        With optimized RC (which deffer deallocation) you have no "constant-time performance guarantee", because you don't know at which time the deffered deallocation will happen... And all modern RC implementations are heavily optimized - especially in Apple's ecosystem...
        camgunz 2y ago
        Yeah I think generally what people mean here is, "if I'm aware that freeing objects takes time, I expect to spend that time when I free the objects, not at some undetermined point in the future". That's not the case if you do any kind of deferring, at which point you're pretty close to a "classic" GC system.
rbehrends 2y ago
First of all, I recommend giving the paper a read, because I think you're misunderstanding the claim (plus, it is a very good paper). The claim is not that they are equivalent, but that tracing GC and reference counting are dual solutions to the same problem, two ends of the same spectrum if you will, with hybrid solutions existing in between. Second, what you seem to consider to be fundamental characteristics of tracing GC and RC is not in fact so fundamental. For starters, RC absolutely can handle cycles (e.g. through trial deletion). Such implementations may be difficult or impossible to implement as pure library solutions, but there is nothing that says it can't be done. The most prominent example of a programming language that uses such an approach is probably Python. Nor does the claim that tracing GC cannot provide hard performance guarantees in the general case (while RC does) hold up under closer examination. Leaving aside the problem that it's already non-trivial to provide hard real time performance guarantees for malloc()/free() and ignoring the issue of cascading deletions, it doesn't hold under the more relaxed assumptions discussed downthread. For starters, we have such predictability only for the single-threaded case, not for arbitrary multi-threaded situations. And even in the single-threaded case, there are real use cases where predicting performance becomes functionally intractable. Examples are implementations of binary decision diagrams or certain persistent data structures, where the presence of shared subgraphs of arbitrary size make predicting performance of individual deallocations impractical. In contrast, in the single-threaded case we can absolutely bound individual operations of a tracing GC by either a constant or (in the case of arbitrarily sized allocations) make them linear in the number of bytes allocated (e.g. Baker's treadmill). What is true is that in the absence of cycles, (naive) reference counting will free memory at the earliest opportunity, which is not something we can say for tracing GC.
- dataflow 2y ago
  > First of all, I recommend giving the paper a read I'll put it on my list, thanks for the recommendation, but it really has no impact on my point (see next point). > because I think you're misunderstanding the claim (plus, it is a very good paper) Note: I wasn't criticizing the paper. I was criticizing the comment, which claimed "it’s better" to view these as special cases. If it's not obvious what I mean, here's an analogy: it's the difference between having a great paper that reduces ~everything to category theory, vs. claiming "it's better" for the audience I'm talking to to view everything in terms of category theory. I can be impressed by the former while still vehemently disagreeing with the latter. > For starters, RC absolutely can handle cycles (e.g. through trial deletion). "Can handle" is quite the hedge. You "can" walk across the continent too, but at what cost? > The most prominent example of a programming language that uses such an approach is probably Python. You're saying Python uses RC to handle reference cycles, and doesn't need a GC for that? If so please ask them to update the documentation, because right now it specifically says "you can disable the collector if you are sure your program does not create reference cycles". https://docs.python.org/3/library/gc.html https://docs.python.org/3/library/gc.html > [...] hard real time [...] Nobody said "real time". I just said "hard guarantee".
pulse7 2y ago
The more optimized RC is, the more similar it is to GC - and this includes properties like cycle handling and performance guarantees.
- pebal 2y ago
  RC is and will be slower than GC. Even in C++ I can have pointers managed by GC that are faster than shared_ptr.

thyecust 2y ago

This paper is referenced in this post too. As "a whole spectrum between the two." (RC and tracing GC)

stefanos82 2y ago

Reference Counting is one way of GC and you can clearly read in great detail about it in the book "The Garbage Collection Handbook", chapter 5 [1] [1] https://gchandbook.org/contents.html https://gchandbook.org/contents.html