Are there languages or compilers having optimizations to deallocate variables early?

Question

In a scope that defines two variables a and b, the code firstly does things only on a. Then a is not used anymore. And it does things only on b afterward.

A possible optimization is to deallocate a before using b, and allocate b in the same memory location as a (if they are allocated on the stack).

In C you could manually do this by grouping each of the two parts using braces. But are there languages or compilers that could automatically do this as an optimization? (I believed some compilers do, but found they don't.) I could accept constructors and destructors are not called in a reliable time sequence in such a language, or at least in the situations that support the optimization. But could it still be possible if there are pointers may or may not be pointing to the variable?

---

This was the code I was testing in gcc and g++:

#include<stdio.h>

int main(){
    int a[2000000];
    scanf("%d",&a[900000]);
    printf("%d\n",a[900000]);
    int b[2000000];
    scanf("%d",&b[900000]);
    printf("%d\n",b[900000]);
}

It segfaulted but would work with the b part all removed. Adjust the numbers if your system had a different default stack size.

I did believe gcc has this optimization as the comments suggest, but it didn't pass the test, even with -O3. Before knowing this, what I intended to ask was whether there are any advances (assuming it has existed in the first place) to this kind of optimization, with the new concepts such as ownership.

Answer 1

Yes. The Koka programming language does this. What you are looking for is referred to by the authors as "garbage-free" memory management, and "reuse" (in various forms).

• "garbage-free": objects are destructed immediately on their last use, via Koka's ownership analysis / reference counting. This means that at any given point in the program's execution, there are no dead objects (or they are immediately about to be destructed). Whether this is a tangible benefit over destructing just at the end of scope / sometime later in most cases is not clear, but it allows for...
• "reuse": when objects are destructed, rather than actually calling dealloc, the compiler can instead keep that memory and do what it wants with it. This is best explored in the FP^2 paper, for updating ex. lists in-place without allocations or growing the stack.

The publications describing how Koka's fancier features work are quite readable and I recommend sitting down and flipping through them. Some choice quotes/summaries:

Garbage Free Reference Counting with Reuse

Starting from a functional core language with explicit control-flow, Perceus emits precise reference counting instructions such that programs are garbage free, where only live references are retained.

Reference Counting with Frame Limited Reuse

An important extension is reuse analysis. This optimization pairs objects of known size with fresh allocations of the same size and tries to reuse the object in-place at runtime if it happens to be unique.

Fully in-Place Functional Programming

In this paper we describe a novel fully in-place (FIP) calculus that guarantees that such a function can be compiled in a way to never (de)allocate memory or use unbounded stack space—it can be executed fully in-place.

Answer 2

This is related to object lifetime optimization.

LLVM has what they call a StackColoring Pass that does exactly that. In the documentation comment on that page:

Stack Coloring reduces stack usage by merging stack slots when they can't be used together. For example, consider the following C program:

     void bar(char *, int);
     void foo(bool var) {
         A: {
             char z[4096];
             bar(z, 0);
         }

         char *p;
         char x[4096];
         char y[4096];
         if (var) {
             p = x;
         } else {
             bar(y, 1);
             p = y + 1024;
         }
     B:
         bar(p, 2);
     } 

Naively-compiled, this program would use 12k of stack space. However, the stack slot corresponding to z is always destroyed before either of the stack slots for x or y are used, and then x is only used if var is true, while y is only used if var is false. So in no time are 2 of the stack slots used together, and therefore we can merge them, compiling the function using only a single 4k alloca:

     void foo(bool var) { // equivalent
         char x[4096];
         char *p;
         bar(x, 0);
         if (var) {
             p = x;
         } else {
             bar(x, 1);
             p = x + 1024;
         }
         bar(p, 2);
     } 

This is an important optimization if we want stack space to be under control in large functions, both open-coded ones and ones created by inlining.

Answer 3

This is just a comment, but consider this line in your example code.

scanf("%d",&a[900000]);

A C compiler would require some extra information (e.g. escape analysis) to know that scanf doesn't retain a copy of that pointer, such as in a static variable. Being a built-in function, perhaps a compiler can just "know" what scanf does, but that's another kind of extra information.

In the absence of that information, it might be an incorrect "optimisation" to deallocate the variable earlier than the end of the scope.

Answer 4

But are there languages or compilers that could automatically do this as an optimization?

Absolutely yes. A very common optimization for a register allocator is to notice that two local variables have non-overlapping lifetimes as you describe, and use the same register for both; a variable might never be reified as a memory location. (Obviously in languages that allow taking the addresses of variables, this optimization does not apply if the variable's address is taken!)

I could accept constructors and destructors are not called in a reliable time sequence in such a language, or at least in the situations that support the optimization.

Oh there are some nasty situations you can get into in garbage collected languages. C# does not guarantee that a local variable containing that reference keeps the referred-to object alive, and the finalizers typically run on another thread. For example, suppose you have an unmanaged code library that creates a temporary disk storage, and deletes it when the storage object is finalized:

var x = CreateTempStorage();
var y = CreateFileInTempStorage(x);
y.Write(whatever)

If x is never used again in this method, the garbage collector is totally within its rights to run the finalizer immediately and destroy the temporary storage. Since the finalizer runs on its own thread, now we've got a race between all operations on that storage, and its destruction, and who knows what will happen? (This is not a theoretical concern; in the early days of .NET I wrote an interop layer on top of the COM IStorage API and had to use various techniques to ensure that the runtime would always destroy the "parent" objects after their children.)

It gets even worse; in C# if the garbage collector determines that an object is never used it is possible that the constructor and the finalizer are running at the same time on different threads. Writing a correct finalizer is quite tricky.

Answer 5

Swift's optimizer does this.

The language guarantees objects live until their last use, not necessary until the end of scope.

E.g.

class C {
    init() { print("Initialized  a new object at \(Unmanaged.passUnretained(self).toOpaque())") }
    deinit { print("Deinitializing the object at \(Unmanaged.passUnretained(self).toOpaque())") }
}

func main() {
    let x = C()
    let y = C()
}

main()

Prints:

Initialized  a new object at 0x0000600003a64030
Deinitializing the object at 0x0000600003a64030
Initialized  a new object at 0x0000600003a64030
Deinitializing the object at 0x0000600003a64030

(It doesn't apply to top-level global variables, so I wrapped this demonstration up in this little main() function)

To keep an object alive for longer, you can use withExtendedLifetime(_:_:)

Answer 6

C++ standard basically mandates that an initialized object stays valid in its scope after initialization (and destructed/deallocated only at the end of scope), so this optimization it's not really possible.

For languages that are ostensibly interpreted in virtual stack machines, this optimization may happen, as any stack popping is implicit and immediately "forgetting" any variable that is not used anymore.

And then you may need to start using things like Reference.reachabilityFence(obj) to avoid objects being collected while methods are still running.

TL;DR: Some language specifications forbides this, and in languages where this is permitted, problems may arise.