8 ms·

No, it's not. Garbage collection and reference counting are "automatic memory management." With reference counting there are no pauses, and memory is reclaimed

No, it's not. Garbage collection and reference counting are "automatic memory management." With reference counting there are no pauses, and memory is reclaimed immediately. It allows for strongly coupling deallocation with resource cleanup. (The consequence is higher overhead maintaining counts, and leaked reference cycles.) In a garbage collected language you need to explicitly release your resources. (IE, the Dispose pattern that's common in C#)

Sindisil 5y ago
[citation needed] Reference counting is widely considered one strategy of garbage collection (https://en.wikipedia.org/wiki/Garbage_collection_(computer_science) https://en.wikipedia.org/wiki/Garbage_collection_(computer_s...). For that matter, some GCs that are primarily tracing also use ref counts for some portion of the heap, as an optimization (just as some primarily refcounting GCs also run a trace to clean up cycles). Also, reference counting can certainly result in pauses, when large graphs of interconnected objects are reclaimed. On the upside, you know when a pause might happen. You still don't know for certain without explicitly keeping track of what is about to be freed, which would add additional overhead, and indeed may not be practical or even feasible.
wgd 5y ago
> With reference counting there are no pauses, and memory is reclaimed immediately You can't guarantee both of these properties at once, in the general case. Consider a very large tree of objects which are referenced through a single root node, and then that root node becomes eligible for reclamation. For a sufficiently large object graph, either reclamation will require a noticeable pause or some portion of the work will have to be deferred until later.
- ncmncm 5y ago
  In such uses, if it matters you don't rely on RC to reclaim the storage. You allocate from an arena, and drop the whole graph as a unit. Using pointers to make up a graph is a choice. It is a thing taught in CS classes, so it may feel comfortably familiar; that does not make it good. I never do.
  - ahtihn 5y ago
    How is this different than working around a GC? There are lots of things you can do in GCed language to avoid allocations and avoid running the GC when it matters.
    - ncmncm 5y ago
      Often it is your SRE who has to do that work.
- pkolaczk 5y ago
  There is a difference between pausing a single thread in a known, predictable point and pausing all threads at random point in time. Tracing GCs do the latter. It is way easier to avoid long pauses with recounting than with tracing GC.
  - Skinney 5y ago
    Java’s ZGC has a constant (O(1)) sub-milliaecond pause-time. GC runs concurrently with the app
    - pkolaczk 5y ago
      Yeah, according to the paper you pay for it by a very high overhead, up to 2x. So generally, pick your poison ;)
      - Skinney 5y ago
        Exactly. But the thing is, I can switch GC implementation according to my needs. If throughput is my number 1 concern I can use ParalellGC, if not I can use ZGC. Or G1 if I want something in between (not sure if the paper picks up the huge drop in overhead of G1 in Java 18).
        pkolaczk 5y ago
        You can switch the GC implementation only globally. In languages like C++ or Rust you can have different parts of program using different memory management strategy, from carefully hand-crafted region allocation through refcounting to even tracing GC (rarely needed though).
- kragen 5y ago
  You may be able to guarantee it in this particular case with region-based allocation (also called arena allocation); discarding a region, or resetting its allocation pointer back to the beginning, is a constant-time operation. If your very large tree is in a single region, and it's the only thing in that region, then you can reclaim the entire thing in constant time as soon as you no longer need it. Region-based memory management is commonly used, for example, with per-frame heaps in games, or per-request heaps in servers; but in those cases memory is not reclaimed immediately. The MLKit implements Standard ML with regions instead of garbage collection, though recent versions also have GC.
  - native_samples 5y ago
    That only works if you are able to prove none of your objects do anything in their destructors. In practice, manually memory managed languages always conflate memory and other resources. A File object is not just a block of memory, it's also a file descriptor, etc. So you have to run the destructors at the 'right' times and can't just toss the memory. In special cases where you control every allocation, sure, but often that isn't practical.
    - kragen 5y ago
      It's true that this solution doesn't apply when you have finalizers, but I think of that as the unusual case, not the usual one. I don't understand what you mean by "special cases where you control every allocation"; how are things getting allocated in your arena without you controlling them? Who is "you" if not the author of the program, who controls everything in it?
      - native_samples 5y ago
        Libraries. If your libraries can't do that because you wrote your own malloc to get this arena allocation, it's because your strategy isn't general and will break the moment you want to use libraries that allocate.
        5y ago
