4 ms·

Garbage collection means a way to automatically collect garbage. Reference counts automatically collect garbage. Therefore reference counting is a subset of g

Garbage collection means a way to automatically collect garbage. Reference counts automatically collect garbage. Therefore reference counting is a subset of garbage collection.

erichocean 7y ago
> Reference counts automatically collect garbage. Reference counts are used to manage resources, one of which is memory (and I'm assuming you are referring to no-longer-referenced memory as "garbage"). But that's not the only use for reference counts! You can, and should, use reference counts for external resources, such as files, or memory buffers on a GPU, or…. Garbage collection is COMPLETELY USELESS for managing non-memory resources because you need to be able to deterministically release non-memory resources (and oftentimes, memory resources—e.g., on the GPU). And since all a GC can do is examine memory, well, it doesn't work. Go ahead: point me to a 3D game engine using garbage collection for GPU resources. I'll wait. So yeah: "reference counting is a subset of garbage collection" is absolutely not true, and even the most basic knowledge of how reference counting is used in practice should be enough to convince anyone of that. Again: this meme needs to die. Garbage collection is not "super sophisticated reference counting", and in fact, can't even be used in most places where reference counting is used. It's not a substitution, or a superset, of reference counting. GC is a compelling alternative to reference counting for resources just in the main memory heap in some situations where performance (esp. total memory usage) isn't an important concern relative to, say, programmer productivity.
- erik_seaberg 7y ago
  You can close a non-memory resource when an object that owns it becomes garbage (Java calls this a "finalizer"), it's just not common. Those resources tend to be too expensive to leave unused indefinitely, and explicit closing risks IOExceptions but not disastrous undefined behavior. Refcounting detects new garbage more quickly than periodic tracing, which is why it costs so much more in bus cycles. But both are dynamically detecting live objects and garbage. I've also seen systems where the only reference count values are "one" and "more than one", with the latter going uncollected until tracing.
  - erichocean 7y ago
    > it's just not common It's not common because it doesn't actually solve deterministic resource disposal, which is what is actually required, and a problem reference counting trivially solves.
  - cesarb 7y ago
    > Those resources tend to be too expensive to leave unused indefinitely The real issue is not that these resources are expensive. The real issue is that they're limited. The usual example is the file descriptor table: once all 1024 (or whatever your ulimit is) slots are in use, trying to open any new file or file-like resource will fail. The same can happen for instance with disk space (once I had a system which could only release a disk file when the corresponding in-memory object was closed, and someone else forgot to close the objects after using them, so all disk space allocated to that system was used up and it stopped working), database connections, and many others. In fact, the only reason this isn't an issue with memory (which is also limited) is that the garbage collector notices when it's getting full, and starts trying to collect garbage. It could in theory do so for other resources like file descriptors, but not all (how could it know that a remote database, shared with other users, is nearing its connection limit?), and it would probably be very inefficient (like having to do a full scan of the memory just to have a chance to find an open file handle which isn't referenced by any live object and therefore could be closed). The main advantage of reference counting is that it's deterministic: it doesn't just detect new garbage "more quickly", it detects new garbage immediately after it becomes garbage, which keeps the resource usage at a minimum.
    - pron 7y ago
      > it's deterministic Sort of. It's only deterministic in the sense that as soon as an object is not referenced it is freed, but it's not entirely deterministic because you don't know exactly when (or even in what thread) that "as soon as" happens. > it detects new garbage immediately after it becomes garbage, which keeps the resource usage at a minimum. Yes, but that comes at a cost to performance. One of the observations that tracing GCs make is that you may not need to do any work to deallocate memory at all. For example, a simple copying algorithm used to manage the young generation in many generational collectors is based on the fact that more objects die young than survive, and it only does work to keep the (fewer) surviving objects alive and does not do any work to free (the many) dead objects. As a result allocation itself becomes much faster. Tracing indeed requires more memory, but it automatically uses that memory to reduce the cost of memory management. In fact the (amortized) cost of memory management can be reduced arbitrarily by enlarging the heap and using a tracing collector, so much so that it could, in principle, be made cheaper than even stack allocation.
- pron 7y ago
  > this meme needs to die. Garbage collection is not "super sophisticated reference counting", and in fact, can't even be used in most places where reference counting is used. It's not a substitution, or a superset, of reference counting. I never said that garbage collection is sophisticated reference counting so if you've seen that "meme," it wasn't here. But reference counting and tracing are two classical approaches to garbage collection, the garbage collection literature does refer counting as a garbage collection algorithm, and refcounting is used for garbage collection in languages such as Rust. Refcounting has other uses, too, but this discussion is about garbage collection and not about 101 uses for refcounting. Anyway, reference counting GC is not intrinsically more primitive or worse-performing than tracing, but in practice, tracing GCs tend to be sophisticated, while languages that rely on refcounting usually employ a rather simple algorithm. In fact, this is one of the attractions of refcounting for GC: it is easier to get OK performance with primitive refcounting than with primitive tracing.

