3 ms·

I prefer the correct definition of a GC: > [1]: Garbage collection is simulating a computer with an infinite amount of memory. Chen even provides the "memory

I prefer the correct definition of a GC: > [1]: Garbage collection is simulating a computer with an infinite amount of memory. Chen even provides the "memory reclamation" definition in his post, but points out that it is incomplete. The article could be made much shorter (although the full read is still very interesting): as Rust has no free() call, Rust simulates infinite memory and is hence garbage collected. [1]: https://blogs.msdn.microsoft.com/oldnewthing/20100809-00/?p=13203 https://blogs.msdn.microsoft.com/oldnewthing/20100809-00/?p=...

amelius 8y ago
I always think that GCs are incomplete in a way. They can reclaim memory in cases such as: x = [1, 2, 3] ... x = [] But not in cases such as: x = [1, 2, 3] ... (x not used) Of course, determining if x is used might be uncomputable in general, but in practice it might be computable in a lot of cases.
- kazinator 8y ago
  A compiler can determine that a local variable x has no "next use", and insert the x = [] at that point to help garbage collection (or else provide some map of what is live). https://en.wikipedia.org/wiki/Live_variable_analysis https://en.wikipedia.org/wiki/Live_variable_analysis
  - amelius 8y ago
    Yes, but it's too simple. Consider: a = { x: [1, 2, 3], y: [1] } ... (a.y used, but a.x not used)
    - arghwhat 8y ago
      This is theoretically solvable, assuming those arrays are by reference. However, it's just not worth the effort of a significant increase in GC complexity.
