4 ms·

The way you make garbage collection deterministic is not by doing regions but by making it concurrent. That’s increasingly common, though fully concurrent GCs a

The way you make garbage collection deterministic is not by doing regions but by making it concurrent. That’s increasingly common, though fully concurrent GCs are not as common as “sorta concurrent” ones because there is a throughput hit to going fully concurrent (albeit probably a smaller one than if you partitioned your heap as the article suggests). Also, no point in calling it “tracing garbage collection”. Its just “garbage collection”. If you’re garbage collecting, you’re tracing.

jakewins 2y ago
Do you have any recommended reading material on this? Intuitively it feels like making it concurrent should do the opposite of making GC deterministic! I’d love to read something showing that intuition is wrong
- pizlonator 2y ago
  Garbage collection handbook https://gchandbook.org/ https://gchandbook.org/ If you want to see my latest concurrent GC, see https://github.com/pizlonator/llvm-project-deluge/blob/deluge/Manifesto.md https://github.com/pizlonator/llvm-project-deluge/blob/delug... https://github.com/pizlonator/llvm-project-deluge/blob/deluge/libpas/src/libpas/fugc.c https://github.com/pizlonator/llvm-project-deluge/blob/delug...
azornathogron 2y ago
Using concurrent GC has various advantages but in no way makes it deterministic.
- pizlonator 2y ago
  True, not by itself. But concurrent GC is the basis for making deterministic GC, since it gives you the option of scheduling GC work whenever you like rather than pausing the world. Some concurrent GCs are also deterministic while others aren’t. I’ve written both kinds.
  - gpderetta 2y ago
    you have some very non-standard definition of determinism.
    - pizlonator 2y ago
      How so?
