Collecting a Heap of Shapes

This talk highlights results from an empirical study of the heap structures and sharing relations that appear in large real-world programs. The aim of this study was to identify what types of structures/sharing relations occur frequently and are critical to understanding the behavior of a program – with an additional goal of identifying a set of properties that can be used to guide the design of static analysis tools or type/annotation systems. This study utilized a novel approach to understanding heap structures. Instead of viewing the heap as a large set of individual objects this work attempts to identify sets of objects (conceptual regions) that all have the same roles in the program and examines the heap at this higher level of abstraction. The results shed light onto the use and importance of recursive data-structures, aggregation, the frequency of sharing, and the sharing patterns that occur in real-world programs. In particular the results show that the heap, in practice and from the viewpoint of conceptual regions, is a relatively simple structure where the vast majority of sharing (aliasing) and shapes that are present can be described by a small number of simple concepts that are closely related to standard programming idioms.

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.

Series:
Microsoft Research Talks
Date:
Speakers:
Mark Marron
Affiliation:
Imdea-Software research

Series: Microsoft Research Talks