4 ms·

RC may turn reads into writes, but of course, GC ends up having to go through literally every piece of memory ever from bottom to top once in a while. RC limit

RC may turn reads into writes, but of course, GC ends up having to go through literally every piece of memory ever from bottom to top once in a while. RC limits itself to modifying only relevant objects, whereas GC reads all objects in a super cache-unfriendly way. Yes, an atomic read-modify-write is worse than a read, but it's not worse than a linked-list traversal of all of memory all the time. And of course, not all kinds of object lend themselves to garbage collection - for instance, file descriptors, since you can't guarantee when or if they'll ever close. So you have to build your own reference counting system on top of your garbage collected system to handle these edge cases. There's trade-offs, yes, but the trade-off is simply that garbage collected languages refuse to provide the compiler and the runtime all the information they need to know in order to do their jobs - and a massive 30 year long effort kicked off to build a Rube Goldberg machine for closing that knowledge gap.

klodolph 4y ago
> RC may turn reads into writes, but of course, GC ends up having to go through literally every piece of memory ever from time to time. Depends on the GC algorithm used. Various GC algorithms only trace reachable objects, not unreachable ones. Reference counting does the opposite, more or less. When you deallocate something, it's tracing unreachable objects. One of the problems with this is that reference counting touches all the memory right before you're done with it. > And of course, not all kinds of object lend themselves to garbage collection - for instance, file descriptors, since you can't guarantee when or if they'll ever close. So you have to build your own reference counting system on top of your garbage collected system. This is not a typical solution. Java threw finalizers into the mix and everyone overused them at first before they realized that finalizers suck. This is bad enough that, in response to "too many files open" in your Java program, you might invoke the GC. Other languages designed since then typically use some kind of scoped system for closing file descriptors. This includes C# and Go. Garbage collection does not need to be used to collect all objects. > There's trade-offs, yes, but the trade-off is simply that garbage collected languages refuse to provide the compiler and the runtime all the information they need to know in order to do their jobs - and a massive 30 year long rube goldberg machine was built around closing that gap. When I hear rhetoric like this, all I think is, "Oh, this person really hates GC, and thinks everyone else should hate GC." Embedded in this statement are usually some assumptions which should be challenged. For example, "memory should be freed as soon as it is no longer needed".
- arcticbull 4y ago
  > When I hear rhetoric like this, all I think is, "Oh, this person really hates GC, and thinks everyone else should hate GC." Yeah, I think it's an inelegant, brute-force solution to a language problem - and that we continue to throw good money after bad improving it. We should be investing in removing the need for GC through smarter compilers and through languages that allow us to better express our intent - and our object graph. Instead, we continue to improve on a giant linked-list traversal through all of live memory to try and infer the object graph at runtime. Without sufficient information to do it efficiently. The fundamental issue is that we don't have languages that express our goals in a way that allows memory management to be elided efficiently. That doesn't mean I have some particular affinity for reference counting, though. It has its own issues as you rightly point out. I prefer it for its determinism, nothing more.
  - kaba0 4y ago
    But reference counting is a GC-algorithm -- that does exactly the same thing: tries to infer the object graph at runtime. I really don't think it is a language problem, for several algorithms that one may want to write, GC is a necessity as object lifetime is not decidable at compile time. And it's not just some special parallel algorithm, I believe most business problems fall into this category - that's why we have basically "hacks" like RC, shared ptr, etc in low level languages to let us fake a partial GC (not collecting cycles). On the plus side of GC, it has been one of the biggest productivity boosters the field has seen since the first non-assembly PL.
    - eru 4y ago
      I wouldn't call reference counting a hack. The paper mention elsewhere in the comments, https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-garbage.pdf https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-... "A Unifying Theory of Garbage Collection" put this in context. For example, a generational garbage collection essentially employs a hybrid approach between tracing and reference counting. Similarly, depending on your system's trade-offs, reference counting might be better. Eg tracing garbage collection works really great for main memory, but for filesystems we typically use reference counting to decide whether to retire an inode. (The paper explains this in more detail.)
tsimionescu 4y ago
> RC limits itself to modifying only relevant objects, whereas GC reads all objects in a super cache-unfriendly way. Yes, an atomic read-modify-write is worse than a read, but it's not worse than a linked-list traversal of all of memory all the time. All tracing GC algorithms scan only live memory, and they typically do so in an array-like scan (writing some bits in the object header when a pointer to that object is discovered), not in linked-list order.
int_19h 4y ago
Most GC implementations that I can think of know which bits in memory are pointers and which aren't, and only scan the pointers.
bitcharmer 4y ago
> RC may turn reads into writes, but of course, GC ends up having to go through literally every piece of memory ever from bottom to top once in a while. > RC limits itself to modifying only relevant objects, whereas GC reads all objects in a super cache-unfriendly way. Yes, an atomic read-modify-write is worse than a read, but it's not worse than a linked-list traversal of all of memory all the time. This is patently untrue. Contemporary GCs have had card marking/scanning for 10+ years now.
garethrowlands 4y ago
Pointer chasing is expensive because fetching a random location defeats locality and therefore caches the the CPU's stream detection. But a compacting GC copies the data it's scanned into a contiguous stream, dramatically improving locality, cache utility and stream detection. And this affects not only subsequent GCs but also the application itself, which may traverse its object graph far more often than the GC does.

