Visualising dynamic memory allocators

ABSTRACT

We present generic extensions to the GCspy visualisation frame-work that make it suitable for tracking the way continuous dynamic memory allocators such as dlmalloc or incremental and concurrent garbage collectors make use of heap memory. These extensions include sample-driven client-server communication, in-cremental stream updates and client-controlled stream update frequency. Additional extensions to the current GCspy client are also described. These include hierarchical driver grouping and hierarchical visualisation, zooming, and the ability to define and view relationships between tiles in different spaces. We also introduce a heuristics engine that is responsible for flipping GCspy from its decoupled 'observation' mode to a synchronous 'single-step' mode, and describe a backtrace facility that can trace the server-side call sequence that led to the triggering of a specified event, such as the allocation or freeing of a block of memory. This enables aspects of the allocator (fragmentation, block ordering, splitting and coalescing policies, etc.) to be understood in the context of a particular application and potential optimisations to be identified. The effectiveness of the enhanced framework is demonstrated with a complete integration with dlmalloc. The framework is evaluated in terms of both performance and its ability to explore contrived modifications to dlmalloc's coalescing policy.

REFERENCES

• 1: Doug Lea. A memory allocator. http://gee.cs.oswego.edu/dl/html/malloc.html.
• 2: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 3: GCspy Team. Enhanced GCspy source code. http://www.experimentalstuff.com/Technologies/GCspy/
• 4: Emery D. Berger , Robert D. Blumofe, Hoard: A Fast, Scalable, and Memory-Efficient Allocator for Shared-MemoryMultiprocessors, University of Texas at Austin, Austin, TX, 1999
• 5: Emery D. Berger , Benjamin G. Zorn , Kathryn S. McKinley, Composing high-performance memory allocators, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.114-124, June 2001, Snowbird, Utah, United States
• 6: Emery D. Berger , Benjamin G. Zorn , Kathryn S. McKinley, Reconsidering custom memory allocation, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 7: Henry Lieberman and Carl E. Hewitt. A real-time garbage collector based on the lifetimes of objects. AI Memo 569a, MIT, April 1981.
• 8: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
• 9: Martin Hirzel , Amer Diwan , Matthew Hertz, Connectivity-based garbage collection, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 10: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 11: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 12: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 13: David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-298, January 15-17, 2003, New Orleans, Louisiana, USA
• 14: A. M. Cheadle , A. J. Field , S. Marlow , S. L. Peyton Jones , R. L. While, Exploring the barrier to entry: incremental generational garbage collection for Haskell, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029893]
• 15: Tony Printezis , Richard Jones, GCspy: an adaptable heap visualisation framework, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 16: Richard L. Hudson , J. Eliot B. Moss, Incremental Collection of Mature Objects, Proceedings of the International Workshop on Memory Management, p.388-403, September 17-19, 1992
• 17: Tony Printezis , Alex Garthwaite, Visualising the train garbage collector, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 18: Imperial College GCspy Team. I Spy with my GCspy. http://www.doc.ic.ac.uk/~ajf/Research/publications.html
• 19: HP Labs. The libunwind project. http://www.hpl.hp.com/research/linux/libunwind/.
• 20: Paul R. Wilson , Mark S. Johnstone , Michael Neely , David Boles, Dynamic Storage Allocation: A Survey and Critical Review, Proceedings of the International Workshop on Memory Management, p.1-116, September 27-29, 1995
• 21: DaCapo Project. The DaCapo benchmark suite (versionbeta051009). http://osl-www.cs.umass.edu/DaCapo/gcbm.html.
• 22: Donald E. Knuth. The Art of Computer Programming, volume I: Fundamental Algorithms, chapter 2. Addison-Wesley, second edition, 1973.
• 23: AT&T Research. Graphviz - graph visualization software. http://www.graphviz.org/.
• 24: Ivan Herman , Guy Melançon , M. Scott Marshall, Graph Visualization and Navigation in Information Visualization: A Survey, IEEE Transactions on Visualization and Computer Graphics, v.6 n.1, p.24-43, January 2000 [doi>10.1109/2945.841119]
• 25: OOPSLA'02 ACM Conference on Object-Oriented Systems, Languages and Applications, ACM SIGPLAN Notices, Seattle, WA, November 2002. ACM Press.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)

General Terms:
Algorithms, Human Factors, Languages, Measurement, Performance

Keywords:
dynamic memory allocation, garbage collection, language implementation, memory management, visualisation of objects