Modeling The Heap: A Practical Approach

January 5, 2010
Mark Marron | Imdea-Software research

At the heart of most software engineering and optimization applications is some
model of runtime program behavior. The widespread adoption of object-oriented
programming and memory managed languages has lead to programs that make
extensive use of rich pointer structures and that use data as a central part of
organizing the program structure. Thus, understanding the memory state of the
program is an increasingly critical part of understanding the behavior of the
program. The increasing difficulty (and importance) of understanding the
behavior of a program is occurring at the same time as increasing program
complexity, the growing need for these programs to take advantage of parallel
hardware (plus complex memory hierarchies), and the decreasing tolerance for
software defects.

This talk will introduce a model we have developed for representing the program
heap and the classes of information that can be represented with this model
(shape, regions, heap use/mod, reachabliltiy, collection/iterator state,
sharing, nullity, and escape information). Using this model we will briefly
demonstrate how it can be used for static analysis and debugger support. The
static analysis is currently able to handle the majority of the managed .net
bytecode and can analyze programs up to 15KLoc in a few minutes and a ~200MB of
memory (which is exceptionally fast for shape analysis techniques). These
results can the be used directly to aid program understanding, for generating
rich type signatures, in optimization applications, or as the basis for other
analysis tools. I will also demonstrate how the model can be used in dynamic
applications, such as a debugger where we use the model to produce compact
visualizations of the heap to aid the programmer in understanding the program
state.

Speaker Details

Mark Marron recieved his Ph.D. from the University of New Mexico and is currently a post-doctoral researcher at Imdea-Software research in Madrid Spain. His research interests include techniques for modeling and understanding the program heap, and on applying this information to program development.