Abstract
Object-oriented programs often require large heaps to run properly or meet performance goals. They use high-overhead collections, bulky data models, and large caches. Discovering this is quite challenging. Manual browsing and flat summaries do not scale to complex graphs with 20 million objects. Context is crucial to understanding responsibility and inefficient object connectivity.
We summarize memory footprint with help from the dominator relation. Each dominator tree captures unique ownership. Edges between trees capture responsibility. We introduce a set of ownership structures, and quantify their abundance. We aggregate these structures, and use thresholds to identify important aggregates. We introduce the ownership graph to summarize responsibility, and backbone equivalence to aggregate patterns within trees. Our implementation quickly generates concise summaries. In two minutes, it generates a 14-node ownership graph from 29 million objects. Backbone equivalence identifies a handful of patterns that account for 80% of a tree’s footprint.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aldrich, J., Chambers, C.: Ownership Domains: Separating Aliasing Policy from Mechanism. In: Odersky, M. (ed.) ECOOP 2004. LNCS, vol. 3086, pp. 1–25. Springer, Heidelberg (2004)
Aldrich, J., Kostadinov, V., Chambers, C.: Alias annotations for program understanding. Object-oriented Programming, Systems, Languages, and Applications (2002)
Borland Software Corporation: OptimizeItTM Enterprise Suite (2005), http://www.borland.com/us/products/optimizeit
Boyapati, C., Lee, R., Rinard, M.: Ownership types for safe programming: preventing data races and deadlocks. Object-oriented Programming, Systems, Languages, and Applications (2002)
Boyapati, C., Liskov, B., Shrira, L.: Ownership types for object encapsulation. In: Symposium on Principles of Programming Languages (2003)
Clack, C., Clayman, S., Parrott, D.: Lexical profiling: Theory and practice. Journal of Functional Programming 5(2), 225–277 (1995)
Clarke, D., Wrigstad, T.: External uniqueness is unique enough. In: Cardelli, L. (ed.) ECOOP 2003. LNCS, vol. 2743, pp. 176–200. Springer, Heidelberg (2003)
Clarke, D.G., Noble, J., Potter, J.M.: Simple Ownership Types for Object Containment. In: Knudsen, J.L. (ed.) ECOOP 2001. LNCS, vol. 2072, pp. 53–76. Springer, Heidelberg (2001)
Corbera, F., Asenjo, R., Zapata, E.L.: A framework to capture dynamic data structures in pointer-based codes. IEEE Transactions on Parallel and Distributed Systems 15(2), 151–166 (2004)
De Pauw, W., Sevitsky, G.: Visualizing reference patterns for solving memory leaks in Java. Concurrency: Practice and Experience 12, 1431–1454 (2000)
Dietl, W., Müller, P.: Universes: Lightweight ownership for JML. Special Issue: ECOOP 2004 Workshop FTfJP, Journal of Object Technology 4(8), 5–32 (2005)
Ghiya, R., Hendren, L.J.: Is it a tree, a DAG, or a cyclic graph? a shape analysis for heap-directed pointers in c. In: Symposium on Principles of Programming Languages (1996)
Hastings, R., Joynce, B.: Purify — fast detection of memory leaks and access errors. In: USENIX Proceedings, pp. 125–136 (1992)
Hill, T., Noble, J., Potter, J.: Scalable visualizations of object-oriented systems with ownership trees. Journal of Visual Languages and Computing 13, 319–339 (2002)
Hirzel, M., Hinkel, J., Diwan, A., Hind, M.: Understanding the connectivity of heap objects. In: International Symposium on Memory Management (2002)
Hitchens, R.: Java NIO, 1st edn. O’Reilly Media, Inc., Sebastopol (2002)
Holzner, S.: Eclipse, 1st edn. O’Reilly Media, Inc., Sebastopol (2004)
IBM Corporation: Rational PurifyPlus (2005)
Jeannet, B., Loginov, A., Reps, T., Sagiv, M.: A relational approach to interprocedural shape analysis. In: International Static Analysis Symposium. LNCS, Springer, New York (2004)
Lattner, C., Adve, V.: Data structure analysis: A fast and scalable context-sensitive heap analysis. Technical Report UIUCDCS-R-2003-2340, Computer Science Deptartment, University of Illinois (2003)
Lattner, C., Adve, V.: Automatic pool allocation: Improving performance by controlling data structure layout in the heap. In: Programming Language Design and Implementation, Chicago, IL, pp. 129–142 (2005)
Lengauer, T., Tarjan, R.E.: A fast algorithm for finding dominators in a flow graph. ACM Transactions on Programming Languages and Systems 1(1), 121–141 (1979)
Mitchell, N., Sevitsky, G.: Leakbot: An automated and lightweight tool for diagnosing memory leaks in large Java applications. In: Cardelli, L. (ed.) ECOOP 2003. LNCS, vol. 2743, pp. 351–377. Springer, Heidelberg (2003)
Parkinson, M., Bierman, G.: Separation logic and abstraction. In: Symposium on Principles of Programming Languages (2005)
Pheng, S., Verbrugge, C.: Dynamic shape and data structure analysis in java. Technical Report 2005-3, School of Computer Science, McGill University (2005)
Pollet, I., Charlier, B.L., Cortesi, A.: Distinctness and Sharing Domains for Static Analysis of Java Programs. In: Knudsen, J.L. (ed.) ECOOP 2001. LNCS, vol. 2072, pp. 77–98. Springer, Heidelberg (2001)
Potanin, A.: The Fox — a tool for object graph analysis. Undergraduate Honors Thesis (2002)
Potanin, A., Noble, J., Biddle, R.: Checking ownership and confinement. Concurrency and Computation: Practice and Experience 16(7), 671–687 (2004)
Potanin, A., Noble, J., Biddle, R.: Snapshot query-based debugging. In: Australian Software Engineering Conference, Melbourne, Australia (2004)
Potanin, A., Noble, J., Frean, M., Biddle, R.: Scale-free geometry in object-oriented programs. Communications of the ACM (2005)
Quest Software: JProbe® Memory Debugger (2005), http://www.quest.com/jprobe
Raman, E., August, D.I.: Recursive data structure profiling. In: ACM SIGPLAN Workshop on Memory Systems Performance (2005)
Rayside, D., Mendel, L., Jackson, D.: A dynamic analysis for revealing object ownership and sharing. In: Workshop on Dynamic Analysis (2006)
Rojemo, N., Runciman, C.: Lag, drag, void and use — heap profiling and space-efficient compilation revisited. In: International Conference on Functional Programming, pp. 34–41 (1996)
Runciman, C., Rojemo, N.: New dimensions in heap profiling. Journal of Functional Programming 6(4), 587–620 (1996)
Sansom, P.M., Peyton Jones, S.L.: Time and space profiling for non-strict higher-order functional languages. In: Symposium on Principles of Programming Languages, San Francisco, CA, pp. 355–366 (1995)
Sansom, P.M., Peyton Jones, S.L.: Formally based profiling for higher-order functional languages. ACM Transactions on Programming Languages and Systems 19(2), 334–385 (1997)
Shaham, R., Kolodner, E.K., Sagiv, M.: Automatic removal of array memory leaks in java. Computational Complexity, 50–66 (2000)
Shaham, R., Kolodner, E.K., Sagiv, M.: Estimating the impact of heap liveness information on space consumption in Java. In: International Symposium on Memory Management (2002)
Shaham, R., Kolodner, E.K., Sagiv, S.: Heap profiling for space-efficient java. In: Programming Language Design and Implementation, pp. 104–113 (2001)
SPEC Corporation: The SPEC JVM Client98 benchmark suite (1998), http://www.spec.org/osg/jvm98
Sun Microsystems: Heap Analysis Tool (2002), https://hat.dev.java.net/
Sun Microsystems: HPROF JVM profiler (2005), http://java.sun.com/developer/technicalArticles/Programming/HPROF.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mitchell, N. (2006). The Runtime Structure of Object Ownership. In: Thomas, D. (eds) ECOOP 2006 – Object-Oriented Programming. ECOOP 2006. Lecture Notes in Computer Science, vol 4067. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11785477_5
Download citation
DOI: https://doi.org/10.1007/11785477_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35726-1
Online ISBN: 978-3-540-35727-8
eBook Packages: Computer ScienceComputer Science (R0)