Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Memory (and resource locks) are returned to the OS at deterministic points during a program's execution. The control flow of a program by itself is enough to know where, for sure, a given resource can be deallocated. Just like how a human programmer knows where to write fclose(file) when the program is done with it.

GCs solve this by figuring it out directly during runtime when the control flow is executed. But the real source of truth about the control flow is the source. So theoretically, it should be possible to determine where to insert the free() calls before compilation by analyzing the source (or AST).

Reference counting is an obvious way to implement this, but it's easy to encounter situations where pointers are still referenced (still in scope) yet no longer needed. This just converts the responsibility of manually deallocating pointers to a responsibility to manually manage the scope/references to those pointers.

It seems like it's possible to write a program that can read a program's source and:

  1. predict all the permutations of the program's control flow---to similar accuracy as watching the live execution of the program
  2. track all the references to allocated resources
  3. for each reference, traverse the whole subsequent control flow in order to find the earliest point that the reference is guaranteed to never be dereferenced
  4. at that point, insert a deallocation statement at that line of source code

Is there anything out there that does this already? I don't think Rust or C++ smart pointers/RAII is the same thing.

share|improve this question
57  
look up the halting problem. It's the grandfather of why the question of "Can't a compiler figure out if a program does X?" is always answered with "Not in the general case." – ratchet freak Mar 7 at 11:50
17  
Memory (and resource locks) are returned to the OS at deterministic points during a program's execution. No. – Euphoric Mar 7 at 11:56
9  
@ratchetfreak Thanks, it's not ever knowing stuff like this halting problem that makes me wish I got my degree in comp sci instead of chemistry. – zelcon5 Mar 7 at 12:06
14  
@zelcon5, you now know about chemistry and the halting problem... :) – David Arno Mar 7 at 12:06
7  
@Euphoric unless you structure your program so the boundaries of when a resource is used is very clear like with RAII or try-with-resources – ratchet freak Mar 7 at 12:12
up vote 19 down vote accepted

Take this (contrived) example:

void* resource1;
void* resource2;

while(true){

    int input = getInputFromUser();

    switch(input){
        case 1: resource1 = malloc(500); break;
        case 2: resource2 = resource1; break;
        case 3: useResource(resource1); useResource(resource2); break;
    }
}

When should free be called? before malloc and assign to resource1 we can't because it might be copied to resource2, before assigning to resource2 we can't because we may have gotten 2 from the user twice without a intervening 1.

The only way to be sure is to test resource1 and resource2 to see if they are not equal in cases 1 and 2 and free the old value if they were not. This is essentially reference counting where you know there are only 2 possible references.

share|improve this answer
    
Actually that's not the only way; the other way is to only allow one copy to exist. This, of course, comes with its own problems. – Jack Aidley Mar 8 at 16:12

RAII is not automatically the same thing, but it has the same effect. It provides an easy answer to the question "how do you know when this cannot be accessed any more?" by using scope to cover the area when a particular resource is being used.

You might want to consider the similar problem "how can I know my program will not suffer a type error at runtime?". The solution to this is not predicting all the execution paths through the program but by using a system of type annotation and inference to prove that there cannot be such an error. Rust is an attempt to extend this proof property to memory allocation.

It is possible to write proofs about program behaviour without having to solve the halting problem, but only if you use annotations of some kind to constrain the program. See also security proofs (sel4 etc.)

share|improve this answer
    
Comments are not for extended discussion; this conversation has been moved to chat. – maple_shaft Mar 9 at 2:17

Yes, this exists in the wild. The ML Kit is a production-quality compiler that has the described strategy (more or less) as one of its available memory management options. It also allows for the use of a conventional GC or hybridizing with reference counting (you can use a heap profiler to see which strategy will actually produce the best results for your program).

A retrospective on region-based memory management is an article by the original authors of the ML Kit that goes into its successes and failures. The eventual conclusion is that the strategy is practical when writing with the assistance of a heap profiler.

(This is a good illustration of why you shouldn't usually look to the Halting Problem for an answer to practical engineering questions: we don't want or need to solve the general case for most realistic programs.)

share|improve this answer
4  
I think this is an excellent example of proper application of the Halting Problem. The halting problem tells us that the problem is unsolvable in the general case, so you look for limited scenarios in which the problem is solvable. – Taemyr Mar 8 at 8:56
    
Note that the problem becomes far more solvable when we talk about pure or nearly pure functional, non-side-effecting languages like Standard ML and Haskell – cat Mar 8 at 22:50

predict all the permutations of the program's control flow

This is where the problem lies. The amount of permutations is so huge (in practice it is infinite) for any non-trivial program, that time and memory needed would make this completely impractical.

