Re: Compile Time Garbage Collection impossible?

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 analysis. References can be found at
http://domino.research.ibm.com/comm/research.nsf/pages/r.plansoft.innovation2.html
and this technology has gone into products such as Rational
Application Developer
(http://www.ibm.com/developerworks/rational/library/05/0816_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 analysis results for directing static
analysis 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. ...

Return to the comp.compilers page.
Search the comp.compilers archives again.