- gwbas1c 5y ago
  > Consider a very large tree of objects which are referenced through a single root node That's predictable and can be planned for: You can hold onto the reference until you get to a point where the pause is acceptable. You can't do that in a garbage collected language, because you have no control over when the garbage collector will pause. (In theory your application can explicitly trigger a garbage collection, but in practice such behavior is discouraged.)
pjmlp 5y ago
I advise reading a couple of CS books on the subject.
chrisseaton 5y ago
> With reference counting there are no pauses How are you reclaiming cycles with no pauses?
- ncmncm 5y ago
  I have had no occasion in the past three decades to make cycles. It smacks of poor discipline, or poor design.
  - deathanatos 5y ago
    While I also haven't ever had a cycle in my decades as an engineer, it doesn't really answer the parent's question about pauses w.r.t. ref counting. Ref counting, in the general, isn't free. (Also, in the sense of releasing a cycle, that would be pretty quick, since a typical RC implementation is just going to leak it. Its where a large graph resource graph is successfully ref-counted to 0 that can cause a pause, theoretically, although that's another case I've not seen.)
    - ncmncm 5y ago
      The usual method is to have strategically placed "weak" references.
      - deathanatos 5y ago
        … yes (and I know), but that has nothing to do with the point being made here, which is about the compute time required to manage the memory.
  - chrisseaton 5y ago
    Well good for you I guess - but that’s not a general solution for language implementation as it’s not sound for a language like Python. Which is why in practice most RCs include tracing. And the reverse as well - most tracers include a degree of RC. That’s the pragmatic solution in practice.