share|improve this answer
    
good point. I guess quantum processors are the only hope, if there's any at all – zelcon5 Mar 7 at 15:02
4  
@zelcon5 Haha, no. Quantum computing makes this worse, not better. It adds additional ("hidden") variables to the program and much more uncertainty. Most practical QC code I've seen relies on "quantum for fast computation, classical for confirmation". I've barely scratched the surface on quantum computing myself, but it seems to me that quantum computers may not be very useful without classical computers to back them up and check their results. – Luaan Mar 8 at 9:20

The halting problem proves this isn't possible in all cases. However, it is still possible in a great many cases, and in fact, is done by nearly all compilers for probably a majority of variables. This is how a compiler can tell it's safe to merely allocate a variable on the stack or even a register, instead of to longer-term heap storage.

If you have pure functions or really good ownership semantics, you can extend that static analysis further, although it becomes prohibitively more costly to do so the more branches your code takes.

share|improve this answer
    
Well, the compiler thinks it can free the memory; but it may not be so. Think of the common beginner's error to return a pointer or a reference to a local variable. The trivial cases are caught by the compiler, true; the less trivial ones aren't. – Peter A. Schneider Mar 8 at 11:31
    
That mistake is made by programmers in languages where programmers must manually manage memory allocation @Peter. When the compiler manages memory allocation, those sorts of mistakes don't happen. – Karl Bielefeldt Mar 8 at 14:04
    
Well, you made a very general statement including the phrase "nearly all compilers" which must include C compilers. – Peter A. Schneider Mar 8 at 15:24
2  
C compilers use it to determine what temporary variables can be allocated to registers. – Karl Bielefeldt Mar 8 at 16:33

If a single programmer or team writes the whole program, it is reasonable that design points can be identified where memory (and other resources) should be freed. Thus, yes, static analysis of the design may be sufficient in more limited contexts.

However, when you factor in third party DLLs, APIs, frameworks, (and throw in threads, too), it can be very difficult (nay, impossible in all cases) for the using programmers to correctly reason about what entity owns what memory and when the last use of it is. Our usual suspect of languages don't sufficiently document the transfer of memory ownership of objects and arrays, shallow and deep. If a programmer can't reason over that (statically or dynamically!) then a compiler most likely can't either. Again, this is due to the fact that memory ownership transfers are not captured in method calls or by interfaces, etc.., so, no it is not possible to statically predict when or where in the code to release memory.

As this is such a serious problem, many modern languages choose garbage collection, which automatically reclaims memory sometime after last live reference. GC has a significant performance cost (especially for real-time applications), however, so is not a universal cure all. Further, you can still have memory leaks using GC (e.g. a collection that only grows). Still, this is a good solution for most programming exercises.

There are some alternatives (some emerging).

The Rust language takes RAII to an extreme. It provides linguistic constructs that define the transfer of ownership in methods of classes and interfaces in more detail, e.g. objects being transferred-to vs. borrowed-by between a caller and callee, or in longer lifetime objects. It provides a high level of compile time safety toward memory management. However, it is not a trivial language to pick up, and is also not without it's problems (e.g. I don't think the design is fully stable, certain things are still being experimented with, and thus, changing).

Swift and Objective-C go yet another route, which is mostly-automatic reference counting. Reference counting gets into issues with cycles, and, there are significant programmer challenges, for example, especially with closures.

share|improve this answer
3  
Sure, GC has costs, but it also has performance benefits. For example, on .NET, allocating from the heap is almost free, because it uses the "stack-allocation" pattern - just increment a pointer, and that's it. I've seen applications that run faster rewritten around the .NET GC than they've been using manual memory allocation, it really isn't clear cut. Similarly, reference counting is actually quite expensive (just at different places from a GC), and something you don't want to pay if you can avoid it. If you want real-time performance, static allocation is often still the only way. – Luaan Mar 8 at 9:25

If a program does not depend on any unknown input then yes, it should be possible (with the caveat that it may be a complex task and may take long; but that would be true for the program as well). Such programs would be completely solvable at compile time; in C++ terms, they could be (almost) completely composed of constexprs. Simple examples would be to compute the first 100 digits of pi or to sort a known dictionary.

share|improve this answer

Freeing of memory, in general, is equivalent to the halting problem - if you can't statically tell whether a program will halt (statically), you can't tell whether it will free memory (statically) either.

function foo(int a) {
    void *p = malloc(1);
    ... do something which may, or may not, halt ...
    free(p);
}

https://en.wikipedia.org/wiki/Halting_problem

That said, Rust is very nice... https://doc.rust-lang.org/book/ownership.html

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.