Collecting a heap of shapes

Earl T. Barr, Christian Bird, Mark Marron

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publication2013 International Symposium on Software Testing and Analysis, ISSTA 2013 - Proceedings
Pages123-133
Number of pages11
DOIs
StatePublished - 2013
Event22nd International Symposium on Software Testing and Analysis, ISSTA 2013 - Lugano, Switzerland
Duration: Jul 15 2013Jul 20 2013

Publication series

Name2013 International Symposium on Software Testing and Analysis, ISSTA 2013 - Proceedings

Conference

Conference22nd International Symposium on Software Testing and Analysis, ISSTA 2013
Country/TerritorySwitzerland
CityLugano
Period7/15/137/20/13

Keywords

  • Dynamic Analysis
  • Heap Structure

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Collecting a heap of shapes'. Together they form a unique fingerprint.

Cite this