Improving locality with dynamic memory allocation

Dynamic memory allocators are a determining factor of an application's performanceand have the opportunity to improve a major performance bottleneck ontoday's computer hardware: data locality. To approach this problem, a memoryallocator must rst oer strategies that allow the locality problem to be addressed.However, while focusing on locality, an allocator must also not ignore the existing constraintsof allocation speed and fragmentation, which further complicate its design. Inorder for a locality improving technique to be successfully employed in today's largecode applications, its integration needs to be automatic, without user intervention.The alternative, manual integration, is not a tractable solution.In this dissertation we develop three novel memory allocators that explore dierentallocation strategies that enhance an application's locality. We conduct the rststudy that shows that allocation speed, fragmentation and locality improving goalsare antagonistic. We develop an automatic method that supplies allocation hintsfrom C++ STL containers to their allocators. This method allows applications tobenet from locality improving techniques at the cost of a simple re-compilation. Weconduct the rst study that quanties the eect of allocation hints on performance,and show that an allocator with high locality of reference can be as competitive asone using an application's spatial feedback.To further allow dynamic memory allocation to improve an application's performance,new and non-traditional strategies need be explored. We develop a generic software tool that allows users to examine unconventional strategies. The tool allowsusers not only to focus on allocation strategies rather than their implementation, butalso to compare and contrast various approaches