roetlich 2y ago
> Also, no point in calling it “tracing garbage collection”. You're against more explicit naming just for the sake of it? In the literature reference counting is also referred to as a type of garbage collection, and doesn't involve tracing. If you talking about a specific context you can probably drop the "tracing", but in a general article like this it would just be very confusing? This way, someone can google "tracing garbage collection", and will find the relevant wikipedia article: https://en.wikipedia.org/wiki/Tracing_garbage_collection https://en.wikipedia.org/wiki/Tracing_garbage_collection
- pizlonator 2y ago
  The literature does not always put the “tracing” in front of the “garbage collection”. For example, nobody says that Objective-C is garbage collected just because it has ARC. Nobody says that C++ is garbage collected even though shared_ptr is widespread. And systems that do tracing GC just call it GC (see for example https://www.oracle.com/webfolder/technetwork/tutorials/obe/java/gc01/index.html https://www.oracle.com/webfolder/technetwork/tutorials/obe/j...) To think clearly about the tradeoff between GC and RC it’s important to acknowledge the semantic differences: - GC definitely collects dead cycles. - RC knows exactly when objects die, which allows for sensible destructor semantics and things like CoW. - it’s possible to use RC as an optimization in a GC, but then you end up with GC semantics and you still have tracing (hence: if it’s got tracing, it’s a garbage collector). It’s a recent fad to say that RC is a kind of GC, but I don’t think it ever took off outside academia. Folks who write GCs call them GCs. Folks who do shared_ptr or ARC say that they don’t use GC. And its good if this fad dies because saying that RC is a kind of GC causes folks to overlook the massive semantic elephant in the room: if you use a GC then you can’t swap it for RC because you’d leak memory (RC would fail to delete cycles), and if you use RC and swap it for a GC then you’d leak resources (your destructors would no longer get called when you expect them to). On the other hand, it is possible to change the guts of an RC impl without anyone noticing. And it’s possible to change the guts of a GC while preserving compatibility. So these are really two different worlds.
  - roetlich 2y ago
    > The literature does not always put the “tracing” in front of the “garbage collection”. Not always, but often enough that an introductory article that presents an overview of different memory managment techniques should maybe use the longer name to avoid confusion. And I kinda agree with you, using the name "garbage collection" for RC doesn't really make sense, there is no metaphorical garbage truck driving around to collect your unused memory. :) What's your opinion on the term "RC with cycle detection" that some use for things like Python's GC? > And it’s possible to change the guts of a GC while preserving compatibility. Moving to a conservative GC might also introduce memory leaks, if you're unlucky. But yes, "tracing" gc and rc obeviously behave very differently, and have very different performance considerations.

jakewins 2y ago

Do you have any recommended reading material on this? Intuitively it feels like making it concurrent should do the opposite of making GC deterministic! I’d love to read something showing that intuition is wrong

pizlonator 2y ago
Garbage collection handbook https://gchandbook.org/ https://gchandbook.org/ If you want to see my latest concurrent GC, see https://github.com/pizlonator/llvm-project-deluge/blob/deluge/Manifesto.md https://github.com/pizlonator/llvm-project-deluge/blob/delug... https://github.com/pizlonator/llvm-project-deluge/blob/deluge/libpas/src/libpas/fugc.c https://github.com/pizlonator/llvm-project-deluge/blob/delug...

azornathogron 2y ago

Using concurrent GC has various advantages but in no way makes it deterministic.

pizlonator 2y ago
True, not by itself. But concurrent GC is the basis for making deterministic GC, since it gives you the option of scheduling GC work whenever you like rather than pausing the world. Some concurrent GCs are also deterministic while others aren’t. I’ve written both kinds.
- gpderetta 2y ago
  you have some very non-standard definition of determinism.
  - pizlonator 2y ago
    How so?

roetlich 2y ago

> Also, no point in calling it “tracing garbage collection”. You're against more explicit naming just for the sake of it? In the literature reference counting is also referred to as a type of garbage collection, and doesn't involve tracing. If you talking about a specific context you can probably drop the "tracing", but in a general article like this it would just be very confusing? This way, someone can google "tracing garbage collection", and will find the relevant wikipedia article: https://en.wikipedia.org/wiki/Tracing_garbage_collection https://en.wikipedia.org/wiki/Tracing_garbage_collection

pizlonator 2y ago
The literature does not always put the “tracing” in front of the “garbage collection”. For example, nobody says that Objective-C is garbage collected just because it has ARC. Nobody says that C++ is garbage collected even though shared_ptr is widespread. And systems that do tracing GC just call it GC (see for example https://www.oracle.com/webfolder/technetwork/tutorials/obe/java/gc01/index.html https://www.oracle.com/webfolder/technetwork/tutorials/obe/j...) To think clearly about the tradeoff between GC and RC it’s important to acknowledge the semantic differences: - GC definitely collects dead cycles. - RC knows exactly when objects die, which allows for sensible destructor semantics and things like CoW. - it’s possible to use RC as an optimization in a GC, but then you end up with GC semantics and you still have tracing (hence: if it’s got tracing, it’s a garbage collector). It’s a recent fad to say that RC is a kind of GC, but I don’t think it ever took off outside academia. Folks who write GCs call them GCs. Folks who do shared_ptr or ARC say that they don’t use GC. And its good if this fad dies because saying that RC is a kind of GC causes folks to overlook the massive semantic elephant in the room: if you use a GC then you can’t swap it for RC because you’d leak memory (RC would fail to delete cycles), and if you use RC and swap it for a GC then you’d leak resources (your destructors would no longer get called when you expect them to). On the other hand, it is possible to change the guts of an RC impl without anyone noticing. And it’s possible to change the guts of a GC while preserving compatibility. So these are really two different worlds.
- roetlich 2y ago
  > The literature does not always put the “tracing” in front of the “garbage collection”. Not always, but often enough that an introductory article that presents an overview of different memory managment techniques should maybe use the longer name to avoid confusion. And I kinda agree with you, using the name "garbage collection" for RC doesn't really make sense, there is no metaphorical garbage truck driving around to collect your unused memory. :) What's your opinion on the term "RC with cycle detection" that some use for things like Python's GC? > And it’s possible to change the guts of a GC while preserving compatibility. Moving to a conservative GC might also introduce memory leaks, if you're unlucky. But yes, "tracing" gc and rc obeviously behave very differently, and have very different performance considerations.