klodolph 4y ago

> RC may turn reads into writes, but of course, GC ends up having to go through literally every piece of memory ever from time to time. Depends on the GC algorithm used. Various GC algorithms only trace reachable objects, not unreachable ones. Reference counting does the opposite, more or less. When you deallocate something, it's tracing unreachable objects. One of the problems with this is that reference counting touches all the memory right before you're done with it. > And of course, not all kinds of object lend themselves to garbage collection - for instance, file descriptors, since you can't guarantee when or if they'll ever close. So you have to build your own reference counting system on top of your garbage collected system. This is not a typical solution. Java threw finalizers into the mix and everyone overused them at first before they realized that finalizers suck. This is bad enough that, in response to "too many files open" in your Java program, you might invoke the GC. Other languages designed since then typically use some kind of scoped system for closing file descriptors. This includes C# and Go. Garbage collection does not need to be used to collect all objects. > There's trade-offs, yes, but the trade-off is simply that garbage collected languages refuse to provide the compiler and the runtime all the information they need to know in order to do their jobs - and a massive 30 year long rube goldberg machine was built around closing that gap. When I hear rhetoric like this, all I think is, "Oh, this person really hates GC, and thinks everyone else should hate GC." Embedded in this statement are usually some assumptions which should be challenged. For example, "memory should be freed as soon as it is no longer needed".

arcticbull 4y ago
> When I hear rhetoric like this, all I think is, "Oh, this person really hates GC, and thinks everyone else should hate GC." Yeah, I think it's an inelegant, brute-force solution to a language problem - and that we continue to throw good money after bad improving it. We should be investing in removing the need for GC through smarter compilers and through languages that allow us to better express our intent - and our object graph. Instead, we continue to improve on a giant linked-list traversal through all of live memory to try and infer the object graph at runtime. Without sufficient information to do it efficiently. The fundamental issue is that we don't have languages that express our goals in a way that allows memory management to be elided efficiently. That doesn't mean I have some particular affinity for reference counting, though. It has its own issues as you rightly point out. I prefer it for its determinism, nothing more.
- kaba0 4y ago
  But reference counting is a GC-algorithm -- that does exactly the same thing: tries to infer the object graph at runtime. I really don't think it is a language problem, for several algorithms that one may want to write, GC is a necessity as object lifetime is not decidable at compile time. And it's not just some special parallel algorithm, I believe most business problems fall into this category - that's why we have basically "hacks" like RC, shared ptr, etc in low level languages to let us fake a partial GC (not collecting cycles). On the plus side of GC, it has been one of the biggest productivity boosters the field has seen since the first non-assembly PL.
  - eru 4y ago
    I wouldn't call reference counting a hack. The paper mention elsewhere in the comments, https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-garbage.pdf https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-... "A Unifying Theory of Garbage Collection" put this in context. For example, a generational garbage collection essentially employs a hybrid approach between tracing and reference counting. Similarly, depending on your system's trade-offs, reference counting might be better. Eg tracing garbage collection works really great for main memory, but for filesystems we typically use reference counting to decide whether to retire an inode. (The paper explains this in more detail.)

tsimionescu 4y ago

> RC limits itself to modifying only relevant objects, whereas GC reads all objects in a super cache-unfriendly way. Yes, an atomic read-modify-write is worse than a read, but it's not worse than a linked-list traversal of all of memory all the time. All tracing GC algorithms scan only live memory, and they typically do so in an array-like scan (writing some bits in the object header when a pointer to that object is discovered), not in linked-list order.

int_19h 4y ago

Most GC implementations that I can think of know which bits in memory are pointers and which aren't, and only scan the pointers.

bitcharmer 4y ago

> RC may turn reads into writes, but of course, GC ends up having to go through literally every piece of memory ever from bottom to top once in a while. > RC limits itself to modifying only relevant objects, whereas GC reads all objects in a super cache-unfriendly way. Yes, an atomic read-modify-write is worse than a read, but it's not worse than a linked-list traversal of all of memory all the time. This is patently untrue. Contemporary GCs have had card marking/scanning for 10+ years now.

garethrowlands 4y ago

Pointer chasing is expensive because fetching a random location defeats locality and therefore caches the the CPU's stream detection. But a compacting GC copies the data it's scanned into a contiguous stream, dramatically improving locality, cache utility and stream detection. And this affects not only subsequent GCs but also the application itself, which may traverse its object graph far more often than the GC does.