pl seminar, Thursday, Sept. 12

["Thomas Reps" <reps@xxxxxxxxxxx>]

-N Programming Languages Seminar
-S Mooly Sagiv
-F Tel Aviv University
-T Heap liveness and its usage in automatic memory management
-D 09/12/02
-W Thursday
-M 16:00
-P 1240 CS
-A
.pp
Deallocating memory in a timely manner is a hard (and in general
undecidable) problem.
Programs (and programmers) face the problem of determining the exact
lifetime of an allocated piece of memory.
Failing to do so may lead either to errors as memory leaks
or to poor performance due to consumption of extra space,
or worse errors due to incorrect reuse of needed memory.
Automatic garbage collectors mitigate some of these
problems, but even they cannot prevent memory leaks and may be
unacceptable in some environments.
.pp
In OO programs, such as Java programs,
most of the allocated memory resides in the heap.
Therefore, we develop automatic techniques to identify when memory
allocated in the heap is live at certain point in the execution,
i.e., can be further used along some execution path from this point. We
developed dynamic and static algorithms to identify heap liveness. This
information is used to safely deallocate space and decide when manual
memory deallocation is unsafe.
.pp
Our dynamic algorithms profile the memory in order to collect liveness
information (including liveness of heap-allocated elements) in a
feasible manner.
The dynamic algorithms were implemented in the Java Virtual Machine
and used to estimated the potential memory saving beyond the ones
obtained by existing GC algorithms.
We also show that simple program transformations can be used to
achieve some of these savings.
.pp
Our static algorithms identify program points at which memory can be
deallocated. These algorithms establish temporal properties of the heap,
which is challenging because the addresses of the memory elements
concerned are not statically known.
The algorithms were implemented in TVLA and used to show that on
toy programs we can actually deallocate memory at compile time.
For online publications see http://www.cs.tau.ac.il/~ransh
.pp
(Joint work with Ran Shaham and Hillel Kolodner.)