6 ms·

You might as well classify allocating without freeing as a form of garbage collection. If the implementation can fail to collect cycles and the language can cr

You might as well classify allocating without freeing as a form of garbage collection. If the implementation can fail to collect cycles and the language can create them, thus leaking memory, lumping in reference counting with real garbage collection is a bad definition because it smears together a crucial distinction. I get that some people, or many people, or some book, have defined it that way, but others have used it in the meaning as distinguished from plain refcounting. Many developers have always understood GC and refcounting (in languages with mutation) to be mutually exclusive concepts. That definition is used in practice, and when people say, "I'm going to implement garbage collection for my programming language," what they mean is one which doesn't leak memory. A reason people use this other definition may be that plain reference counting and "having a garbage collector" are mutually disjoint, even if you define "garbage collection" as including reference-counted implementations. Making garbage collection a distinct concept from the set of acts a garbage collector might do will always be fighting against how language usually works.

kibwen 5y ago
They get lumped together because when some people say "garbage collection" they mean "whatever Java specifically does", and when other people say "garbage collection" they mean "automatic dynamic lifetime determination" (as a contrast to C-style "manual static lifetime determination", or Rust-style "automatic static lifetime determination").
Kranar 5y ago
>You might as well classify allocating without freeing as a form of garbage collection. Of course, Java even explicitly supports this garbage collection strategy: https://openjdk.java.net/jeps/318 https://openjdk.java.net/jeps/318 The best definition I've read comes from Raymond Chen, which is that garbage collection is a system to simulate an infinite amount of memory: https://devblogs.microsoft.com/oldnewthing/20100809-00/?p=13203 https://devblogs.microsoft.com/oldnewthing/20100809-00/?p=13... This definition is very elegant in that it allows one to reason about program correctness across all garbage collectors without having to know any of the implementation details, be it reference counting or the many flavors of mark and sweep. Basically garbage collection is not an implementation detail, nor is it a specific algorithm or even class of algorithms, garbage collection is a goal, namely the goal of achieving an infinite amount of memory. Different algorithms will reach that goal to different degrees and with different trade-offs.
cmrdporcupine 5y ago
RC need not leak memory. If it's done right, it doesn't. That Objective-C exposed the innards of the system badly enough that it was possible to leak, that's not intrinsic to RC. It's just yet another piece of the awkward legacy puzzle that is Objective-C. As for cycles.. Cycle detection in RC has been a solved problem for over two decades. I implemented it once, based on a paper from some IBM researchers, if I recall.
- tomp 5y ago
  Can you link to some resources/papers detailing how to solve this problem? I’m only aware of “RC+GC” solution (i.e. adding a full tracing GC in addition to RC to find and collect cycles).
  - hayley-patton 5y ago
    David F. Bacon and V. T. Rajan, Concurrent Cycle Collection in Reference Counted Systems https://www.cs.purdue.edu/homes/hosking/690M/Bacon01Concurrent.pdf https://www.cs.purdue.edu/homes/hosking/690M/Bacon01Concurre...
    - cmrdporcupine 5y ago
      That's the one I was thinking of, and I once implemented that one myself in C++ back in, uh, 2001, 2002, during a bout of unemployment in the .com crash. I guess I just assumed that there's been some advancement in the world since then.
- mojuba 5y ago
  Cycles in RC is a fundamentally unsolvable problem because there are situations when you in fact want an unreferenced cycle exist in memory at least for a while. Imagine a slow async operation such as a network request, where a GUI object is locked in a cycle with a self reference in a callback. Before the network response arrives the GUI object may be removed from the view hierarchy (e.g. the user has navigated away), however, whether you want the cycle to be broken or not depends on your needs. You may want to wait for the results, update stuff and break the cycle manually, or you may choose to completely discard the results by declaring weak self. Therefore, solving the problem of cycles with RC I think means giving more manual control. Explicit weak pointers solve part of the problem, but the "I know what I'm doing" scenario requires great care and is obviously error prone. To my knowledge this hasn't been solved in any more or less safe manner.
prionassembly 5y ago
So many words, so little clarity.
- solarengineer 5y ago
  Are you referring to the response by SamReidHughes? I understood it perfectly, and indeed, that was my own understanding as well. Could you elaborate on what you feel should be explained with more clarity?

kibwen 5y ago

They get lumped together because when some people say "garbage collection" they mean "whatever Java specifically does", and when other people say "garbage collection" they mean "automatic dynamic lifetime determination" (as a contrast to C-style "manual static lifetime determination", or Rust-style "automatic static lifetime determination").

Kranar 5y ago

>You might as well classify allocating without freeing as a form of garbage collection. Of course, Java even explicitly supports this garbage collection strategy: https://openjdk.java.net/jeps/318 https://openjdk.java.net/jeps/318 The best definition I've read comes from Raymond Chen, which is that garbage collection is a system to simulate an infinite amount of memory: https://devblogs.microsoft.com/oldnewthing/20100809-00/?p=13203 https://devblogs.microsoft.com/oldnewthing/20100809-00/?p=13... This definition is very elegant in that it allows one to reason about program correctness across all garbage collectors without having to know any of the implementation details, be it reference counting or the many flavors of mark and sweep. Basically garbage collection is not an implementation detail, nor is it a specific algorithm or even class of algorithms, garbage collection is a goal, namely the goal of achieving an infinite amount of memory. Different algorithms will reach that goal to different degrees and with different trade-offs.

cmrdporcupine 5y ago

RC need not leak memory. If it's done right, it doesn't. That Objective-C exposed the innards of the system badly enough that it was possible to leak, that's not intrinsic to RC. It's just yet another piece of the awkward legacy puzzle that is Objective-C. As for cycles.. Cycle detection in RC has been a solved problem for over two decades. I implemented it once, based on a paper from some IBM researchers, if I recall.

tomp 5y ago
Can you link to some resources/papers detailing how to solve this problem? I’m only aware of “RC+GC” solution (i.e. adding a full tracing GC in addition to RC to find and collect cycles).
- hayley-patton 5y ago
  David F. Bacon and V. T. Rajan, Concurrent Cycle Collection in Reference Counted Systems https://www.cs.purdue.edu/homes/hosking/690M/Bacon01Concurrent.pdf https://www.cs.purdue.edu/homes/hosking/690M/Bacon01Concurre...
  - cmrdporcupine 5y ago
    That's the one I was thinking of, and I once implemented that one myself in C++ back in, uh, 2001, 2002, during a bout of unemployment in the .com crash. I guess I just assumed that there's been some advancement in the world since then.
mojuba 5y ago
Cycles in RC is a fundamentally unsolvable problem because there are situations when you in fact want an unreferenced cycle exist in memory at least for a while. Imagine a slow async operation such as a network request, where a GUI object is locked in a cycle with a self reference in a callback. Before the network response arrives the GUI object may be removed from the view hierarchy (e.g. the user has navigated away), however, whether you want the cycle to be broken or not depends on your needs. You may want to wait for the results, update stuff and break the cycle manually, or you may choose to completely discard the results by declaring weak self. Therefore, solving the problem of cycles with RC I think means giving more manual control. Explicit weak pointers solve part of the problem, but the "I know what I'm doing" scenario requires great care and is obviously error prone. To my knowledge this hasn't been solved in any more or less safe manner.

prionassembly 5y ago

So many words, so little clarity.

solarengineer 5y ago
Are you referring to the response by SamReidHughes? I understood it perfectly, and indeed, that was my own understanding as well. Could you elaborate on what you feel should be explained with more clarity?