A large gap exists between the wide range of admissible heap structures and those that programmers actually build. To understand this gap, we empirically study heap structures and their sharing relations in real-world programs. Our goal is to characterize these heaps. Our study rests on a heap abstraction that uses structural indistinguishability principles to group objects that play the same role. Our results shed light on prevalence of recursive data-structures, aggregation, and the sharing patterns that occur in programs. We find, for example, that real-world heaps are dominated by atomic shapes (79% on average) and the majority of sharing occurs via common programming idioms. In short, the heap is, in practice, a simple structure constructed out of a small number of simple structures. Our findings imply that garbage collection and program analysis may achieve a high return by focusing on simple heap structures.

PDF file

Details