Two memory allocators that use hints to improve locality

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 goodbalance of these traits, and they can easily be adjusted to optimize the most important trait for each application.

Original languageEnglish (US)
Title of host publicationISMM'09 - Proceedings of the 2009 ACM SIGPLAN International Symposium on Memory Management
Number of pages10
StatePublished - 2009
Externally publishedYes
Event2009 ACM SIGPLAN International Symposium on Memory Management, ISMM'09 - Dublin, Ireland
Duration: Jun 19 2009Jun 20 2009

Publication series

NameInternational Symposium on Memory Management, ISMM


Conference2009 ACM SIGPLAN International Symposium on Memory Management, ISMM'09


  • Automatic locality improvement
  • C++ STL allocation
  • Cache-conscious
  • Dynamic memory management
  • Memory fragmentation.
  • Page-conscious
  • Spatial locality
  • Temporal locality

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software


Dive into the research topics of 'Two memory allocators that use hints to improve locality'. Together they form a unique fingerprint.

Cite this