colejohnson66 5y ago
> With reference counting there are no pauses... Same with GC. "Stop the world" may be a characteristic of a simple GC, but it's entirely possible to have GC that works by "coloring" objects. > In a garbage collected language you need to explicitly release your resources. (IE, the Dispose pattern that's common in C#) You only need to implement IDisposable if you are dealing with unmanaged resources (ie. non-GC objects). But it's the same with C/C++: you have to call `free()` or `delete`; The difference is that managed resources are auto-released for you.
munificent 5y ago
These days, "garbage collection" is the umbrella term that includes ref counting and other forms. "Tracing garbage collection" the term for GC that doesn't include ref counting. > With reference counting there are no pauses You can still have pauses of arbitrary duration with ref counting. When the last reference to an object that is the sole owner of a large graph of other objects gets decremented, the entire object graph must be immediately deallocated. It's possible for a single dereference to trigger an unbounded amount of deallocation. > and memory is reclaimed immediately. Most production-quality ref counting implementations defer tracking references on the stack to minimize ref count churn. That significantly improves performance but it means you can no longer claim that the system always reclaims memory "immediately". > In a garbage collected language you need to explicitly release your resources. (IE, the Dispose pattern that's common in C#) Managing non-memory resources is orthogonal to tracing versus ref counting. If you choose to tie a resource's lifetime to a piece of memory's lifetime then, yes, the memory manager's deallocation policy becomes user-visible. I think you would get a lot out of reading "A Unified Theory of Garbage Collection".
- SomeCallMeTim 5y ago
  > When the last reference to an object that is the sole owner of a large graph of other objects gets decremented, the entire object graph must be immediately deallocated. It's possible for a single dereference to trigger an unbounded amount of deallocation. Two things: 1. Unbounded may be technically true, but it's really not a hard problem to ensure that time-critical runtime deallocations either rarely happen or are simply never huge chains of objects that release each other. Source: Used C++ & boost::shared_ptr/boost::weak_ptr extensively in game development and never had unexpected jank due to deallocations. 2. There's no actual reason that the full deallocation needs to happen immediately in all reference counting implementations. If you have hard time or latency constraints you could queue up the actual dereferencing and ensure that you only dereference a certain number of objects per time period. Yes, #2 changes some assumptions about when objects will be dereferenced; in C++ one might rely on guarantees that objects are immediately released along with associated resources. But if you go into a project knowing that it needed to support deferred reference counting, manually releasing critical resources is hardly the worst thing you'd need to do.
spullara 5y ago
Reference counting absolutely has pauses. Try allocating millions of objects in a block and then exiting that block. Hell, even malloc pauses when fragmentation gets too high.
- mirekrusin 5y ago
  I'll show in profiler straight away. With tracing gc it won't.
  - spullara 5y ago
    What do you think won't show up in a profiler with GC? With the right profiler I can see the entire heap as well as where every object was allocated and all those deallocations are basically free. With a modern collector like ZGC, max pause times are now sub-millisecond for collections. Also easy to measure the total GC cost in the profiler as well. The modern GC story is extremely good. The biggest issue with GC in my opinion is that it uses more memory than you strictly need.
    - mirekrusin 5y ago
      It won't show what we're talking about in this thread - deallocations of large number of allocations when they loose last root reference at once.
      - spullara 5y ago
        It absolutely will show them because they cost nothing. 0 will show up in the profiler which is how much deallocations cost with GC.
        mirekrusin 5y ago
        Magic. In rc/arc you can achieve the same by making release a no-op.
        5y ago
pron 5y ago
Reference counting and tracing are the two main approaches for garbage collection. See, for example, https://courses.cs.washington.edu/courses/cse590p/05au/p50-bacon.pdf https://courses.cs.washington.edu/courses/cse590p/05au/p50-b... While tracing is considered to have better throughput and reference counting to have a lower footprint, as the liked paper shows, they are really on a spectrum of techniques with different tradeoffs.
throwaway894345 5y ago
> No, it's not. Garbage collection and reference counting are "automatic memory management. In strict computer science parlance, refcounting is a kind of GC, but to most people GC refers to "tracing GC" specifically. It's fairly pedantic. > In a garbage collected language you need to explicitly release your resources. I assume "resources" here must mean "non-memory resources"? Even still, GC can apply to any kind of resource, it's just most popularly applied to memory (you could have a GC for file handles, for example). Also, so you know, the user you're replying to knows a thing or two about programming languages.

Sindisil 5y ago

[citation needed] Reference counting is widely considered one strategy of garbage collection (https://en.wikipedia.org/wiki/Garbage_collection_(computer_science) https://en.wikipedia.org/wiki/Garbage_collection_(computer_s...). For that matter, some GCs that are primarily tracing also use ref counts for some portion of the heap, as an optimization (just as some primarily refcounting GCs also run a trace to clean up cycles). Also, reference counting can certainly result in pauses, when large graphs of interconnected objects are reclaimed. On the upside, you know when a pause might happen. You still don't know for certain without explicitly keeping track of what is about to be freed, which would add additional overhead, and indeed may not be practical or even feasible.

wgd 5y ago

> With reference counting there are no pauses, and memory is reclaimed immediately You can't guarantee both of these properties at once, in the general case. Consider a very large tree of objects which are referenced through a single root node, and then that root node becomes eligible for reclamation. For a sufficiently large object graph, either reclamation will require a noticeable pause or some portion of the work will have to be deferred until later.

ncmncm 5y ago
In such uses, if it matters you don't rely on RC to reclaim the storage. You allocate from an arena, and drop the whole graph as a unit. Using pointers to make up a graph is a choice. It is a thing taught in CS classes, so it may feel comfortably familiar; that does not make it good. I never do.
- ahtihn 5y ago
  How is this different than working around a GC? There are lots of things you can do in GCed language to avoid allocations and avoid running the GC when it matters.
  - ncmncm 5y ago
    Often it is your SRE who has to do that work.
pkolaczk 5y ago
There is a difference between pausing a single thread in a known, predictable point and pausing all threads at random point in time. Tracing GCs do the latter. It is way easier to avoid long pauses with recounting than with tracing GC.
- Skinney 5y ago
  Java’s ZGC has a constant (O(1)) sub-milliaecond pause-time. GC runs concurrently with the app
  - pkolaczk 5y ago
    Yeah, according to the paper you pay for it by a very high overhead, up to 2x. So generally, pick your poison ;)
    - Skinney 5y ago
      Exactly. But the thing is, I can switch GC implementation according to my needs. If throughput is my number 1 concern I can use ParalellGC, if not I can use ZGC. Or G1 if I want something in between (not sure if the paper picks up the huge drop in overhead of G1 in Java 18).
      - pkolaczk 5y ago
        You can switch the GC implementation only globally. In languages like C++ or Rust you can have different parts of program using different memory management strategy, from carefully hand-crafted region allocation through refcounting to even tracing GC (rarely needed though).
kragen 5y ago
You may be able to guarantee it in this particular case with region-based allocation (also called arena allocation); discarding a region, or resetting its allocation pointer back to the beginning, is a constant-time operation. If your very large tree is in a single region, and it's the only thing in that region, then you can reclaim the entire thing in constant time as soon as you no longer need it. Region-based memory management is commonly used, for example, with per-frame heaps in games, or per-request heaps in servers; but in those cases memory is not reclaimed immediately. The MLKit implements Standard ML with regions instead of garbage collection, though recent versions also have GC.
- native_samples 5y ago
  That only works if you are able to prove none of your objects do anything in their destructors. In practice, manually memory managed languages always conflate memory and other resources. A File object is not just a block of memory, it's also a file descriptor, etc. So you have to run the destructors at the 'right' times and can't just toss the memory. In special cases where you control every allocation, sure, but often that isn't practical.
  - kragen 5y ago
    It's true that this solution doesn't apply when you have finalizers, but I think of that as the unusual case, not the usual one. I don't understand what you mean by "special cases where you control every allocation"; how are things getting allocated in your arena without you controlling them? Who is "you" if not the author of the program, who controls everything in it?
    - native_samples 5y ago
      Libraries. If your libraries can't do that because you wrote your own malloc to get this arena allocation, it's because your strategy isn't general and will break the moment you want to use libraries that allocate.
      - 5y ago
gwbas1c 5y ago
> Consider a very large tree of objects which are referenced through a single root node That's predictable and can be planned for: You can hold onto the reference until you get to a point where the pause is acceptable. You can't do that in a garbage collected language, because you have no control over when the garbage collector will pause. (In theory your application can explicitly trigger a garbage collection, but in practice such behavior is discouraged.)

pjmlp 5y ago

I advise reading a couple of CS books on the subject.

chrisseaton 5y ago

> With reference counting there are no pauses How are you reclaiming cycles with no pauses?

ncmncm 5y ago
I have had no occasion in the past three decades to make cycles. It smacks of poor discipline, or poor design.
- deathanatos 5y ago
  While I also haven't ever had a cycle in my decades as an engineer, it doesn't really answer the parent's question about pauses w.r.t. ref counting. Ref counting, in the general, isn't free. (Also, in the sense of releasing a cycle, that would be pretty quick, since a typical RC implementation is just going to leak it. Its where a large graph resource graph is successfully ref-counted to 0 that can cause a pause, theoretically, although that's another case I've not seen.)
  - ncmncm 5y ago
    The usual method is to have strategically placed "weak" references.
    - deathanatos 5y ago
      … yes (and I know), but that has nothing to do with the point being made here, which is about the compute time required to manage the memory.
- chrisseaton 5y ago
  Well good for you I guess - but that’s not a general solution for language implementation as it’s not sound for a language like Python. Which is why in practice most RCs include tracing. And the reverse as well - most tracers include a degree of RC. That’s the pragmatic solution in practice.

colejohnson66 5y ago

> With reference counting there are no pauses... Same with GC. "Stop the world" may be a characteristic of a simple GC, but it's entirely possible to have GC that works by "coloring" objects. > In a garbage collected language you need to explicitly release your resources. (IE, the Dispose pattern that's common in C#) You only need to implement IDisposable if you are dealing with unmanaged resources (ie. non-GC objects). But it's the same with C/C++: you have to call `free()` or `delete`; The difference is that managed resources are auto-released for you.

munificent 5y ago

These days, "garbage collection" is the umbrella term that includes ref counting and other forms. "Tracing garbage collection" the term for GC that doesn't include ref counting. > With reference counting there are no pauses You can still have pauses of arbitrary duration with ref counting. When the last reference to an object that is the sole owner of a large graph of other objects gets decremented, the entire object graph must be immediately deallocated. It's possible for a single dereference to trigger an unbounded amount of deallocation. > and memory is reclaimed immediately. Most production-quality ref counting implementations defer tracking references on the stack to minimize ref count churn. That significantly improves performance but it means you can no longer claim that the system always reclaims memory "immediately". > In a garbage collected language you need to explicitly release your resources. (IE, the Dispose pattern that's common in C#) Managing non-memory resources is orthogonal to tracing versus ref counting. If you choose to tie a resource's lifetime to a piece of memory's lifetime then, yes, the memory manager's deallocation policy becomes user-visible. I think you would get a lot out of reading "A Unified Theory of Garbage Collection".

SomeCallMeTim 5y ago
> When the last reference to an object that is the sole owner of a large graph of other objects gets decremented, the entire object graph must be immediately deallocated. It's possible for a single dereference to trigger an unbounded amount of deallocation. Two things: 1. Unbounded may be technically true, but it's really not a hard problem to ensure that time-critical runtime deallocations either rarely happen or are simply never huge chains of objects that release each other. Source: Used C++ & boost::shared_ptr/boost::weak_ptr extensively in game development and never had unexpected jank due to deallocations. 2. There's no actual reason that the full deallocation needs to happen immediately in all reference counting implementations. If you have hard time or latency constraints you could queue up the actual dereferencing and ensure that you only dereference a certain number of objects per time period. Yes, #2 changes some assumptions about when objects will be dereferenced; in C++ one might rely on guarantees that objects are immediately released along with associated resources. But if you go into a project knowing that it needed to support deferred reference counting, manually releasing critical resources is hardly the worst thing you'd need to do.

spullara 5y ago

Reference counting absolutely has pauses. Try allocating millions of objects in a block and then exiting that block. Hell, even malloc pauses when fragmentation gets too high.

mirekrusin 5y ago
I'll show in profiler straight away. With tracing gc it won't.
- spullara 5y ago
  What do you think won't show up in a profiler with GC? With the right profiler I can see the entire heap as well as where every object was allocated and all those deallocations are basically free. With a modern collector like ZGC, max pause times are now sub-millisecond for collections. Also easy to measure the total GC cost in the profiler as well. The modern GC story is extremely good. The biggest issue with GC in my opinion is that it uses more memory than you strictly need.
  - mirekrusin 5y ago
    It won't show what we're talking about in this thread - deallocations of large number of allocations when they loose last root reference at once.
    - spullara 5y ago
      It absolutely will show them because they cost nothing. 0 will show up in the profiler which is how much deallocations cost with GC.
      - mirekrusin 5y ago
        Magic. In rc/arc you can achieve the same by making release a no-op.
        5y ago

pron 5y ago

Reference counting and tracing are the two main approaches for garbage collection. See, for example, https://courses.cs.washington.edu/courses/cse590p/05au/p50-bacon.pdf https://courses.cs.washington.edu/courses/cse590p/05au/p50-b... While tracing is considered to have better throughput and reference counting to have a lower footprint, as the liked paper shows, they are really on a spectrum of techniques with different tradeoffs.

throwaway894345 5y ago

> No, it's not. Garbage collection and reference counting are "automatic memory management. In strict computer science parlance, refcounting is a kind of GC, but to most people GC refers to "tracing GC" specifically. It's fairly pedantic. > In a garbage collected language you need to explicitly release your resources. I assume "resources" here must mean "non-memory resources"? Even still, GC can apply to any kind of resource, it's just most popularly applied to memory (you could have a GC for file handles, for example). Also, so you know, the user you're replying to knows a thing or two about programming languages.