Creating and preserving locality of java applications at allocation and garbage collection times

ABSTRACT

The growing gap between processor and memory speeds is motivating the need for optimization strategies that improve data locality. A major challenge is to devise techniques suitable for pointer-intensive applications. This paper presents two techniques aimed at improving the memory behavior of pointer-intensive applications with dynamic memory allocation, such as those written in Java. First, we present an allocation time object placement technique based on the recently introduced notion of prolific (frequently instantiated) types. We attempt to co-locate, at allocation time, objects of prolific types that are connected via object references. Then, we present a novel locality based graph traversal technique. The benefits of this technique, when applied to garbage collection (GC), are twofold: (i) it improves the performance of GC due to better locality during a heap traversal and (ii) it restructures surviving objects in a way that enhances locality. On multiprocessors, this technique can further reduce overhead due to synchronization and false sharing. The experimental results, on a well-known suite of Java benchmarks (SPECjvm98 [26], SPECjbb2000 [27], and jOlden [4]), from an implementation of these techniques in the Jikes RVM [1], are very encouraging. The object co-allocation technique improves application performance by up to 21% (10% on average) in the Jikes RVM configured with a non-copying mark-and-sweep collector. The locality-based traversal technique reduces GC times by up to 20% (10% on average) and improves the performance of applications by up to 14% (6% on average) in the Jikes RVM configured with a copying semi-space collector. Both techniques combined can improve application performance by up to 22% (10% on average) in the Jikes RVM configured with a non-copying mark-and-sweep collector.

REFERENCES

• 1: B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 2: A. W. Appel and A. Bendiksen. Vectorized garbage collection. The Journal of Supercomputing, 3:151--160, 1989.
• 3: Hans-J. Boehm, Reducing garbage collector cache misses, Proceedings of the 2nd international symposium on Memory management, p.59-64, October 15-16, 2000, Minneapolis, Minnesota, United States
• 4: Brendon Cahoon , Kathryn S. McKinley, Data Flow Analysis for Software Prefetching Linked Data Structures in Java, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.280-291, September 08-12, 2001
• 5: Brad Calder , Chandra Krintz , Simmi John , Todd Austin, Cache-conscious data placement, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.139-149, October 02-07, 1998, San Jose, California, United States
• 6: 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]
• 7: K. Chevalier, J. Kodumal, and X. Jiang. Memory subsystem optimization for functional languages: A case study. Technical Report, Computer Science Division, University of California, Berkeley, May 2002. Available at http://www.cs.berkeley.edu/~xdjiang/cs252.
• 8: Trishul M. Chilimbi , Mark D. Hill , James R. Larus, Cache-conscious structure layout, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.1-12, May 01-04, 1999, Atlanta, Georgia, United States
• 9: Trishul M. Chilimbi , James R. Larus, Using generational garbage collection to implement cache-conscious data placement, Proceedings of the 1st international symposium on Memory management, p.37-48, October 17-19, 1998, Vancouver, British Columbia, Canada
• 10: Robert Courts, Improving locality of reference in a garbage-collecting memory management system, Communications of the ACM, v.31 n.9, p.1128-1138, Sept. 1988 [doi>10.1145/48529.48536]
• 11: Julian Dolby, Automatic inline allocation of objects, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.7-17, June 16-18, 1997, Las Vegas, Nevada, United States
• 12: Julian Dolby , Andrew A. Chien, An evaluation of automatic object inline allocation techniques, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-20, October 18-22, 1998, Vancouver, British Columbia, Canada
• 13: Julian Dolby , Andrew Chien, An automatic object inlining optimization and its evaluation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.345-357, June 18-21, 2000, Vancouver, British Columbia, Canada
• 14: ECperf. ECperf Home Page. http://java.sun.com/j2ee/ecperf/.
• 15: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 16: Java Grande Forum. The Java Grande Forum Benchmark Suite. Document available at URL http://www.epcc.ed.ac.uk/javagrande/, 2000.
• 17: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 18: M. Karlsson, K. Moore, E. Hagersten, and D. Wood. Memory characterization of the ECperf benchmark. In Proc. of the 2nd Annual Workshop on Memory Performance Issues (WMPI 2002), held in conjunction with the 29th International Symposium on Computer Architecture (ISCA29), Anchorage, Alaska, May 2002.
• 19: Jin-Soo Kim , Yarsun Hsu, Memory system behavior of Java programs: methodology and analysis, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.264-274, June 18-21, 2000, Santa Clara, California, United States
• 20: David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
• 21: Matthew L. Seidl , Benjamin G. Zorn, Segregating heap objects by reference behavior and lifetime, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.12-23, October 02-07, 1998, San Jose, California, United States
• 22: Yefim Shuf , Manish Gupta , Rajesh Bordawekar , Jaswinder Pal Singh, Exploiting prolific types for memory management and optimizations, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.295-306, January 16-18, 2002, Portland, Oregon
• 23: Yefim Shuf , Mauricio J. Serrano , Manish Gupta , Jaswinder Pal Singh, Characterizing the memory behavior of Java workloads: a structured view and opportunities for optimizations, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.194-205, June 2001, Cambridge, Massachusetts, United States
• 24: L. A. Smith and J. M. Bull. A multithreaded Java Grande benchmark suite. In Proc. of the Third Workshop on Java for High Performance Computing, Sorrento, Italy, June 2001.
• 25: Standard Performance Evaluation Council. SPEC jAppServer Development Page. http://www.spec.org/osg/jAppServer/.
• 26: Standard Performance Evaluation Council. SPEC JVM98 Benchmarks, 1998. http://www.spec.org/osg/jvm98/.
• 27: Standard Performance Evaluation Council. SPEC JBB2000 Benchmark, 2000. http://www.spec.org/osg/jbb2000/.
• 28: Sun Microsystems, Inc. SPECjbb2000 Results for Sun-Fire 6800 with HotSpot Server VM on Solaris/SPARC, version 1.3.1-02. http://www.spec.org/osg/jbb2000/results/res2001q4/jbb2000-20011105-00092.html, October 2001.
• 29: Sun Microsystems, Inc. SPECjbb2000 Results for Sun-Fire 6800 with HotSpot Server VM on Solaris/SPARC, version 1.3.1-02 . http://www.spec.org/osg/jbb2000/results/res2001q4/jbb2000-20011128-00097.html, October 2001.
• 30: Paul R. Wilson , Michael S. Lam , Thomas G. Moher, Effective “static-graph” reorganization to improve locality in garbage-collected systems, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.177-191, June 24-28, 1991, Toronto, Ontario, Canada
• 31: E. Yardimci and D. Kaeli. Profile-guided tuning of heap-based memory access. In Proc. of the 2nd Workshop on Memory Performance Issues, Goteberg, Sweden, July 2001.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management
      D.3.4 Processors
          Subjects: Compilers; Run-time environments; Optimization
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection; Allocation/deallocation strategies

General Terms:
Algorithms, Experimentation, Languages, Performance

Keywords:
JVM, Java, garbage collection, heap traversal, locality, locality based graph traversal, memory allocation, memory management, object co-allocation, object placement, prolific types, run-time systems