Compile Time Garbage Collection impossible? - Compilers

I think that compile time garbage collection is impossible, and
existing approximation are not good enough or scalable. (it is my
opinion, but what do I know?)

But there have been some success in developing runtime tools to
identify and isolate problems due to holding references beyound useful
life an object. I will list two approaches:

1. Leakbot at IBM Research : It identifies "leaking regions" in Java
programs by doing heapdump ****ysis. References can be found at
http://domino.research.ibm.com/comm/...novation2.html
and this technology has gone into products such as Rational
Application Developer
(http://www.ibm.com/developerworks/ra..._GuptaPalanki/)
and Memory Dump Diagnostic tool bundled with WebSphare. So this one is
pretty scalable and useful. I have used with heap dumps from
production environments having 20+ million objects and almost 39+
million references.

2. Tools to identify Lag, Drag, Void and Use of various objects in
heap: Originally it was done for Haskell (N. Rojemo and C. Runciman,
"Lag, drag, void and use -- heap profiling and space-efficient
compilation revisited," Proceedings of the ACM SIGPLAN International
Conference on Function Programming, pp. 34-41, 1996), and later for
Java as well (R. Shaham, E. K. Kolodner, and M. Sagiv, "Heap Profiling
for Space-Efficient Java," Proceedings of ACM SIGPLAN Conference on
Programming Language Design and Implementation, pp. 104-113, 2001).

Of course, these tools wouldn't GC the "useless but rechable" objects
automatically. They just indicate where you need to look to fix your
program so that a reference to unused objects doesn't remain alive.
Interestingly, Shaham/Kolodner/Sagiv indicate that the future work
would be to use the drag ****ysis results for directing static
****ysis in a compiler to automatically do some code transformation
for reducing drag.

my 2 bits,
+satish


--- glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:

> A.L. wrote:
>
> (snip)

>> Determining what objects could be deallocated during compilation is
>> equivalent to "halting problem" that is undecidable. i.e. there is
>> no algorithm possible that could do this for all possible programs.

> I don't disagree, but determining deallocation at
> run-time isn't so easy, either.

> In addition to circular linked lists, which as already mentioned are
> a problem for reference count GC, there is memory allocated in main
> and not referenced later. Those two are often indicated in Java
> documentation. ...