- umanwizard 8y ago
  I don't understand what you mean. Any GC will reclaim `x` after it is unreachable from a root.
  - TheCoreh 8y ago
    Unreachable is not the same as unused It could still be reachable, just never read from. Static code analysis can detect some forms of this, but not all e.g. if (someUnknownCondition) { // access x }
    - umanwizard 8y ago
      Well as the person I was replying to points out, this is uncomputeable in general (`someUnknownCondition` might be brute-forcing all possible mathematical proofs to see whether the Reimann hypothesis is true), and I would expect optimizing compilers to already handle this in the cases where it is feasibly computable. Is that not the case?
    - arghwhat 8y ago
      In this case, you cannot free the memory manually either without making your program potentially invalid. It is unreasonable to expect a GC to do runtime control flow analysis, which is also more than you would do in a normal case of manual memory management. If you have tricky situations where you know that program flow dictates that an expensive but reachable variable is no longer needed, you would insert a "x = nil" or similar in the position where you would otherwise have made a free. However, this is solely a case of fine-tuned optimization, rather than a case of correctness.
      - zamalek 8y ago
        > without making your program potentially invalid You'd only need the GC to disconnect that local from the stack frame, as anything that escapes would be rooted elsewhere. This can be done by having the compiler/JIT emit a liveness map: instruction pointer ranges indicating which variables uninitialized, live or dead. Otherwise, exactly. Rust could do this with zero runtime overhead (as the map would be used by borrowck). This is pretty simple to do but generally isn't, precisely because of this: "this is solely a case of fine-tuned optimization." If you are part of the 0.1% of the people who is actually solving one the of 0.001% problems where this level of control is _genuinely_ important, then use a language that supports this. Assuming that the method is executing for a very long time (>μs), because this the only time you'd probably care about memory management at this level, any FFI is virtually free. However, even if you are part of the 0.1% of people who have a legitimate concern for this, and you are working on a 0.001% problem, why on earth are you doing so many allocations and frees? Against your own better judgement? If you care enough to worry about when memory is freed, you should know enough that you should re-use memory as much as possible without involving the allocator.
- zamalek 8y ago
  The article I linked deals with this. GCs typically guarantee cleanup in a scope. With managed languages, this is whenever the runtime decides to run the GC (probably when memory is needed and isn't available). With Rust RAII this is when the ref count reaches zero which is, at the very soonest, at the end of the current scope (you can force the collection with a naked scope if you need[1]). [1]: https://play.rust-lang.org/?gist=66740557884b17683b868483e524c6ba&version=stable&mode=debug&edition=2015 https://play.rust-lang.org/?gist=66740557884b17683b868483e52...
millstone 8y ago
"GC: a simulation of a computer with an infinite amount of memory." This is not a correct definition.
pcwalton 8y ago
> [1]: Garbage collection is simulating a computer with an infinite amount of memory. But that definition also applies to virtual memory. On any modern OS, you can simulate a computer with an infinite amount of memory in C and C++ by just never calling free(). It'll even work pretty well for programs with small working sets, as the kernel will start paging out unused memory to swap. I think any definition of garbage collection needs to specify that it is a form of memory management: it can automatically determine what memory will be used later so that it can recycle memory that will not.
- zamalek 8y ago
  > just never calling free() So your code would look a lot like it was running under a garbage collector? The OS memory manager is the garbage collector in this case.
  - ecnahc515 8y ago
    No, because the OS isn't reclaiming the memory specifically; and this only works with overcommit and/or swap. The memory isn't actually being reclaimed, it's being paged out. If your application actually begins to use the memory but never uses the data again (eg; can't reference it) it will continue to eat memory until the OOM killer kicks in or the system crashes.
    - eximius 8y ago
      Well, unless your program is particularly long lived, it will be reclaimed. There are many tools that could reasonably forego `free` for their entire runtimes.
      - ecnahc515 8y ago
        I presume we're talking about long running programs otherwise the conversation isn't really super useful since for any program, short or long memory is reclaimed when a program exits (well, at least on any modern OS).
- 8y ago
mikeash 8y ago
That definition doesn’t work when presented with a program with a working set that grows arbitrarily large.

amelius 8y ago

I always think that GCs are incomplete in a way. They can reclaim memory in cases such as: x = [1, 2, 3] ... x = [] But not in cases such as: x = [1, 2, 3] ... (x not used) Of course, determining if x is used might be uncomputable in general, but in practice it might be computable in a lot of cases.

kazinator 8y ago
A compiler can determine that a local variable x has no "next use", and insert the x = [] at that point to help garbage collection (or else provide some map of what is live). https://en.wikipedia.org/wiki/Live_variable_analysis https://en.wikipedia.org/wiki/Live_variable_analysis
- amelius 8y ago
  Yes, but it's too simple. Consider: a = { x: [1, 2, 3], y: [1] } ... (a.y used, but a.x not used)
  - arghwhat 8y ago
    This is theoretically solvable, assuming those arrays are by reference. However, it's just not worth the effort of a significant increase in GC complexity.
umanwizard 8y ago
I don't understand what you mean. Any GC will reclaim `x` after it is unreachable from a root.
- TheCoreh 8y ago
  Unreachable is not the same as unused It could still be reachable, just never read from. Static code analysis can detect some forms of this, but not all e.g. if (someUnknownCondition) { // access x }
  - umanwizard 8y ago
    Well as the person I was replying to points out, this is uncomputeable in general (`someUnknownCondition` might be brute-forcing all possible mathematical proofs to see whether the Reimann hypothesis is true), and I would expect optimizing compilers to already handle this in the cases where it is feasibly computable. Is that not the case?
  - arghwhat 8y ago
    In this case, you cannot free the memory manually either without making your program potentially invalid. It is unreasonable to expect a GC to do runtime control flow analysis, which is also more than you would do in a normal case of manual memory management. If you have tricky situations where you know that program flow dictates that an expensive but reachable variable is no longer needed, you would insert a "x = nil" or similar in the position where you would otherwise have made a free. However, this is solely a case of fine-tuned optimization, rather than a case of correctness.
    - zamalek 8y ago
      > without making your program potentially invalid You'd only need the GC to disconnect that local from the stack frame, as anything that escapes would be rooted elsewhere. This can be done by having the compiler/JIT emit a liveness map: instruction pointer ranges indicating which variables uninitialized, live or dead. Otherwise, exactly. Rust could do this with zero runtime overhead (as the map would be used by borrowck). This is pretty simple to do but generally isn't, precisely because of this: "this is solely a case of fine-tuned optimization." If you are part of the 0.1% of the people who is actually solving one the of 0.001% problems where this level of control is _genuinely_ important, then use a language that supports this. Assuming that the method is executing for a very long time (>μs), because this the only time you'd probably care about memory management at this level, any FFI is virtually free. However, even if you are part of the 0.1% of people who have a legitimate concern for this, and you are working on a 0.001% problem, why on earth are you doing so many allocations and frees? Against your own better judgement? If you care enough to worry about when memory is freed, you should know enough that you should re-use memory as much as possible without involving the allocator.
zamalek 8y ago
The article I linked deals with this. GCs typically guarantee cleanup in a scope. With managed languages, this is whenever the runtime decides to run the GC (probably when memory is needed and isn't available). With Rust RAII this is when the ref count reaches zero which is, at the very soonest, at the end of the current scope (you can force the collection with a naked scope if you need[1]). [1]: https://play.rust-lang.org/?gist=66740557884b17683b868483e524c6ba&version=stable&mode=debug&edition=2015 https://play.rust-lang.org/?gist=66740557884b17683b868483e52...

millstone 8y ago

"GC: a simulation of a computer with an infinite amount of memory." This is not a correct definition.

pcwalton 8y ago

> [1]: Garbage collection is simulating a computer with an infinite amount of memory. But that definition also applies to virtual memory. On any modern OS, you can simulate a computer with an infinite amount of memory in C and C++ by just never calling free(). It'll even work pretty well for programs with small working sets, as the kernel will start paging out unused memory to swap. I think any definition of garbage collection needs to specify that it is a form of memory management: it can automatically determine what memory will be used later so that it can recycle memory that will not.

zamalek 8y ago
> just never calling free() So your code would look a lot like it was running under a garbage collector? The OS memory manager is the garbage collector in this case.
- ecnahc515 8y ago
  No, because the OS isn't reclaiming the memory specifically; and this only works with overcommit and/or swap. The memory isn't actually being reclaimed, it's being paged out. If your application actually begins to use the memory but never uses the data again (eg; can't reference it) it will continue to eat memory until the OOM killer kicks in or the system crashes.
  - eximius 8y ago
    Well, unless your program is particularly long lived, it will be reclaimed. There are many tools that could reasonably forego `free` for their entire runtimes.
    - ecnahc515 8y ago
      I presume we're talking about long running programs otherwise the conversation isn't really super useful since for any program, short or long memory is reclaimed when a program exits (well, at least on any modern OS).
8y ago

mikeash 8y ago

That definition doesn’t work when presented with a program with a working set that grows arbitrarily large.