5 ms·

Always remember: a garbage collector is a theorem prover that proves that objects are unreachable, over and over, so that they can be destroyed. It is in gener

Always remember: a garbage collector is a theorem prover that proves that objects are unreachable, over and over, so that they can be destroyed. It is in general undecidable whether an object is unreachable, but we can get good performance with heuristics.

convolvatron 3y ago
I'm not sure this is right. the classic gc approach is dynamic, not static, and it discovers the reachable set, not the unreachable one. please elaborate?
- Filligree 3y ago
  There's garbage collection algorithms that do one, the other, or a combination. It depends mostly on what constraints you have, though yes, high-performance GC mostly looks for the reachable set.
KRAKRISMOTT 3y ago
Why is it undecidable? Is it not just a graph traversal/coloring problem?
- zer8k 3y ago
  To put it simply it's very difficult to determine what objects (in the C term) are garbage. Hence why we have things like reference counting. We need extra data to hint to the collector what is, in fact, garbage.
  - bruce343434 3y ago
    Okay, so you need to set up some scaffolding/bookkeep some metadata. Still not impossible.
    - papruapap 3y ago
      No an expert, but afaik the problem is not the complexity but the performance cost.
      - robertlagrant 3y ago
        Sure, but that's not "undecidable"?
        hypertele-Xii 3y ago
        Technically the halting problem is a performance cost issue, because you can always tell whether a program stops by just running it. The performance cost is having to actually run it and wait and see, rather than find some quicker way to the answer.
        myk9001 3y ago
        I don't think it can be boiled down to a performance cost issue. If a program is going to run forever, how do you measure the forever has passed to conclude the program doesn't halt?
        hypertele-Xii 3y ago
        By waiting forever. I understand that "forever" is a nebulous term, but it works both ways. We both know that no computer program could actually run forever.
        myk9001 3y ago
        > I understand that "forever" is a nebulous term, but it works both ways. So, at what point in time the person who is observing a running program is going to declare it doesn't halt? What if they conclude the program doesn't halt, just for it to actually complete execution the very next second? In practical terms, that's why we have timeouts. And in some cases relying on a reasonable timeout is fundamentally the best we can do -- exactly because we can't deterministically answer if a program ever halts. > We both know that no computer program could actually run forever. No program can actually run forever, of course. But any program will stop eventually due to external factors -- me hitting Ctrl + C or pulling the power plug or whatever. The halting problem asks whether it's possible to tell if a program will ever stop or not according to its internal logic. Here's a (likely dumb) analogy off the top of my head regarding a program stopping due to external reasons. Imagine, I toss a coin, lightning strikes and evaporates the coin while its midair. Do I get to say it was heads or tails? Guess, it's impossible to claim either way.
  - tylerhou 3y ago
    If you define garbage in the conventional way — “objects that can never be reached from any GC roots” — determining what objects are garbage only takes linear time (tracing)… Reference counting helps the tracing phase out by pruning objects that are clearly garbage early — if a refcount hits zero, that object can clearly be deallocated safely. The converse is not true, which is why we need tracing.
- fweimer 3y ago
  The case that arises quite often in practice is when a reference is retained, but can only be used on an error path (e.g., as part of an exception). The error condition may not ever happen due to the way to code is written, but it's unlikely the garbage collector can prove that except in the simplest possible cases. Usually, it is acceptable to do a conservative approximation of the actual lifetime, and blame space leaks on the programmer. Garbage collectors usually also make assumptions in the other direction (a non-conservative approximation) when it comes to finalizable resources (e.g., file descriptors). These uses do not involve the reference that is visible to the collector. This gives us Reference.reachabilityFence(), and again mistakes are blamed on the programmer.
raincole 3y ago
It's not. You're describing a static analyzer that inserts free() automatically. Not GC. GC is pretty much the opposite. Edit: Well, I didn't think it through. You're correct. A "perfect GC" is indeed undecidable, and all the real world, practical GC have "false positive" (a piece of memory is no longer used by the code, but there is no way to know it). A perfect GC without false positive is equal to halting problem. Example: var obj = new Object(); // === real code begin ... 50 lines of real code that never uses obj if (something == true) return; ... another 50 lines of real code that never uses obj // === real code end obj.doThings(); A perfect GC can release obj while the real code is running. A real world, imperfect GC can't, since whether the real code returns early or not is undecidable.
- lisper 3y ago
  > You're correct. No, s/he's not. The original claim was: > It is in general undecidable whether an object is UNREACHABLE. [Emphasis added] Being unreachable is not the same thing as being "no longer used by the code". The latter is indeed undecidable, but the former is not.
- chubot 3y ago
  After writing a garbage collector, I can say that I’ve seen the unreachable / “will never be used” distinction, and it’s more or less irrelevant trivia. It doesn’t help you write a garbage collector to think of it that way. It doesn’t provide insight into the problem. The problems are elsewhere. Focus on reachability, dynamic understanding of the heap, performance, etc.
  - nomel 3y ago
    > more or less irrelevant trivia What are some cases? The only I can think of is if a "remote" thing owned the memory. For example, if I sent a pointer elsewhere, then reused it later. Like, maybe with a device driver, or library.
