Heap Space Analysis for Java Bytecode
Elvira Albert, Samir Genaim and Miguel Gomez-Zamalloa
The 2007 International
Symposium on Memory Management (ISMM 2007) Montreal, Canada, 21-22
October, 2007
Abstract
This article presents a heap space analysis for (sequential)
Java bytecode. The analysis generates heap space cost relations which define at
compile-time the heap consumption of a program as a function of its data size.
These relations can be used to obtain upper bounds on the heap space allocated
during the execution of the different methods. In addition, we describe how to
refine the cost relations, by relying on escape analysis, in order to take into
account the heap space that can be safely deallocated by the garbage collector
upon exit from a corresponding method. These refined cost relations are then
used to infer upper bounds on the active heap space upon methods return. Example
applications for the analysis consider inference of constant heap usage and heap
usage proportional to the data size (including polynomial and exponential heap
consumption). Our prototype implementation is reported and demonstrated by means
of a series of examples which illustrate how the analysis naturally encompasses
standard data-structures like lists, trees and arrays with several dimensions
written in object-oriented programming style.