A locality-improving dynamic memory allocator

ABSTRACT

In general-purpose applications, most data is dynamically allocated. The memory manager therefore plays a crucial role in application performance by determining the spatial locality of heap objects. Previous general-purpose allocators have focused on reducing fragmentation, while most locality-improving allocators have either focused on improving the locality of the allocator (not the application), or required programmer hints or profiling to guide object placement. We present a high-performance memory allocator called Vam that transparently improves both cache-level and page-level locality of the application while achieving low fragmentation. Over a range of large-footprint benchmarks, Vam improves application performance by an average of 4%-8% versus the Lea (Linux) and FreeBSD allocators. When memory is scarce, Vam improves application performance by up to 2X compared to the FreeBSD allocator, and by over 10X compared to the Lea allocator.

REFERENCES

• 1: David F. Bacon , Perry Cheng , V. T. Rajan, Controlling fragmentation and space consumption in the metronome, a real-time garbage collector for Java, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 2: David A. Barrett , Benjamin G. Zorn, Using lifetime predictors to improve memory allocation performance, ACM SIGPLAN Notices, v.28 n.6, p.187-196, June 1993
• 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: 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: D. Black, J. Carter, G. Feinberg, R. MacDonald, S. Mangalat, E. Sheinbrood, J. Sciver, and P. Wang. OSF/1 virtual memory improvements. In Proceedings of the USENIX Mac Symposium, pages 87--103, November 1991.
• 7: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 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: Dirk Grunwald , Benjamin Zorn , Robert Henderson, Improving the cache locality of memory allocation, ACM SIGPLAN Notices, v.28 n.6, p.177-186, June 1993
• 10: D. R. Hanson. A portable storage management system for the Icon programming language. Software Practice and Experience, 10(6):489--500, 1980.
• 11: IA-32 Intel architecture software developer's manual, volume 3: System programming guide. ftp://download.intel.com/design/Pentium4/manuals/25366814.pdf.
• 12: Mark Stuart Johnstone , Paul R. Wilson, Non-compacting memory allocation and real-time garbage collection, 1997
• 13: 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
• 14: P.-H. Kamp. Malloc(3) revisited. http://phk.freebsd.dk/pubs/malloc.pdf.
• 15: Scott F. Kaplan , Yannis Smaragdakis , Paul R. Wilson, Flexible reference trace reduction for VM simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.1, p.1-38, January 2003 [doi>10.1145/778553.778554]
• 16: D. Lea. A memory allocator. http://gee.cs.oswego.edu/dl/html/malloc.html.
• 17: M. Pettersson. The perfctr patch for Linux and the perfex tool. http://user.it.uu.se/~mikpe/linux/perfctr/.
• 18: Mathew L. Seidl , Benjamin G. Zorn, Implemting heap-object behavior prediction efficiently and effectively, Software—Practice & Experience, v.31 n.9, p.869-892, July 25,2001 [doi>10.1002/spe.375.abs]
• 19: SPEC CPU2000. http://www.spec.org/osg/cpu2000/.
• 20: SPEC CPU2000 memory footprint. http://www.spec.org/osg/cpu2000/analysis/memory/.
• 21: 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
• 22: 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
• 23: Ting Yang , Matthew Hertz , Emery D. Berger , Scott F. Kaplan , J. Eliot B. Moss, Automatic heap sizing: taking real memory into account, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029881]
• 24: 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

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

General Terms:
Algorithms, Languages, Performance

Keywords:
allocator, cache locality, fragmentation, memory management, paging, vam, virtual memory