I have read this question on compile time gc and what I understand from it is that the compiler wouldn't know if a variable is referenced or not by some other object due to conditional statements (because they are computed at runtime), and that is why runtime GCs are used, as they can dynamically check if a variable is referenced or not. My question is, if a compiler would simulate every conditional statement in a program, could it then always find when a variable has 0 references to it, and then add a delete/deallocation statement?
1
-
1$\begingroup$ Related question: cs.stackexchange.com/questions/68635/… $\endgroup$– Pseudonym ♦Commented Aug 3, 2022 at 11:36
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
2
No, it's not possible for a compiler to do that. Doing so is an undecidable problem.
To get some intuition for why it is hard, consider the combinations of loops and conditional statements. It's not clear how you would simulate all possibilities since you don't know at compile time how long the loop will iterate. (In fact it is impossible, as shown by the undecidability of the halting problem.)
-
$\begingroup$ I think good Java compilers do this sometimes. You may sometimes create an object, store some values, use some method, and then remove all references to the object in a way that the compiler can recognise. In that case the compiler can allocate and deallocate the object, or even not allocate the object at all, but just do the calculations. It's just not possible in general. $\endgroup$ Commented Aug 3, 2022 at 18:17
-
$\begingroup$ @gnasher729: Yes, this is a useful optimization in simple cases where it is provable via some cheapish algorithms (low-order polynomial, especially for a JIT compiler) on the program logic. (e.g. Escape Analysis). This normally also allows Scalar Replacement (of an object by separate primitive members), which can then be allocated in registers and/or spilled to the stack if needed. (e.g. how fragile is escape analysis in Hotspot in simple cases such as iterator in for-each loop but JS engines and AoT C# do it, too.) $\endgroup$ Commented Aug 3, 2022 at 23:42
$\begingroup$
$\endgroup$
Even without (appropriately) invoking the halting problem, there are situations where this is impossible: for instance when the allocation/deallocation scheme depends on the particular values of the input data, which are unknown at compile-time.
$\begingroup$
$\endgroup$
What D.W. said is correct in one way: It is impossible for a compiler in general to decide that at point X in a program, object O is not referenced anymore and can be deallocated.
However, you can (and lots of software does that) use reference counting instead of garbage collection. So you count at runtime how many references to an object O there are, and when the number of references goes down to 0, it is deallocated. That is what happens for practically all MacOS and iOS software.
In this particular case, circular references are not handled as they should be. If object A has a reference to B, and B has a reference to A, both have a reference count of 1 if there are no other references, and will never be deallocated. To solve this problem, they rely on the developer not creating such a situation, and the compiler detecting both situations where a circular reference is created, and detecting situations where it cannot prove that no circular reference is created.
They also support "weak references", that is references that don't keep an object alive. For example, if an array contains 100 objects, and each object has a reference to the array, then those backward references would be typically weak references. So the array can be deallocated if there are no other references than those from the objects that it contains. (And when the array is deallocated, the reference counts of many objects might go to 0, and then those objects are also deallocated).
$\begingroup$
$\endgroup$
For a more practical example, imagine writing a program that reads in a graph, performs some operations on it, and prints it out. It's possible a command in the middle deletes a node, dropping half the graph. The only way the program could know to delete the associated memory, however, is to read the graph in, execute the operations, and then trace the graph/memory to find if there's any abandoned parts. That's inherently a run time operation.
$\begingroup$
$\endgroup$
1
... if a compiler would simulate every conditional statement in a program ...
You forget about programs that have some input:
Let's say we have two variables: A and B. Both are pointers (or references) to objects.
If the user presses X on the keyboard, a new object is generated and the reference is written to A.
if the user presses Y on the keyboard, the value of A is copied to B, so B points to the same object as A.
Question: Do we have to deallocate an object if the user presses Y?
The answer: This depends on what the user typed before the Y:
If the user typed Y before typing Y again, the object must not be deallocated because A points to the same object. If the user typed X before typing Y, the object B points to (before being overwritten) must be deallocatd.
Your next question could be:
"What if we store some additional information - such as if the last key pressed was X or Y"?
The information you need to store is how often some object is referenced - this means: How many variables point to an object.
The compiler must increment or decrement this value for each object and if the value becomes zero, it deallocates the object.
This approach is really done (e.g. in the GTK toolkit (used in many Linux programs) or in Windows OLE/COM). However, according to Wikipedia, it is less efficient than garbage collection.
And your next question could be:
"What about programs that do not have input?"
In this case, what you are suggesting is nothing but running the program a first time and using the results for the optimization of the program.
If you have a program which is terminating (halting), you can of course do this.
However, in this case, you could also simply store the output of the program and when running the program again, simply use the saved pre-calculated output instead of doing the calculations again.
-
$\begingroup$ "According to Wikipedia it is less efficient than garbage collection". Apple used garbage collection at some point and later removed it; I assume they had a reason (admittedly having to use low-level C code was probably one reason). I assume that the time complexity will be similar, so this is very much a matter of implementation. Details are: Speed on a theoretically multi-threaded system where most objects are referenced by one thread only, the compiler merging multiple reference count changes into one, deallocation on background threads, and many other things. Depends on the effort. $\endgroup$ Commented Aug 3, 2022 at 16:00