7 ms·

> 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. C

by wgd 4y 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 4y 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 4y 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 4y ago
    Often it is your SRE who has to do that work.
pkolaczk 4y 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 4y ago
  Java’s ZGC has a constant (O(1)) sub-milliaecond pause-time. GC runs concurrently with the app
  - pkolaczk 4y ago
    Yeah, according to the paper you pay for it by a very high overhead, up to 2x. So generally, pick your poison ;)
    - Skinney 4y 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 4y 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 4y 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 4y 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 4y 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 4y 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.
      - 4y ago
gwbas1c 4y 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.)

by wgd 4y ago

ncmncm 4y 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 4y 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 4y ago
  Often it is your SRE who has to do that work.

pkolaczk 4y 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 4y ago
Java’s ZGC has a constant (O(1)) sub-milliaecond pause-time. GC runs concurrently with the app
- pkolaczk 4y ago
  Yeah, according to the paper you pay for it by a very high overhead, up to 2x. So generally, pick your poison ;)
  - Skinney 4y 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 4y 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 4y 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 4y 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 4y 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 4y 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.
    - 4y ago

gwbas1c 4y 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.)