Automatic pool allocation: improving performance by controlling data structure layout in the heap

ABSTRACT

This paper describes Automatic Pool Allocation, a transformation framework that segregates distinct instances of heap-based data structures into seperate memory pools and allows heuristics to be used to partially control the internal layout of those data structures. The primary goal of this work is performance improvement, not automatic memory management, and the paper makes several new contributions. The key contribution is a new compiler algorithm for partitioning heap objects in imperative programs based on a context-sensitive pointer analysis, including a novel strategy for correct handling of indirect (and potentially unsafe) function calls. The transformation does not require type safe programs and works for the full generality of C and C++. Second, the paper describes several optimizations that exploit data structure partitioning to further improve program performance. Third, the paper evaluates how memory hierarchy behavior and overall program performance are impacted by the new transformations. Using a number of benchmarks and a few applications, we find that compilation times are extremely low, and overall running times for heap intensive programs speed up by 10-25% in many cases, about 2x in two cases, and more than 10x in two small benchmarks. Overall, we believe this work provides a new framework for optimizing pointer intensive programs by segregating and controlling the layout of heap-based data structures.

REFERENCES

• 1: Alexander Aiken , Manuel Fähndrich , Raph Levien, Better static memory management: improving region-based analysis of higher-order languages, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.174-185, June 18-21, 1995, La Jolla, California, United States
• 2: T. Austin, et al. The Pointer-intensive Benchmark Suite. www.cs.wisc.edu/~austin/ptr-dist.html+, Sept 1995.
• 3: Andrew Ayers , Stuart de Jong , John Peyton , Richard Schooler, Scalable cross-module optimization, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.301-312, June 17-19, 1998, Montreal, Quebec, Canada
• 4: David A. Barrett , Benjamin G. Zorn, Using lifetime predictors to improve memory allocation performance, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.187-196, June 21-25, 1993, Albuquerque, New Mexico, United States
• 5: 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
• 6: 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]
• 7: Greg Bollella , James Gosling, The Real-Time Specification for Java, Computer, v.33 n.6, p.47-54, June 2000 [doi>10.1109/2.846318]
• 8: Chandrasekhar Boyapati , Alexandru Salcianu , William Beebee, Jr. , Martin Rinard, Ownership types for safe region-based memory management in real-time Java, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 9: 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
• 10: Sigmund Cherem , Radu Rugina, Region analysis and transformation for Java programs, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029884]
• 11: Trishul M. Chilimbi , Bob Davidson , James R. Larus, Cache-conscious structure definition, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.13-24, May 01-04, 1999, Atlanta, Georgia, United States
• 12: 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
• 13: Trishul M. Chilimbi , James R. Larus, Using generational garbage collection to implement cache-conscious data placement, ACM SIGPLAN Notices, v.34 n.3, p.37-48, March 1999
• 14: Wei-Ngan Chin , Florin Craciun , Shengchao Qin , Martin Rinard, Region inference for an object-oriented language, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 15: 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]
• 16: Manuvir Das, Unification-based pointer analysis with directional assignments, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.35-46, June 18-21, 2000, Vancouver, British Columbia, Canada
• 17: Robert DeLine , Manuel Fähndrich, Enforcing high-level protocols in low-level software, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.59-69, June 2001, Snowbird, Utah, United States
• 18: Alan Demmers , Mark Weiser , Barry Hayes , Hans Boehm , Daniel Bobrow , Scott Shenker, Combining generational and conservative garbage collection: framework and implementations, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.261-269, December 1989, San Francisco, California, United States [doi>10.1145/96709.96735]
• 19: Dinakar Dhurjati , Sumant Kowshik , Vikram Adve , Chris Lattner, Memory safety without garbage collection for embedded applications, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.1, p.73-111, February 2005 [doi>10.1145/1053271.1053275]
• 20: Manuel Fähndrich , Jakob Rehof , Manuvir Das, Scalable context-sensitive flow analysis using instantiation constraints, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.253-263, June 18-21, 2000, Vancouver, British Columbia, Canada
• 21: David Gay , Alex Aiken, Memory management with explicit regions, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.313-323, June 17-19, 1998, Montreal, Quebec, Canada
• 22: Dan Grossman , Greg Morrisett , Trevor Jim , Michael Hicks , Yanling Wang , James Cheney, Region-based memory management in cyclone, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 23: Dirk Grunwald , Benjamin Zorn, CustoMalloc: efficient synthesized memory allocators, Software—Practice & Experience, v.23 n.8, p.851-869, Aug. 1993 [doi>10.1002/spe.4380230804]
• 24: Niels Hallenberg , Martin Elsman , Mads Tofte, Combining region inference and garbage collection, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 25: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 26: D. R. Hanson, Fast allocation and deallocation of memory based on object lifetimes, Software—Practice & Experience, v.20 n.1, p.5-12, January 1990 [doi>10.1002/spe.4380200104]
• 27: Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379665]
• 28: 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
• 29: 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
• 30: Trevor Jim , J. Greg Morrisett , Dan Grossman , Michael W. Hicks , James Cheney , Yanling Wang, Cyclone: A Safe Dialect of C, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.275-288, June 10-15, 2002
• 31: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 32: Christopher Arthur Lattner , Vikram Adve, Macroscopic data structure analysis and optimization, University of Illinois at Urbana-Champaign, Champaign, IL, 2005
• 33: Chris Lattner , Vikram Adve, Automatic pool allocation for disjoint data structures, Proceedings of the 2002 workshop on Memory system performance, p.13-24, June 16-16, 2002, Berlin, Germany
• 34: Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
• 35: Chris Lattner , Vikram S. Adve, Transparent pointer compression for linked data structures, Proceedings of the 2005 workshop on Memory system performance, June 12-12, 2005, Chicago, Illinois [doi>10.1145/1111583.1111587]
• 36: Donglin Liang , Mary Jean Harrold, Efficient points-to analysis for whole-program analysis, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.199-215, September 06-10, 1999, Toulouse, France
• 37: Donglin Liang , Mary Jean Harrold, Efficient Computation of Parameterized Pointer Information for Interprocedural Analyses, Proceedings of the 8th International Symposium on Static Analysis, p.279-298, July 16-18, 2001
• 38: E. M. Nystrom, H.-S. Kim, and W. mei W. Hwu. Bottom-up and top-down context-sensitive summary-based pointer analysis. In SAS, 2004.
• 39: Anne Rogers , Martin C. Carlisle , John H. Reppy , Laurie J. Hendren, Supporting dynamic data structures on distributed-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.233-263, March 1995 [doi>10.1145/201059.201065]
• 40: P. Rundberg and F. Warg. The FreeBench v1.0 Benchmark Suite. http://www.freebench.org+, Jan 2002.
• 41: 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
• 42: R. Shaham, E. Yahav, E. K. Kolodner, and M. Sagiv. Establishing local temporal heap safety properties with applications to compile-time memory management. In SAS, San Diego, USA, June 2003.
• 43: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 44: Mads Tofte , Lars Birkedal, A region inference algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.4, p.724-767, July 1998 [doi>10.1145/291891.291894]
• 45: Mads Tofte , Jean-Pierre Talpin, Implementation of the typed call-by-value λ-calculus using a stack of regions, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.188-201, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177855]
• 46: Craig B. Zilles, Benchmark health considered harmful, ACM SIGARCH Computer Architecture News, v.29 n.3, p.4-5, June 2001 [doi>10.1145/503205.503206]

INDEX TERMS

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

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

General Terms:
Algorithms, Performance

Keywords:
cache, data layout, pool allocation, recursive data structure, static analysis