5 ms·

I'm definitely a newbie at this topic, but I wonder if we can have some type of static GC? I'm not speaking about Radical change to the model of the programming

I'm definitely a newbie at this topic, but I wonder if we can have some type of static GC? I'm not speaking about Radical change to the model of the programming language (like Rust), but about a compile time analyzer that can detect when object will go out of memory (edit: out of scope) and insert a code to deal with it, or make some expectations about the real generation of the object, this will decrease the amount of required work by the GC during runtime, no?

cardiffspaceman 7y ago
The Standard ML implementation called ML Kit added memory tracking to the type system in order to infer the lifetime of objects. I ran into a safe C dialect that built on the work in ML Kit to avoid memory allocation overhead in C as well, but I can't remember the name of the project. The Cyclone project mentioned in the link might have been it, but it has less automation than ML Kit. https://en.wikipedia.org/wiki/Region-based_memory_management#Region_inference https://en.wikipedia.org/wiki/Region-based_memory_management...
rng_civ 7y ago
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).
vidarh 7y ago
Depending on the language, you can do this for some things. The fundamental challenge is escape analysis: when this function returns, what might have been retained elsewhere? If you can answer that, then you can optimize accordingly. E.g you can choose to allocate objects that won't be retained on the stack instead of the heap, or in separate blocks. You can even potentially benefit from this even if you can't 100% know. If you use a generational collector, an object that almost certainly escapes could bypass the nursery, for example.
- ufo 7y ago
  There are some optimizations that do thus. When you know the object won't outlive the function, allocate it on thw stack instead of on the heap And on the more extreme case you can even replace the objects with a bunch of local variables. For example, replace a Point object allocated on the stack with a pair of variables gor the x and y coordinates.

cardiffspaceman 7y ago

The Standard ML implementation called ML Kit added memory tracking to the type system in order to infer the lifetime of objects. I ran into a safe C dialect that built on the work in ML Kit to avoid memory allocation overhead in C as well, but I can't remember the name of the project. The Cyclone project mentioned in the link might have been it, but it has less automation than ML Kit. https://en.wikipedia.org/wiki/Region-based_memory_management#Region_inference https://en.wikipedia.org/wiki/Region-based_memory_management...

rng_civ 7y ago

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

vidarh 7y ago

Depending on the language, you can do this for some things. The fundamental challenge is escape analysis: when this function returns, what might have been retained elsewhere? If you can answer that, then you can optimize accordingly. E.g you can choose to allocate objects that won't be retained on the stack instead of the heap, or in separate blocks. You can even potentially benefit from this even if you can't 100% know. If you use a generational collector, an object that almost certainly escapes could bypass the nursery, for example.

ufo 7y ago
There are some optimizations that do thus. When you know the object won't outlive the function, allocate it on thw stack instead of on the heap And on the more extreme case you can even replace the objects with a bunch of local variables. For example, replace a Point object allocated on the stack with a pair of variables gor the x and y coordinates.