TY - GEN
T1 - Collecting a heap of shapes
AU - Barr, Earl T.
AU - Bird, Christian
AU - Marron, Mark
PY - 2013
Y1 - 2013
N2 - The program heap is fundamentally a simple mathematical concept - a set of objects and a connectivity relation on them. However, a large gap exists between the set of heap structures that could be constructed and those that programmers actually build. To understand this gap, we empirically study heap structures and sharing relations in large object-oriented programs. To scale and make sense of real world heaps, any analysis must employ abstraction; our abstraction groups sets of objects by role and the aliasing present in pointer sets. We find that the heaps of real-world programs are, in practice, fundamentally simple structures that are largely constructed from a small number of simple structures and sharing idioms, such as the sharing of immutable or unique (e.g., singleton) objects. For instance, we find that, under our abstraction, 53 - 75% of pointers build tree structures and we classify all but 7 - 18% of aliasing pointers. These results provide actionable information for rethinking the design of annotation systems, memory allocation/collection, and program analyses.
AB - The program heap is fundamentally a simple mathematical concept - a set of objects and a connectivity relation on them. However, a large gap exists between the set of heap structures that could be constructed and those that programmers actually build. To understand this gap, we empirically study heap structures and sharing relations in large object-oriented programs. To scale and make sense of real world heaps, any analysis must employ abstraction; our abstraction groups sets of objects by role and the aliasing present in pointer sets. We find that the heaps of real-world programs are, in practice, fundamentally simple structures that are largely constructed from a small number of simple structures and sharing idioms, such as the sharing of immutable or unique (e.g., singleton) objects. For instance, we find that, under our abstraction, 53 - 75% of pointers build tree structures and we classify all but 7 - 18% of aliasing pointers. These results provide actionable information for rethinking the design of annotation systems, memory allocation/collection, and program analyses.
KW - Dynamic Analysis
KW - Heap Structure
UR - http://www.scopus.com/inward/record.url?scp=84881274877&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84881274877&partnerID=8YFLogxK
U2 - 10.1145/2483760.2483761
DO - 10.1145/2483760.2483761
M3 - Conference contribution
AN - SCOPUS:84881274877
SN - 9781450321594
T3 - 2013 International Symposium on Software Testing and Analysis, ISSTA 2013 - Proceedings
SP - 123
EP - 133
BT - 2013 International Symposium on Software Testing and Analysis, ISSTA 2013 - Proceedings
T2 - 22nd International Symposium on Software Testing and Analysis, ISSTA 2013
Y2 - 15 July 2013 through 20 July 2013
ER -