3 ms·

Isn't a compile-time analyzer that can detect when an object will go out of memory precisely what Rust (and C++ RAII) does? It's just a form of escape analysis.

Isn't a compile-time analyzer that can detect when an object will go out of memory precisely what Rust (and C++ RAII) does? It's just a form of escape analysis. Imagine creating a Rust program entirely with `Rc`. It's basically a GC'd program at the point where the "roots" are managed by the reference counter. The "list of roots" is only ever messed with whenever a `Rc` is dropped/created, and one can optimize functions to take `&Rc` to reduce "GC" pressure. I do not believe it's possible to automate this process in general because if you could, I have a hunch the solution can be used to decide the Halting Problem. So sure, in general a GC can perform some heuristics to predict the lifetime of an object, but usually the point of using a GC is that one does NOT know the lifetime or it is insanely complex.

nostrademons 7y ago
Such analysis also requires language design that limits the legal statements in a program to make the analysis tractable. Without these restrictions, this problem is isomorphic to the halting problem. (Proof: assignment of a given memory object to a field within another unrelated object creates another reference. The job of automatic memory management is to determine when no such references exist. Now replace that assignment with HALT. Any such automatic memory manager that operates statically would be able to find all HALT statements within the program and so solve the halting problem for an arbitrary program.) That's why languages that manage memory statically like Rust & C++ must be able to reject some programs as "not passing the borrow-checker", and everything else requires run-time support via either GC or refcounting.
- vidarh 7y ago
  Doing it perfectly requires a suitable language design, but even a pathologically statical analysis unfriendly language like Ruby still allows you to determine it in many cases. You just need to accept that for such languages it is an optimisation, and you still need to fall back on full gc.
pjmlp 7y ago
Systems programming languages with GC (any form of automatic memory management), also provide features for doing manually memory management, explicitly releasing resources, allocating on the stack or the global memory segment. Depending on what one is trying to do, those constructs can still be allowed on safe code, or require explicit unsafe modules (or code blocks). Examples, D, Nim, Swift, Mesa/Cedar, Modula-2+, Modula-3, Sing#, System C# (aka M#), .NET (version and language dependent).

nostrademons 7y ago

Such analysis also requires language design that limits the legal statements in a program to make the analysis tractable. Without these restrictions, this problem is isomorphic to the halting problem. (Proof: assignment of a given memory object to a field within another unrelated object creates another reference. The job of automatic memory management is to determine when no such references exist. Now replace that assignment with HALT. Any such automatic memory manager that operates statically would be able to find all HALT statements within the program and so solve the halting problem for an arbitrary program.) That's why languages that manage memory statically like Rust & C++ must be able to reject some programs as "not passing the borrow-checker", and everything else requires run-time support via either GC or refcounting.

vidarh 7y ago
Doing it perfectly requires a suitable language design, but even a pathologically statical analysis unfriendly language like Ruby still allows you to determine it in many cases. You just need to accept that for such languages it is an optimisation, and you still need to fall back on full gc.

pjmlp 7y ago

Systems programming languages with GC (any form of automatic memory management), also provide features for doing manually memory management, explicitly releasing resources, allocating on the stack or the global memory segment. Depending on what one is trying to do, those constructs can still be allowed on safe code, or require explicit unsafe modules (or code blocks). Examples, D, Nim, Swift, Mesa/Cedar, Modula-2+, Modula-3, Sing#, System C# (aka M#), .NET (version and language dependent).