- monocasa 3y ago
  You normally fix that not with the GC itself, but with the compiler. If new Object() truly doesn't have any effects visible other than the valid reference, then it's creation can be moved to after the if statement.
aatd86 3y ago
I'll join the others in trying to bring up a nuance. The issue is not necessarily unreachability being undecidable. The issue is that reachability depends on control flow. And that implies being conservative which translates into having to deal with false positives. That static analysis in a nutshell: how to get precision and soundness. Probably a mere question of terminology.
deleted 3y ago
[deleted]
3cats-in-a-coat 3y ago
Empirically what you say can't be the case, because if it's "undecidable" then one of these must be true: 1. The GC frees objects that could be reachable (program gets corrupted in spectacular ways). 2. The GC never frees anything (as it can't decide). The GC may not dispose of objects immediately, but when it determines they're not reachable, they're not reachable, period. There's nothing undecidable about it.
- hashmash 3y ago
  It's undecidable when you consider the possibility that the program won't ever attempt to access an object. A tracing collector plays it safe and assumes such objects might still be accessed at some point. In GC languages you'll often see deliberate null assignments in order to allow the collector to clean up objects sooner.
  - 3cats-in-a-coat 3y ago
    Reachable/accessible and reached/accessed are different things, why are we talking about it as if it's the same thing? One is a potential eventuality, the other is an event. GC are concerned with the potential eventuality, which is 100% decidable, not with the latter, that was never under discussion. To say "reachability is undecidable" means you can't decide whether you MAY or MAY NOT reach it. Which is wrong. You can decide whether you MAY or MAY NOT reach it. And if you MAY NOT... then that's 100% unreachable and safe to collect.
munificent 3y ago
It's easily decidable whether a given GC object could be reached. What isn't decidable is whether a it will be used in the future. The conservative approximation that GC's make is that they keep all objects that could be accessed in the future by the program (reach-able) instead of only keeping the objects that will be used in the future. A trivial example is: void main() { var obj = new Object(); while (true) { // Do other work... if (dayOfWeek == 9) { print(obj); } } } Since there are only seven days in the week, that `print()` statement will never be reached, and an optimal GC would free obj. But the GC can't determine that. All it knows is that it could possibly be reached, so the object stays in memory.
- cozzyd 3y ago
  https://en.wikipedia.org/wiki/French_Republican_calendar https://en.wikipedia.org/wiki/French_Republican_calendar

convolvatron 3y ago

I'm not sure this is right. the classic gc approach is dynamic, not static, and it discovers the reachable set, not the unreachable one. please elaborate?

Filligree 3y ago
There's garbage collection algorithms that do one, the other, or a combination. It depends mostly on what constraints you have, though yes, high-performance GC mostly looks for the reachable set.

KRAKRISMOTT 3y ago

Why is it undecidable? Is it not just a graph traversal/coloring problem?

zer8k 3y ago
To put it simply it's very difficult to determine what objects (in the C term) are garbage. Hence why we have things like reference counting. We need extra data to hint to the collector what is, in fact, garbage.
- bruce343434 3y ago
  Okay, so you need to set up some scaffolding/bookkeep some metadata. Still not impossible.
  - papruapap 3y ago
    No an expert, but afaik the problem is not the complexity but the performance cost.
    - robertlagrant 3y ago
      Sure, but that's not "undecidable"?
      - hypertele-Xii 3y ago
        Technically the halting problem is a performance cost issue, because you can always tell whether a program stops by just running it. The performance cost is having to actually run it and wait and see, rather than find some quicker way to the answer.
        myk9001 3y ago
        I don't think it can be boiled down to a performance cost issue. If a program is going to run forever, how do you measure the forever has passed to conclude the program doesn't halt?
        hypertele-Xii 3y ago
        By waiting forever. I understand that "forever" is a nebulous term, but it works both ways. We both know that no computer program could actually run forever.
        myk9001 3y ago
        > I understand that "forever" is a nebulous term, but it works both ways. So, at what point in time the person who is observing a running program is going to declare it doesn't halt? What if they conclude the program doesn't halt, just for it to actually complete execution the very next second? In practical terms, that's why we have timeouts. And in some cases relying on a reasonable timeout is fundamentally the best we can do -- exactly because we can't deterministically answer if a program ever halts. > We both know that no computer program could actually run forever. No program can actually run forever, of course. But any program will stop eventually due to external factors -- me hitting Ctrl + C or pulling the power plug or whatever. The halting problem asks whether it's possible to tell if a program will ever stop or not according to its internal logic. Here's a (likely dumb) analogy off the top of my head regarding a program stopping due to external reasons. Imagine, I toss a coin, lightning strikes and evaporates the coin while its midair. Do I get to say it was heads or tails? Guess, it's impossible to claim either way.
- tylerhou 3y ago
  If you define garbage in the conventional way — “objects that can never be reached from any GC roots” — determining what objects are garbage only takes linear time (tracing)… Reference counting helps the tracing phase out by pruning objects that are clearly garbage early — if a refcount hits zero, that object can clearly be deallocated safely. The converse is not true, which is why we need tracing.
fweimer 3y ago
The case that arises quite often in practice is when a reference is retained, but can only be used on an error path (e.g., as part of an exception). The error condition may not ever happen due to the way to code is written, but it's unlikely the garbage collector can prove that except in the simplest possible cases. Usually, it is acceptable to do a conservative approximation of the actual lifetime, and blame space leaks on the programmer. Garbage collectors usually also make assumptions in the other direction (a non-conservative approximation) when it comes to finalizable resources (e.g., file descriptors). These uses do not involve the reference that is visible to the collector. This gives us Reference.reachabilityFence(), and again mistakes are blamed on the programmer.

raincole 3y ago

It's not. You're describing a static analyzer that inserts free() automatically. Not GC. GC is pretty much the opposite. Edit: Well, I didn't think it through. You're correct. A "perfect GC" is indeed undecidable, and all the real world, practical GC have "false positive" (a piece of memory is no longer used by the code, but there is no way to know it). A perfect GC without false positive is equal to halting problem. Example: var obj = new Object(); // === real code begin ... 50 lines of real code that never uses obj if (something == true) return; ... another 50 lines of real code that never uses obj // === real code end obj.doThings(); A perfect GC can release obj while the real code is running. A real world, imperfect GC can't, since whether the real code returns early or not is undecidable.

lisper 3y ago
> You're correct. No, s/he's not. The original claim was: > It is in general undecidable whether an object is UNREACHABLE. [Emphasis added] Being unreachable is not the same thing as being "no longer used by the code". The latter is indeed undecidable, but the former is not.
chubot 3y ago
After writing a garbage collector, I can say that I’ve seen the unreachable / “will never be used” distinction, and it’s more or less irrelevant trivia. It doesn’t help you write a garbage collector to think of it that way. It doesn’t provide insight into the problem. The problems are elsewhere. Focus on reachability, dynamic understanding of the heap, performance, etc.
- nomel 3y ago
  > more or less irrelevant trivia What are some cases? The only I can think of is if a "remote" thing owned the memory. For example, if I sent a pointer elsewhere, then reused it later. Like, maybe with a device driver, or library.
monocasa 3y ago
You normally fix that not with the GC itself, but with the compiler. If new Object() truly doesn't have any effects visible other than the valid reference, then it's creation can be moved to after the if statement.

aatd86 3y ago

I'll join the others in trying to bring up a nuance. The issue is not necessarily unreachability being undecidable. The issue is that reachability depends on control flow. And that implies being conservative which translates into having to deal with false positives. That static analysis in a nutshell: how to get precision and soundness. Probably a mere question of terminology.

deleted 3y ago

[deleted]

3cats-in-a-coat 3y ago

Empirically what you say can't be the case, because if it's "undecidable" then one of these must be true: 1. The GC frees objects that could be reachable (program gets corrupted in spectacular ways). 2. The GC never frees anything (as it can't decide). The GC may not dispose of objects immediately, but when it determines they're not reachable, they're not reachable, period. There's nothing undecidable about it.

hashmash 3y ago
It's undecidable when you consider the possibility that the program won't ever attempt to access an object. A tracing collector plays it safe and assumes such objects might still be accessed at some point. In GC languages you'll often see deliberate null assignments in order to allow the collector to clean up objects sooner.
- 3cats-in-a-coat 3y ago
  Reachable/accessible and reached/accessed are different things, why are we talking about it as if it's the same thing? One is a potential eventuality, the other is an event. GC are concerned with the potential eventuality, which is 100% decidable, not with the latter, that was never under discussion. To say "reachability is undecidable" means you can't decide whether you MAY or MAY NOT reach it. Which is wrong. You can decide whether you MAY or MAY NOT reach it. And if you MAY NOT... then that's 100% unreachable and safe to collect.

munificent 3y ago

It's easily decidable whether a given GC object could be reached. What isn't decidable is whether a it will be used in the future. The conservative approximation that GC's make is that they keep all objects that could be accessed in the future by the program (reach-able) instead of only keeping the objects that will be used in the future. A trivial example is: void main() { var obj = new Object(); while (true) { // Do other work... if (dayOfWeek == 9) { print(obj); } } } Since there are only seven days in the week, that `print()` statement will never be reached, and an optimal GC would free obj. But the GC can't determine that. All it knows is that it could possibly be reached, so the object stays in memory.

cozzyd 3y ago
https://en.wikipedia.org/wiki/French_Republican_calendar https://en.wikipedia.org/wiki/French_Republican_calendar