In unmanaged programming languages like C, C++, the programmer is responsible for explicitly allocating and freeing memory using malloc and free. Even modern memory-safe languages like Rust are built on malloc and free. The performance of an application can be very sensitive to how memory is managed. However, until now, there has not been a suitable methodology to fully expose the cost of malloc and free. Perhaps due to lack of understanding of the overheads of the freelist-based malloc and free design, this design has remained unchanged for decades and optimized for the hardware and software of the past. This thesis addresses the question of whether a fundamentally different design of malloc and free could yield substantially better performance on today’s software and hardware. To the best of our knowledge, this would be the first published work to consider this question.

The first contribution of this work is the development of a new methodology to expose the overheads of malloc and free. Our approach is inspired by the Lower Bound Overhead (LBO) methodology recently developed for garbage collection. The second contribution is the development of a novel analysis of object lifetimes in real-world C/C++ programs. The third and major contribution of this work will be the design and implementation of a new memory allocator motivated by our lower bound analysis and inspired by our lifetime analysis.

With the analysis and results we have observed so far, we are optimistic that a new allocator design, possibly augmented with the hardware support, can significantly improve the system performance. We expect that this design will significantly improve performance of languages whose implementation depends on malloc and free, including C, C++, and Rust. We hope that our entirely different approach will open new thinking on allocator design.

My thesis is that the performance of malloc and free can be dramatically improved if we fundamentally reconsider their design by adapting emerging ideas in other domains and supporting the allocator with new hardware features where required.