Two memory allocators that use hints to improve locality

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

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

Two memory allocators that use hints to improve locality

Full text

Pdf (1.15 MB)

Source

International Symposium on Memory Management archive
Proceedings of the 2009 international symposium on Memory management table of contents

Dublin, Ireland

SESSION: Paper session 4 table of contents

Pages: 109-118

Year of Publication: 2009

ISBN:978-1-60558-347-1

Authors

Alin Jula	SAP Labs, Palo Alto, CA, USA
Lawrence Rauchwerger	Texas A&M University, College Station, TX, USA

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 22, Downloads (12 Months): 93, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1542431.1542447 What is a DOI?

ABSTRACT

Dynamic memory allocators affect an application's performance through their data layout quality. They can use an application's allocation hints to improve the spatial locality of this layout. However, a practical approach needs to be automatic, without user intervention. In this paper we present two locality improving allocators, that use allocation hints provided automatically from the C++ STL library to improve an application's spatial locality. When compared to state-of-the-art allocators on seven real world applications, our allocators run on average 7% faster than the Lea allocator, and 17% faster than the FreeBSD's allocator, with the same memory fragmentation as the Lea allocator, one of the best allocators.

While considering locality as an important goal, locality improving allocators must not abandon the existing constraints of fast allocation speed and low fragmentation. These constraints further challenge their design and implementation. We experimentally show that within a memory allocator, allocation speed, memory fragmentation, and spatial locality compete with each other in a game of rock, paper, scissors: when one tries to improve one trait, the others suffer. We conclude that our allocators achieve a good balance of these traits, and they can easily be adjusted to optimize the most important trait for each application.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	International Standard ISO/IEC 14882. Programming Languages -- C++. First edition, 1998.
	2	Aneesh Aggarwal, Software caching vs. prefetching, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
	3	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
	4	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
	5	S. Borkar, P. Dubey, K. Kahn, D. Kuck, H. Mulder, S. Pawlowski, and J. Rattner. Platform 2015: Intel Processor and Platform Evolution for the Next Decade. Technology@Intel Magazine, March, 2005.
	6	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
	7	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
	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	Yi Feng , Emery D. Berger, A locality-improving dynamic memory allocator, Proceedings of the 2005 workshop on Memory system performance, June 12-12, 2005, Chicago, Illinois [doi>10.1145/1111583.1111594]
	10	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
	11	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]
	12	Dirk Grunwald , Benjamin Zorn , Robert Henderson, Improving the cache locality of memory allocation, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.177-186, June 21-25, 1993, Albuquerque, New Mexico, United States
	13	J. Hallberg, T. Palm, and M. Brorsson. Cache-Conscious Allocation of Pointer-Based Data Structures Revisited with HW/SW Prefetching, 2003.
	14	Daniel S. Hirschberg, A class of dynamic memory allocation algorithms, Communications of the ACM, v.16 n.10, p.615-618, Oct. 1973 [doi>10.1145/362375.362392]
	15	Martin Hirzel, Data layouts for object-oriented programs, ACM SIGMETRICS Performance Evaluation Review, v.35 n.1, June 2007
	16	Standard Performance Evaluation Corporation - SPEC - CPU2006. http://www.spec.org/cpu2006.
	17	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
	18	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
	19	A. Jula and L. Rauchwerger. Custom Memory Allocation for Free. In The 19th Workshop on Languages and Compilers for Parallel Computing, New Orleans, Louisiana, USA, 2006. Springer-Verlag Lecture Notes in Computer Science.
	20	Alin Jula. Improving Locality with Dynamic Memory Allocation. PhD thesis, Texas A&M University, College Station, TX, 2008.
	21	Poul-Henning Kamp, Malloc(3) revisited, Proceedings of the annual conference on USENIX Annual Technical Conference, p.36-36, June 15-19, 1998, New Orleans, Louisiana
	22	Scott F. Kaplan , Lyle A. McGeoch , Megan F. Cole, Adaptive caching for demand prepaging, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
	23	Kenneth C. Knowlton, A fast storage allocator, Communications of the ACM, v.8 n.10, p.623-624, Oct. 1965 [doi>10.1145/365628.365655]
	24	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	25	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
	26	Doug Lea. A memory allocator. The C++ Report, 1989.
	27	P.W. Purdom, S. M. Stigler, and T. Cheam. Statistical Investigation of Three Storage Allocation Algorithms. Technical Report 98, Computer Science, University of Wisconsin - Madison, 1970.
	28	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
	29	Mads Tofte, A brief introduction to regions, Proceedings of the 1st international symposium on Memory management, p.186-195, October 17-19, 1998, Vancouver, British Columbia, Canada
	30	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
	31	K. Vo. Vmalloc: A general and efficient memory allocator. Software Practice and Experience, pages 357--374, 1996. 26(3).
	32	C. B. Weinstock , W. A. Wulf, An efficient algorithm for heap storage allocation, ACM SIGPLAN Notices, v.23 n.10, p.141-148, Oct. 1988 [doi>10.1145/51607.51619]
	33	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
	34	Wm. A. Wulf , Sally A. McKee, Hitting the memory wall: implications of the obvious, ACM SIGARCH Computer Architecture News, v.23 n.1, p.20-24, March 1995 [doi>10.1145/216585.216588]