  Modern programming environments provide extensive support for inspecting,
analyzing, and testing programs based on the algorithmic structure of a
program. Unfortunately, support for inspecting and understanding runtime data
structures during execution is typically much more limited. This paper provides
a general purpose technique for abstracting and summarizing entire runtime
heaps. We describe the abstract heap model and the associated algorithms for
transforming a concrete heap dump into the corresponding abstract model as well
as algorithms for merging, comparing, and computing changes between abstract
models. The abstract model is designed to emphasize high-level concepts about
heap-based data structures, such as shape and size, as well as relationships
between heap structures, such as sharing and connectivity. We demonstrate the
utility and computational tractability of the abstract heap model by building a
memory profiler. We then use this tool to check for, pinpoint, and correct
sources of memory bloat from a suite of programs from DaCapo.
