Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

As hardware complexity increases and virtualization is added at more layers of the execution stack, predicting the performance impact of optimizations becomes increasingly difficult. Production compilers and virtual machines invest substantial development effort in performance tuning to achieve good performance for a range of benchmarks. Although optimizations typically perform well on average, they often have unpredictable impact on running time, sometimes degrading performance significantly. Today's VMs perform sophisticated feedback-directed optimizations, but these techniques do not address performance degradations, and they actually make the situation worse by making the system more unpredictable.This paper presents an online framework for evaluating the effectiveness of optimizations, enabling an online system to automatically identify and correct performance anomalies that occur at runtime. This work opens the door for a fundamental shift in the way optimizations are developed and tuned for online systems, and may allow the body of work in offline empirical optimization search to be applied automatically at runtime. We present our implementation and evaluation of this system in a product Java VM.

REFERENCES

• 1: A.-R. Adl-Tabatabai, J. Bharadwaj, D.-Y. Chen, A. Ghuloum, V. Menon, B. Murphy, M. Serrano, and T. Shpeisman. The Star-JIT compiler: A dynamic compiler for managed runtime environments. Intel Technology Journal, 7(1):19--31, Feb. 2003.
• 2: Ali-Reza Adl-Tabatabai , Richard L. Hudson , Mauricio J. Serrano , Sreenivas Subramoney, Prefetch injection based on hardware monitoring and object metadata, ACM SIGPLAN Notices, v.39 n.6, May 2004
• 3: F. Agakov , E. Bonilla , J. Cavazos , B. Franke , G. Fursin , M. F. P. O'Boyle , J. Thomson , M. Toussaint , C. K. I. Williams, Using Machine Learning to Focus Iterative Optimization, Proceedings of the International Symposium on Code Generation and Optimization, p.295-305, March 26-29, 2006 [doi>10.1109/CGO.2006.37]
• 4: A. W. Appel, Simple generational garbage collection and fast allocation, Software—Practice & Experience, v.19 n.2, p.171-183, February 1989 [doi>10.1002/spe.4380190206]
• 5: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, ACM SIGPLAN Notices, v.35 n.10, p.47-65, Oct. 2000
• 6: M. Arnold, S. J. Fink, D. Grove, M. Hind, and P. F. Sweeney. A survey of adaptive optimization in virtual machines. Proceedings of the IEEE, 93(2), 2005. Special issue on Program Generation, Optimization, and Adaptation.
• 7: Matthew Arnold , Barbara G. Ryder, A framework for reducing the cost of instrumented code, ACM SIGPLAN Notices, v.36 n.5, p.168-179, May 2001
• 8: David F. Bacon , Ravi Konuru , Chet Murthy , Mauricio Serrano, Thin locks: featherweight synchronization for Java, ACM SIGPLAN Notices, v.33 n.5, p.258-268, May 1998
• 9: Jeff Bilmes , Krste Asanovic , Chee-Whye Chin , Jim Demmel, Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology, Proceedings of the 11th international conference on Supercomputing, p.340-347, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263662]
• 10: John Cavazos , J. Eliot , B. Moss, Inducing heuristics to decide whether to schedule, ACM SIGPLAN Notices, v.39 n.6, May 2004
• 11: Chun Chen , Jacqueline Chame , Mary Hall, Combining Models and Guided Empirical Search to Optimize for Multiple Levels of the Memory Hierarchy, Proceedings of the international symposium on Code generation and optimization, p.111-122, March 20-23, 2005 [doi>10.1109/CGO.2005.10]
• 12: H. Chen, J. Lu, W.-C. Hsu, and P.-C. Yew. Continuous adaptive objectcode re-optimization framework. In Ninth Asia-Pacific Computer Systems Architecture, Sept. 2004.
• 13: Bruce Childers , Jack W. Davidson , Mary Lou Soffa, Continuous Compilation: A New Approach to Aggressive and Adaptive Code Transformation, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.205.1, April 22-26, 2003
• 14: Trishul M. Chilimbi , Martin Hirzel, Dynamic hot data stream prefetching for general-purpose programs, ACM SIGPLAN Notices, v.37 n.5, May 2002
• 15: http://www-plan.cs.colorado.edu/henkel/projects/colorado bench.
• 16: Keith D. Cooper , Philip J. Schielke , Devika Subramanian, Optimizing for reduced code space using genetic algorithms, Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, p.1-9, May 05-05, 1999, Atlanta, Georgia, United States
• 17: Keith D. Cooper , Devika Subramanian , Linda Torczon, Adaptive Optimizing Compilers for the 21st Century, The Journal of Supercomputing, v.23 n.1, p.7-22, August 2002 [doi>10.1023/A:1015729001611]
• 18: http://pag.csail.mit.edu/daikon.
• 19: Jeffrey Dean , Craig Chambers, Towards better inlining decisions using inlining trials, Proceedings of the 1994 ACM conference on LISP and functional programming, p.273-282, June 27-29, 1994, Orlando, Florida, United States
• 20: L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
• 21: Pedro C. Diniz , Martin C. Rinard, Dynamic feedback: an effective technique for adaptive computing, ACM SIGPLAN Notices, v.32 n.5, p.71-84, May 1997
• 22: Matteo Frigo, A fast Fourier transform compiler, ACM SIGPLAN Notices, v.34 n.5, p.169-180, May 1999
• 23: M. Frigo and S. G. Johnson. FFTW: An adaptive software architecture for the FFT. In 1998 IEEE International Conference on Acoustics Speech and Signal Processing, volume 3, pages 1381--1384. IEEE, 1998.
• 24: G. Fursin, A. Cohen, M. O'Boyle, and O. Temam. A practical method for quickly evaluating program optimizations. In Proceedings of the 1st International Conference on High Performance Embedded Architectures & Compilers (HiPEAC 2005), number 3793 in LNCS, pages 29--46. Springer Verlag, November 2005.
• 25: N. Grcevski, A. Kilstra, K. Stoodley, M. Stoodley, and V. Sundaresan. Java just-in-time compiler and virtual machine improvements for server and middleware applications. In 3rd Virtual Machine Research and Technology Symposium (VM), May 2004.
• 26: Gilbert Joseph Hansen, Adaptive systems for the dynamic run-time optimization of programs., 1974
• 27: M. Hirzel, A. Diwan, and M. Hind. Pointer analysis in the pressence of dynamic class loading. In 18th European Conference on Object-Oriented Programming (ECOOP), volume 3086 of LNCS, pages 96--122, June 2004.
• 28: Urs Hölzle , Craig Chambers , David Ungar, Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches, Proceedings of the European Conference on Object-Oriented Programming, p.21-38, July 15-19, 1991
• 29: Urs Hölzle , David Ungar, Reconciling responsiveness with performance in pure object-oriented languages, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.355-400, July 1996 [doi>10.1145/233561.233562]
• 30: Xianglong Huang , Stephen M. Blackburn , Kathryn S. McKinley , J Eliot B. Moss , Zhenlin Wang , Perry Cheng, The garbage collection advantage: improving program locality, ACM SIGPLAN Notices, v.39 n.10, October 2004
• 31: Eun-Jin Im , Katherine A. Yelick, Optimizing Sparse Matrix Computations for Register Reuse in SPARSITY, Proceedings of the International Conference on Computational Sciences-Part I, p.127-136, May 28-30, 2001
• 32: Eun-Jin Im , Katherine Yelick , Richard Vuduc, Sparsity: Optimization Framework for Sparse Matrix Kernels, International Journal of High Performance Computing Applications, v.18 n.1, p.135-158, February 2004 [doi>10.1177/1094342004041296]
• 33: Kazuaki Ishizaki , Mikio Takeuchi , Kiyokuni Kawachiya , Toshio Suganuma , Osamu Gohda , Tatsushi Inagaki , Akira Koseki , Kazunori Ogata , Motohiro Kawahito , Toshiaki Yasue , Takeshi Ogasawara , Tamiya Onodera , Hideaki Komatsu , Toshio Nakatani, Effectiveness of cross-platform optimizations for a java just-in-time compiler, ACM SIGPLAN Notices, v.38 n.11, November 2003
• 34: Thomas Kistler , Michael Franz, Automated data-member layout of heap objects to improve memory-hierarchy performance, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.490-505, May 2000 [doi>10.1145/353926.353937]
• 35: Thomas Kistler , Michael Franz, Continuous Program Optimization: Design and Evaluation, IEEE Transactions on Computers, v.50 n.6, p.549-566, June 2001 [doi>10.1109/12.931893]
• 36: Prasad A. Kulkarni , David B. Whalley , Gary S. Tyson , Jack W. Davidson, Exhaustive Optimization Phase Order Space Exploration, Proceedings of the International Symposium on Code Generation and Optimization, p.306-318, March 26-29, 2006 [doi>10.1109/CGO.2006.15]
• 37: Prasad A. Kulkarni , Stephen R. Hines , David B. Whalley , Jason D. Hiser , Jack W. Davidson , Douglas L. Jones, Fast and efficient searches for effective optimization-phase sequences, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.2, p.165-198, June 2005 [doi>10.1145/1071604.1071607]
• 38: Xiaoming Li , Maria Jesus Garzaran , David Padua, Optimizing Sorting with Genetic Algorithms, Proceedings of the international symposium on Code generation and optimization, p.99-110, March 20-23, 2005 [doi>10.1109/CGO.2005.24]
• 39: Vijay Sundaresan , Daryl Maier , Pramod Ramarao , Mark Stoodley, Experiences with Multi-threading and Dynamic Class Loading in a Java Just-In-Time Compiler, Proceedings of the International Symposium on Code Generation and Optimization, p.87-97, March 26-29, 2006 [doi>10.1109/CGO.2006.16]
• 40: Priya Nagpurkar , Chandra Krintz , Michael Hind , Peter F. Sweeney , V. T. Rajan, Online Phase Detection Algorithms, Proceedings of the International Symposium on Code Generation and Optimization, p.111-123, March 26-29, 2006 [doi>10.1109/CGO.2006.26]
• 41: N. Nethercote, D. Burger, and K. S. McKinley. Self-evaluating compilation applied to loop unrolling. Technical Report TR-06-12, The University of Texas at Austin, Feb. 2006.
• 42: M. Paleczny, C. Vick, and C. Click. The Java Hotspot server compiler. In Java Virtual Machine Research and Technology Symposium (JVM), pages 1--12, Apr. 2001.
• 43: M. Püschel, J. M. F. Moura, J. Johnson, D. Padua, M. Veloso, B. W. Singer, J. Xiong, F. Franchetti, A. Gačić, Y. Voronenko, K. Chen, R. W. Johnson, and N. Rizzolo. SPIRAL: Code generation for DSP transforms. Proceedings of the IEEE, 93(2), 2005. Special issue on Program Generation, Optimization, and Adaptation.
• 44: Rodric M. Rabbah , Krishna V. Palem, Data remapping for design space optimization of embedded memory systems, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.2, p.186-218, May 2003 [doi>10.1145/643470.643474]
• 45: Rafael H. Saavedra , Daeyeon Park, Improving the Effectiveness of Software Prefetching with Adaptive Execution, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.68, October 20-23, 1996
• 46: http://www.sable.mcgill.ca/software/#soot.
• 47: Standard Performance Evaluation Corporation. SPECjbb2000 Java Business Benchmark. http://www.spec.org/jbb2000.
• 48: Standard Performance Evaluation Corporation. SPECjvm98 Benchmarks. http://www.spec.org/jvm98.
• 49: Mark Stephenson , Saman Amarasinghe, Predicting Unroll Factors Using Supervised Classification, Proceedings of the international symposium on Code generation and optimization, p.123-134, March 20-23, 2005 [doi>10.1109/CGO.2005.29]
• 50: Toshio Suganuma , Toshiaki Yasue , Motohiro Kawahito , Hideaki Komatsu , Toshio Nakatani, A dynamic optimization framework for a Java just-in-time compiler, ACM SIGPLAN Notices, v.36 n.11, p.180-195, 11/01/2001
• 51: The DaCapo Project. DaCapo Benchmark Suite, version beta051009. http://www-ali.cs.umass.edu/DaCapo/gcbm.html.
• 52: Nathan Thomas , Gabriel Tanase , Olga Tkachyshyn , Jack Perdue , Nancy M. Amato , Lawrence Rauchwerger, A framework for adaptive algorithm selection in STAPL, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065981]
• 53: S. Triantafyllis, M. Vachharajani, and D. August. Compiler optimization-space exploration. Journal of Instruction-Level Parallelism, 7:1--25, Jan. 2005.
• 54: Michael J. Voss , Rudolf Eigemann, High-level adaptive program optimization with ADAPT, ACM SIGPLAN Notices, v.36 n.7, p.93-102, July 2001
• 55: R. C. Whaley, A. Petitet, and J. J. Dongarra. Automated empirical optimizations of software and the ATLAS project. Parallel Computing, 27(1-2):3--35, 2001.
• 56: http://xml.apache.org/xerces2-j/index.html.
• 57: Kamen Yotov , Xiaoming Li , Gang Ren , Michael Cibulskis , Gerald DeJong , Maria Garzaran , David Padua , Keshav Pingali , Paul Stodghill , Peng Wu, A comparison of empirical and model-driven optimization, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Code generation; Run-time environments

General Terms:
Languages, Performance

Keywords:
Java, feedback-directed optmizations, virtual machines