Tight Bounds for Memory Allocation With and Without Request Fragmentation
Data Structures and Algorithms
Summary
The authors study a classic problem about how to fit different-sized objects into memory while minimizing the peak memory use. Traditionally, the best online methods had a performance limited by a logarithm of the total request size. They notice that some real-world methods break requests into multiple parts, allowing a form of fragmentation controlled by a parameter k. The authors show that even a small amount of fragmentation drastically improves performance, reducing the complexity from a log scale to a log-log scale, and this improvement is proven optimal. Their findings hold for both deterministic and randomized approaches.
memory allocationonline algorithmscompetitive ratiorequest fragmentationdeterministic algorithmsrandomized algorithmslogarithmic boundshigh-water mark
Authors
Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, Nicole Wein
Abstract
The classical memory-allocation problem captures the task of placing objects of different sizes in memory, while minimizing the so-called memory high-water mark. It has been known since the early 1970s that the optimal competitive ratio for any deterministic online allocator is $Θ(\log M)$, where $M$ is the volume high-water mark of the underlying request sequence. This paper begins with a simple observation: many real-world allocators seem to bypass the 1971 lower bound by adopting a slightly different model for memory allocation. These allocators use what we call $k$-aggregate request fragmentation, meaning that the memory allocator is permitted to break requests into multiple fragments, so long as the all-time maximum number of simultaneous fragments is at most $k$ times the all-time maximum number of simultaneous requests. We consider the following basic question: Does request fragmentation fundamentally change the problem of memory allocation, and if so, how? Our results come with several surprises. Among these, we find that even using $k = 1 + o(1)$ request fragmentation, the optimal competitive ratio---which was $Θ(\log M)$ in the classical setting---collapses to $Θ(\log \log M)$. This result is shown to be tight with matching upper and lower bounds, applying to both deterministic and randomized algorithms.