Placement optimization using data context collected during garbage collection

ABSTRACT

We present a study on data context for object-oriented programs. We first introduce several data structures related to data context that can properly organize object fields, object types and the access sequence in a compact manner. Our approach combines the collection of data context with commonly used garbage collectors in a virtual machine environment. The garbage collector maintains extra runtime data for the building of data contexts with minimal overhead. To save memory space and also the time spent on retrieving data, a shorter representation is proposed which sacrifices a small amount of accuracy. To further demonstrate the usefulness of data context for dynamic optimizations, we implemented a placement optimization that captures data accesses that frequently miss, and places relevant objects to reduce data cache misses and improve performance.

The proposed scheme was measured with several benchmarks and in various experimental setups. We demonstrate that building the data context for program understanding and optimization is valuable in a virtual machine environment by using a garbage collector, while adding less than 1% extra overhead.

REFERENCES

• 1: Standard Performance Evaluation Corporation, Java Client/Server Applications. http://www.spec.org/
• 2: Ali-Reza Adl-Tabatabai , Richard L. Hudson , Mauricio J. Serrano , Sreenivas Subramoney, Prefetch injection based on hardware monitoring and object metadata, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 3: M. Arnold and Peter F. Sweeney, "Approximating the calling context tree via sampling." IBM Research Report, July 2000.
• 4: Glenn Ammons , Thomas Ball , James R. Larus, Exploiting hardware performance counters with flow and context sensitive profiling, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.85-96, June 16-18, 1997, Las Vegas, Nevada, United States
• 5: David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994 [doi>10.1145/197405.197406]
• 6: 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
• 7: 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
• 8: Wen-ke Chen , Sanjay Bhansali , Trishul Chilimbi , Xiaofeng Gao , Weihaw Chuang, Profile-guided proactive garbage collection for locality optimization, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 9: 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]
• 10: Trishul M. Chilimbi , Martin Hirzel, Dynamic hot data stream prefetching for general-purpose programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 11: 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
• 12: Nikola Grcevski , Allan Kielstra , Kevin Stoodley , Mark Stoodley , Vijay Sundaresan, Java^TM just-in-time compiler and virtual machine improvements for server and middleware applications, Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium, p.12-12, May 06-07, 2004, San Jose, California
• 13: 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
• 14: M. Hirzel and T. Chilimbi, "Bursty tracing: A framework for low-overhead temporal profiling," In 4th ACM Workshop on Feedback-Directed and Dynamic Optimization (FDDO-4), December 2001
• 15: Xianglong Huang , Stephen M. Blackburn , Kathryn S. McKinley , J Eliot B. Moss , Zhenlin Wang , Perry Cheng, The garbage collection advantage: improving program locality, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 16: IBM. Trade Performance Benchmark, Trade6. https://www14. software.ibm.com/webapp/iwm/web/preLogin.do?source=trade6.
• 17: A. Ibrahim and W. R. Cook. "Automatic prefetching by traversal profiling in object persistence architectures". European Conference for Object-Oriented Programming (ECOOP), 2006.
• 18: Tatsushi Inagaki , Tamiya Onodera , Hideaki Komatsu , Toshio Nakatani, Stride prefetching by dynamically inspecting objects, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 19: Hajime Inoue , Darko Stefanovic , Stephanie Forrest, On the Prediction of Java Object Lifetimes, IEEE Transactions on Computers, v.55 n.7, p.880-892, July 2006 [doi>10.1109/TC.2006.107]
• 20: A. Imai , E. Tick, Evaluation of Parallel Copying Garbage Collection on a Shared-Memory Multiprocessor, IEEE Transactions on Parallel and Distributed Systems, v.4 n.9, p.1030-1040, September 1993 [doi>10.1109/71.243529]
• 21: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 22: Kiyokuni Kawachiya , Kazunori Ogata , Tamiya Onodera, Analysis and reduction of memory inefficiencies in Java strings, Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA
• 23: Chris Lattner , Vikram Adve, Automatic pool allocation: improving performance by controlling data structure layout in the heap, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 24: F. E. Levine , C. P. Roth, A programmer's view of performance monitoring in the PowerPC microprocessor, IBM Journal of Research and Development, v.41 n.3, p.345-356, May 1997
• 25: Erez Petrank , Dror Rawitz, The hardness of cache conscious data placement, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.101-112, January 16-18, 2002, Portland, Oregon
• 26: C. Pospiech, "Hardware Performance Monitoring (HPM) Toolkit". http://www.idris.fr/su/Scalaire/vargas/hpm/HPM_ug.html
• 27: Florian T. Schneider , Mathias Payer , Thomas R. Gross, Online optimizations driven by hardware performance monitoring, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 28: David Siegwart , Martin Hirzel, Improving locality with parallel hierarchical copying GC, Proceedings of the 5th international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada [doi>10.1145/1133956.1133964]
• 29: 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
• 30: Yefim Shuf , Manish Gupta , Hubertus Franke , Andrew Appel , Jaswinder Pal Singh, Creating and preserving locality of java applications at allocation and garbage collection times, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 31: 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
• 32: Stephen Somogyi , Thomas F. Wenisch , Anastassia Ailamaki , Babak Falsafi , Andreas Moshovos, Spatial Memory Streaming, Proceedings of the 33rd annual international symposium on Computer Architecture, p.252-263, June 17-21, 2006
• 33: Mustafa M. Tikir , Jeffery K. Hollingsworth, NUMA-Aware Java Heaps for Server Applications, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.108.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.299]
• 34: Xiaotong Zhuang , Mauricio J. Serrano , Harold W. Cain , Jong-Deok Choi, Accurate, efficient, and adaptive calling context profiling, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada

INDEX TERMS

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

Additional Classification:
  D. Software
  D.m MISCELLANEOUS

General Terms:
Algorithms, Measurement, Performance

Keywords:
data context, data context analysis, placement optimization, program understanding