Re: Compile Time Garbage Collection impossible?

Satish Chandra Gupta <scgupta@yahoo.com>
3 Oct 2006 18:18:50 -0400

          From comp.compilers

Related articles
[12 earlier articles]
Re: Compile Time Garbage Collection impossible? torbenm@app-3.diku.dk (2006-09-28)
Re: Compile Time Garbage Collection impossible? sleepingsquirrel@yahoo.com (Greg Buchholz) (2006-09-28)
Re: Compile Time Garbage Collection impossible? bobduff@shell01.TheWorld.com (Robert A Duff) (2006-09-30)
Re: Compile Time Garbage Collection impossible? danwang74@gmail.com (Daniel C. Wang) (2006-09-30)
Re: Compile Time Garbage Collection impossible? gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-09-30)
Re: Compile Time Garbage Collection impossible? int2k@gmx.net (Wolfram Fenske) (2006-09-30)
Re: Compile Time Garbage Collection impossible? scgupta@yahoo.com (Satish Chandra Gupta) (2006-10-03)
Re: Compile Time Garbage Collection impossible? oliver@first.in-berlin.de (Oliver Bandel) (2006-10-08)
| List of all articles for this month |

From: Satish Chandra Gupta <scgupta@yahoo.com>
Newsgroups: comp.compilers
Date: 3 Oct 2006 18:18:50 -0400
Organization: Compilers Central
References: 06-09-164
Keywords: GC
Posted-Date: 03 Oct 2006 18:18:50 EDT

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. ...



Post a followup to this message

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