Rock, paper, scissors: How spatial locality, fragmentation, and allocation speed compete in a dynamic memory allocator

Wednesday, March 23, 2011 - 16:30
TH 331
Alin Jula (SAP Labs - Palo Alto)

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 talk I'll discuss two locality improving allocators that use allocation hints provided automatically from the C++ STL library to improve an application's spatial locality. 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. I'll argue 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.


Alin Jula is a Senior Research Scientist at SAP Labs in Palo Alto where he has been working on multithreading optimization for multicore. He
received a Ph.D. in Computer Science from Texas A&M University in 2008,and he has worked in parallel programming, dynamic memory allocation, performance optimization, and compiler technologies.