Garbage collection means a way to automatically collect garbage. Reference counts automatically collect garbage. Therefore reference counting is a subset of garbage collection.

erichocean 7y ago

> Reference counts automatically collect garbage. Reference counts are used to manage resources, one of which is memory (and I'm assuming you are referring to no-longer-referenced memory as "garbage"). But that's not the only use for reference counts! You can, and should, use reference counts for external resources, such as files, or memory buffers on a GPU, or…. Garbage collection is COMPLETELY USELESS for managing non-memory resources because you need to be able to deterministically release non-memory resources (and oftentimes, memory resources—e.g., on the GPU). And since all a GC can do is examine memory, well, it doesn't work. Go ahead: point me to a 3D game engine using garbage collection for GPU resources. I'll wait. So yeah: "reference counting is a subset of garbage collection" is absolutely not true, and even the most basic knowledge of how reference counting is used in practice should be enough to convince anyone of that. Again: this meme needs to die. Garbage collection is not "super sophisticated reference counting", and in fact, can't even be used in most places where reference counting is used. It's not a substitution, or a superset, of reference counting. GC is a compelling alternative to reference counting for resources just in the main memory heap in some situations where performance (esp. total memory usage) isn't an important concern relative to, say, programmer productivity.

erik_seaberg 7y ago
You can close a non-memory resource when an object that owns it becomes garbage (Java calls this a "finalizer"), it's just not common. Those resources tend to be too expensive to leave unused indefinitely, and explicit closing risks IOExceptions but not disastrous undefined behavior. Refcounting detects new garbage more quickly than periodic tracing, which is why it costs so much more in bus cycles. But both are dynamically detecting live objects and garbage. I've also seen systems where the only reference count values are "one" and "more than one", with the latter going uncollected until tracing.
- erichocean 7y ago
  > it's just not common It's not common because it doesn't actually solve deterministic resource disposal, which is what is actually required, and a problem reference counting trivially solves.
- cesarb 7y ago
  > Those resources tend to be too expensive to leave unused indefinitely The real issue is not that these resources are expensive. The real issue is that they're limited. The usual example is the file descriptor table: once all 1024 (or whatever your ulimit is) slots are in use, trying to open any new file or file-like resource will fail. The same can happen for instance with disk space (once I had a system which could only release a disk file when the corresponding in-memory object was closed, and someone else forgot to close the objects after using them, so all disk space allocated to that system was used up and it stopped working), database connections, and many others. In fact, the only reason this isn't an issue with memory (which is also limited) is that the garbage collector notices when it's getting full, and starts trying to collect garbage. It could in theory do so for other resources like file descriptors, but not all (how could it know that a remote database, shared with other users, is nearing its connection limit?), and it would probably be very inefficient (like having to do a full scan of the memory just to have a chance to find an open file handle which isn't referenced by any live object and therefore could be closed). The main advantage of reference counting is that it's deterministic: it doesn't just detect new garbage "more quickly", it detects new garbage immediately after it becomes garbage, which keeps the resource usage at a minimum.
  - pron 7y ago
    > it's deterministic Sort of. It's only deterministic in the sense that as soon as an object is not referenced it is freed, but it's not entirely deterministic because you don't know exactly when (or even in what thread) that "as soon as" happens. > it detects new garbage immediately after it becomes garbage, which keeps the resource usage at a minimum. Yes, but that comes at a cost to performance. One of the observations that tracing GCs make is that you may not need to do any work to deallocate memory at all. For example, a simple copying algorithm used to manage the young generation in many generational collectors is based on the fact that more objects die young than survive, and it only does work to keep the (fewer) surviving objects alive and does not do any work to free (the many) dead objects. As a result allocation itself becomes much faster. Tracing indeed requires more memory, but it automatically uses that memory to reduce the cost of memory management. In fact the (amortized) cost of memory management can be reduced arbitrarily by enlarging the heap and using a tracing collector, so much so that it could, in principle, be made cheaper than even stack allocation.
pron 7y ago
> this meme needs to die. Garbage collection is not "super sophisticated reference counting", and in fact, can't even be used in most places where reference counting is used. It's not a substitution, or a superset, of reference counting. I never said that garbage collection is sophisticated reference counting so if you've seen that "meme," it wasn't here. But reference counting and tracing are two classical approaches to garbage collection, the garbage collection literature does refer counting as a garbage collection algorithm, and refcounting is used for garbage collection in languages such as Rust. Refcounting has other uses, too, but this discussion is about garbage collection and not about 101 uses for refcounting. Anyway, reference counting GC is not intrinsically more primitive or worse-performing than tracing, but in practice, tracing GCs tend to be sophisticated, while languages that rely on refcounting usually employ a rather simple algorithm. In fact, this is one of the attractions of refcounting for GC: it is easier to get OK performance with primitive refcounting than with primitive tracing.