Optimal Memory Allocation: The Dos and Don’ts of Request Fragmentation

Abstract: I will talk about the classical problem of memory allocation, with and without request fragmentation. In the standard version (without request fragmentation), the input is an arbitrary sequence of memory requests of various sizes and frees. Upon arrival of each memory request, the algorithm must decide where to allocate it in memory. A free specifies a previous memory request, and the algorithm responds by deallocating its allocated memory. The quality of an algorithm is measured by its memory high-water mark (largest occupied memory slot) as a function of the volume high-water mark M (largest volume of requests simultaneously allocated). The best known upper and lower bounds are the classical bounds of O(M log M) and Omega(M log M / log log M) respectively. Since logarithmic lower bounds can be prohibitive in practice, a common memory-saving strategy is to fragment requests into a small number of pieces. Despite wide proliferation of request fragmentation in practice, we are the first to study it in theory. We prove tight upper and lower bounds for the memory allocation problem both with and without fragmentation.

Joint work with Michael Bender, Alexander Conway, Martin Farach-Colton, Hanna Komlos, and William Kuszmaul.

PASSCODE: 985224