Reconsidering custom memory allocation

ABSTRACT

Programmers hoping to achieve performance improvements often use custom memory allocators. This in-depth study examines eight applications that use custom allocators. Surprisingly, for six of these applications, a state-of-the-art general-purpose allocator (the Lea allocator) performs as well as or better than the custom allocators. The two exceptions use regions, which deliver higher performance (improvements of up to 44%). Regions also reduce programmer burden and eliminate a source of memory leaks. However, we show that the inability of programmers to free individual objects within regions can lead to a substantial increase in memory consumption. Worse, this limitation precludes the use of regions for common programming idioms, reducing their usefulness.We present a generalization of general-purpose and region-based allocators that we call reaps. Reaps are a combination of regions and heaps, providing a full range of region semantics with the addition of individual object deletion. We show that our implementation of reaps provides high performance, outperforming other allocators with region-like semantics. We then use a case study to demonstrate the space advantages and software engineering benefits of reaps in practice. Our results indicate that programmers needing fast regions should use reaps, and that most programmers considering custom allocators should instead use the Lea allocator.

REFERENCES

• 1: Apache Foundation. Apache Web server. http://www.apache.org.
• 2: William S. Beebee , Martin C. Rinard, An Implementation of Scoped Memory for Real-Time Java, Proceedings of the First International Workshop on Embedded Software, p.289-305, October 08-10, 2001
• 3: Emery D. Berger , Kathryn S. McKinley , Robert D. Blumofe , Paul R. Wilson, Hoard: a scalable memory allocator for multithreaded applications, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.117-128, November 2000, Cambridge, Massachusetts, United States
• 4: Emery D. Berger , Benjamin G. Zorn , Kathryn S. McKinley, Composing high-performance memory allocators, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.114-124, June 2001, Snowbird, Utah, United States
• 5: James Gosling , Greg Bollella, The Real-Time Specification for Java, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 6: Gilad Bracha , William Cook, Mixin-based inheritance, Proceedings of the European conference on object-oriented programming on Object-oriented programming systems, languages, and applications, p.303-311, September 1990, Ottawa, Canada
• 7: Dov Bulka and David Mayhew. Efficient C++. Addison-Wesley, 2001.
• 8: Trishul M. Chilimbi, Efficient representations and abstractions for quantifying and exploiting data reference locality, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.191-202, June 2001, Snowbird, Utah, United States
• 9: 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
• 10: Margaret A. Ellis , Bjarne Stroustrup, The annotated C++ reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 11: Boris Fomitchev. STLport. http://www.stlport.org/.
• 12: Christopher W. Fraser , David R. Hanson, A Retargetable C Compiler: Design and Implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 13: Free Software Foundation. GCC Home Page. http://gcc.gnu.org/.
• 14: 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
• 15: David Gay , Alex Aiken, Language support for regions, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.70-80, June 2001, Snowbird, Utah, United States
• 16: Wolfram Gloger. Dynamic memory allocator implementations in Linux system libraries. http://www.dent.med.uni-muenchen.de/~wmglo/malloc-slides.html.
• 17: 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
• 18: Sam Guyer, Daniel A. Jiménez, and Calvin Lin. The C-Breeze compiler infrastructure. Technical Report UTCS-TR01-43, The University of Texas at Austin, November 2001.
• 19: 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]
• 20: David R. Hanson. C Interfaces and Implementation. Addison-Wesley, 1997.
• 21: Reed Hastings and Bob Joyce. Purify: Fast detection of memory leaks and access errors. In Proceedings of the Winter USENIX 1992 Conference, pages 125--136, December 1992.
• 22: Mark S. Johnstone , Paul R. Wilson, The memory fragmentation problem: solved?, Proceedings of the 1st international symposium on Memory management, p.26-36, October 17-19, 1998, Vancouver, British Columbia, Canada
• 23: Doug Lea. A memory allocator. http://g.oswego.edu/dl/html/malloc.html.
• 24: Scott Meyers, Effective C++ CD, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 25: Scott Meyers, Effective C++ CD, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 26: Bartosz Milewski. C++ In Action: Industrial-Strength Programming Techniques. Addison-Wesley, 2001.
• 27: Philip A. Nelson. bc - An arbitrary precision calculator language. http://www.gnu.org/software/bc/bc.html.
• 28: Jeffrey M. Richter, Advanced Windows: The Developer's Guide to the WIN32 API for Windows NT 3.5 and Windows 95, Microsoft Press, Redmond, WA, 1995
• 29: Gustavo Rodriguez-Rivera, Conservative garbage collection for general memory allocators, Proceedings of the 2nd international symposium on Memory management, p.71-79, October 15-16, 2000, Minneapolis, Minnesota, United States
• 30: Douglas T. Ross, The AED free storage package, Communications of the ACM, v.10 n.8, p.481-492, Aug. 1967 [doi>10.1145/363534.363546]
• 31: Colin Runciman and Niklas Rojemo. Lag, drag and postmortem heap profiling. In Implementation of Functional Languages Workshop, Bastad, Sweden, September 1995.
• 32: SGI. The Standard Template Library for C++: Allocators. http://www.sgi.com/tech/stl/Allocators.html.
• 33: Ran Shaham , Elliot K. Kolodner , Mooly Sagiv, Heap profiling for space-efficient Java, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.104-113, June 2001, Snowbird, Utah, United States
• 34: Standard Performance Evaluation Corporation. SPEC2000. http://www.spec.org.
• 35: Standard Performance Evaluation Corporation. SPEC95. http://www.spec.org.
• 36: Lincoln Stein , Doug McEachern , Linda Mui, Writing Apache Modules with PERL and C, O'Reilly & Associates, Inc., Sebastopol, CA, 1999
• 37: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 38: Suzanne Pierce. PPRC: Microsoft's Tool Box. http://research.microsoft.com/research/pprc/mstoolbox.asp.
• 39: Mads Tofte , Jean-Pierre Talpin, Region-based memory management, Information and Computation, v.132 n.2, p.109-176, Feb. 1, 1997 [doi>10.1006/inco.1996.2613]
• 40: D. N. Truong , F. Bodin , A. Seznec, Improving Cache Behavior of Dynamically Allocated Data Structures, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.322, October 12-18, 1998
• 41: Kiem-Phong Vo. Vmalloc: A general and efficient memory allocator. In Software Practice & Experience, number 26, pages 1--18. Wiley, 1996.
• 42: M. Weiser , A. Demers , C. Hauser, The portable common runtime approach to interoperability, Proceedings of the twelfth ACM symposium on Operating systems principles, p.114-122, November 1989
• 43: Paul R. Wilson , Mark S. Johnstone , Michael Neely , David Boles, Dynamic Storage Allocation: A Survey and Critical Review, Proceedings of the International Workshop on Memory Management, p.1-116, September 27-29, 1995
• 44: Benjamin Zorn, The measured cost of conservative garbage collection, Software—Practice & Experience, v.23 n.7, p.733-756, July 1993 [doi>10.1002/spe.4380230704]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management

General Terms:
Algorithms, Experimentation, Performance, Reliability