Clustering the heap in multi-threaded applications for improved garbage collection

ABSTRACT

Garbage collection can be a performance bottleneck in large distributed, multi-threaded applications. Applications may produce millions of objects during their lifetimes and may invoke hundreds or thousands of threads. When using a single shared heap, each time a garbage collection phase occurs all threads must be stopped, essentially halting all other processing. Attempts to fix this bottleneck include creating a single heap per thread, however this may not scale to large thread intensive applications. In this paper we explore the potential of clustering threads into related sub-heaps. We hypothesize that this will lead to a smaller shared heap, while maintaining good garbage collection parallelism. We leverage results from software module clustering to achieve this goal. Our results show that we can significantly reduce the number of sub-heaps created and reduce the number of objects in the shared heap in a representative application. This suggests that clustering may be a promising optimization technique for garbage collection in large multi-threaded systems with many shared objects.

REFERENCES

• 1: Matthew Arnold , Adam Welc , V. T. Rajan, Improving virtual machine performance using a cross-run profile repository, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 2: Godmar Back , Wilson C. Hsieh, The KaffeOS Java runtime system, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.4, p.583-630, July 2005 [doi>10.1145/1075382.1075383]
• 3: Stephen M. Blackburn , Sharad Singhai , Matthew Hertz , Kathryn S. McKinely , J. Eliot B. Moss, Pretenuring for Java, ACM SIGPLAN Notices, v.36 n.11, p.342-352, 11/01/2001
• 4: Bruno Blanchet, Escape analysis for Java^TM: Theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.6, p.713-775, November 2003 [doi>10.1145/945885.945886]
• 5: D. Browning. Integrate .NET remoting into the enterprise. In .NET Magazine, November 2002.
• 6: David Conger, Remoting with C# and .NET: Remote Objects for Distributed, John Wiley & Sons, Inc., New York, NY, 2002
• 7: Tamar Domani , Gal Goldshtein , Elliot K. Kolodner , Ethan Lewis , Erez Petrank , Dafna Sheinwald, Thread-local heaps for Java, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 8: L. Dykstra, W. Srisa-an, and J. M. Chang. An analysis of the garbage collection performance in Sun's HotSpot JVM. In Proceedings of the IEEE International Performance Computing and Communications Conference, pages 335--339, 2002.
• 9: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 10: Mark Harman , Stephen Swift , Kiarash Mahdavi, An empirical study of the robustness of two module clustering fitness functions, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068184]
• 11: Matthew Hertz , Stephen M Blackburn , J Eliot B Moss , Kathryn S. McKinley , Darko Stefanović, Error-free garbage collection traces: how to cheat and not get caught, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 12: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 13: Per-Åke Larson , Murali Krishnan, Memory allocation for long-running server applications, Proceedings of the 1st international symposium on Memory management, p.176-185, October 17-19, 1998, Vancouver, British Columbia, Canada
• 14: Chia-Tien Dan Lo , Witawas Srisa-an , J. Morris Chang, A Multithreaded Concurrent Garbage Collector Parallelizing the New Instruction in Java, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.19, April 15-19, 2002
• 15: Mathew MacDonald, Peer-to-Peer with VB.NET, APress L. P., 2003
• 16: Kiarash Mahdavi , Mark Harman , Robert Mark Hierons, A Multiple Hill Climbing Approach to Software Module Clustering, Proceedings of the International Conference on Software Maintenance, p.315, September 22-26, 2003
• 17: S. Mancoridis , B. S. Mitchell , Y. Chen , E. R. Gansner, Bunch: A Clustering Tool for the Recovery and Maintenance of Software System Structures, Proceedings of the IEEE International Conference on Software Maintenance, p.50, August 30-September 03, 1999
• 18: Brian Scott Mitchell , Spiros Mancoridis, A heuristic search approach to solving the software clustering problem, 2002
• 19: Brian S. Mitchell , Spiros Mancoridis , Martin Traverso, Search based reverse engineering, Proceedings of the 14th international conference on Software engineering and knowledge engineering, July 15-19, 2002, Ischia, Italy [doi>10.1145/568760.568835]
• 20: K. Nilsen and W. Schmidt. A high-performance hardware-assisted real-time garbage collection system. Journal of Programming Languages, pages 1--40, 1994.
• 21: David J. Roth , David S. Wise, One-bit counts between unique and sticky, Proceedings of the 1st international symposium on Memory management, p.49-56, October 17-19, 1998, Vancouver, British Columbia, Canada
• 22: Witawas Srisa-an , Chia-Tien Dan Lo , Ji-en Morris Chang, Active Memory Processor: A Hardware Garbage Collector for Real-Time Java Embedded Devices, IEEE Transactions on Mobile Computing, v.2 n.2, p.89-101, January 2003 [doi>10.1109/TMC.2003.1217230]
• 23: Bjarne Steensgaard, Thread-specific heaps for multi-threaded programs, Proceedings of the 2nd international symposium on Memory management, p.18-24, October 15-16, 2000, Minneapolis, Minnesota, United States
• 24: David Stutz , Ted Neward , Geoff Shilling, Shared Source Cli Essentials, O'Reilly & Associates, Inc., Sebastopol, CA, 2002
• 25: A. Tucker, S. Swift, and X. Liu. Variable grouping in multivariate time series via correlation. IEEE Transactions on Systems, Man and Cybernetics, Part B, 31(2):235--245, 2001.
• 26: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
garbage collection, heap clustering, hill climbing, search based software engineering, virtual machines