Source-linked AI summary
Tight Bounds for Memory Allocation With and Without Request Fragmentation
Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, Nicole Wein
TL;DR
The paper asks whether request fragmentation changes the classical memory-allocation problem and develops tight bounds for deterministic and randomized algorithms under multiple fragmentation models. It shows that even k = 1 + o(1) aggregate fragmentation reduces the optimal competitive ratio from Θ(log M) to Θ(log log M), while aggregate and per-request fragmentation have substantially different tradeoffs.
Problem
Request fragmentation is widely used in practice, but its theoretical effect and the amount of fragmentation needed to overcome classical lower bounds were largely unexplored.
Method
The paper proves matching upper and lower bounds for deterministic and randomized memory allocation with and without k-aggregate or k-per-request fragmentation.
Results
Even k = 1 + 1/polylog M aggregate fragmentation reduces the optimal competitive ratio to Θ(log log M), with the result applying to both deterministic and randomized algorithms.
Takeaways & Limitations
Aggregate fragmentation can nearly collapse classical lower bounds, whereas most of the algorithmic value of fragmentation requires different requests to be broken into different numbers of fragments.
Takeaways & Limitations
The analysis includes expected-fragmentation extensions and, in one lower-bound setting, assumes k and workload parameters are powers of two with power-of-two request sizes.
Abstract
from arXiv · showhide
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.
1 Introduction
Memory allocation minimizes the memory high-water mark, but classical online allocation has logarithmic competitive bounds. The paper studies how aggregate and per-request fragmentation alter these bounds, finding sharply different tradeoffs for deterministic and randomized algorithms.
- Classical memory allocation: Θ(log M) is the optimal deterministic competitive ratio in classical memory allocation, even when M is known in advance.Here M is the volume high-water mark, the maximum simultaneous volume of live requests.
- Request fragmentation: Request fragmentation splits requests into separately allocated fragments, allowing non-contiguous physical placement while preserving apparent contiguity through virtual addresses.The model is motivated by modern operating systems and allocators.
- Aggregate fragmentation: k-aggregate fragmentation limits the maximum number of live fragments to k times the maximum number of simultaneously live requests.This models the capacity needed for fragment-indexing data structures.
- Aggregate fragmentation: Matching upper and lower bounds characterize the best competitive ratio for deterministic and randomized algorithms using k-aggregate fragmentation.The paper summarizes these bounds across fragmentation regimes.
- Aggregate fragmentation: k = O(1) fragmentation causes an exponential collapse in competitive ratio as a function of M, while increasing k to ω(1) improves the ratio only by Θ(log k).The paper identifies this as a central surprise in the tradeoff.
- Extensions: Even k = 1 + 1/polylog M reduces the optimal competitive ratio to Θ(log log M), whereas known volume-range restrictions can reduce it further to O(1) when R = 1 and k = Θ(1).For restricted ranges, the paper gives a separate tradeoff in terms of k and R.
- Per-request fragmentation: k-per-request fragmentation has weaker bounds than k-aggregate fragmentation, and the paper argues that aggregate fragmentation is at least exponentially better.Per-request fragmentation limits each individual request to at most k fragments.
- Randomization: The analysis also yields an improved randomized lower bound for classical allocation, showing no asymptotic advantage from randomization in that setting.This closes the stated log log M gap in the prior randomized lower bound.
2 Preliminaries
The preliminaries formalize workloads, contiguous allocation, high-water marks, competitive ratio, and the two fragmentation models. They also extend the framework to expected fragment-count constraints.
- Allocation model: A workload is an arbitrary sequence of positive-integer memory requests and frees on an unbounded one-dimensional memory array.Each request specifies the number of slots that must be reserved.
- Allocation model: Each classical allocation must be a non-overlapping contiguous block chosen before the next request is revealed.A free deallocates the specified live request and returns its slots to availability.
- Performance measures: The memory high-water mark is the highest memory index allocated, while M(W) is the maximum number of simultaneously occupied slots.The competitive ratio compares the algorithm’s high-water mark with the workload’s volume high-water mark.
- Performance measures: The request high-water mark Q(W) is the maximum number of simultaneously live requests in a workload.It is used to state aggregate-fragmentation limits.
- Fragmentation models: Fragmentation partitions each request into positive-integer fragments whose sizes sum to the request size, with each fragment allocated contiguously and kept live until the request is freed.The two models differ in whether the bound applies across all live fragments or separately to each request.
- Fragmentation models: For k = 1 + ε aggregate fragmentation, the constraint is equivalent to allowing at most ε·Q(W) live partial fragments; per-request fragmentation permits at most k fragments per request.Aggregate fragmentation is defined for real k ≥ 1, whereas per-request fragmentation is defined only for positive integer k.
- Expected fragmentation: The lower bounds also apply to expected-k fragmentation, where the relevant fragment counts are bounded by k·Q(W) or k in expectation.This extends the constraints beyond worst-case fragment counts.
3 Technical Overview
The paper develops tight lower and upper bounds for memory allocation with request fragmentation, extending a classical lower-bound approach based on aligned blocks and potential functions. Fragmentation changes the dependence on the volume high-water mark from logarithmic to iterated logarithmic, with matching bounds for aggregate fragmentation.
- Classical lower bound: The classical randomized lower bound reaches an expected memory high-water mark of at least Ω(M log M).The workload has volume high-water mark O(M), yielding an expected competitive ratio of Ω(log M).
- Classical lower bound: The warmup workload uses geometrically increasing request sizes, randomized deletions, and aligned dyadic memory blocks.A potential-function argument limits the total allocation volume that each block can receive across rounds.
- Classical lower bound: The volume-versus-count dichotomy leaves earlier-round requests numerous but contributes most live-request volume from recent rounds.This makes earlier allocations interfere with later, larger allocations.
- Per-request fragmentation: For k-expected per-request fragmentation, a workload with at most Q live requests forces competitive ratio Ω(log_k Q).The workload has volume high-water mark Θ(M), and requests have sizes in [M/Q,M].
- Aggregate fragmentation: For k-aggregate fragmentation, randomized algorithms have a lower bound of Ω(log_k log M).The argument combines the per-request lower bound with a phase analysis; termination either yields a large memory high-water mark or many fragments.
- Matching upper bounds: Deterministic algorithms achieve matching upper bounds O(log_k log M) with k-aggregate fragmentation and O(log log M + log ε^-1) with (1 + ε)-aggregate fragmentation.The corresponding lower bound for (1 + ε)-aggregate fragmentation is Ω(log log M + log ε^-1).
4 A Tight Lower Bound for Expected-k Per-Request Fragmentation
This section proves tight lower bounds for expected-k per-request fragmentation using an adversarial workload and block-based allocation analysis. The proof yields a matching competitive-ratio lower bound and establishes that randomization cannot asymptotically improve the non-fragmented case.
- Theorem 4.1 constructs a randomized workload with volume high-water mark M and request high-water mark Q that challenges every allocation algorithm under the stated memory bound.The theorem applies to possibly randomized algorithms and forms the central lower-bound result.
- Classical case: For k = 1, Corollary 4.4 shows that randomized non-fragmented algorithms cannot asymptotically beat deterministic algorithms.This closes the remaining log log M gap in the randomized classical lower bound.
- Workload properties: The workload has volume high-water mark O(M), request high-water mark Q, and total request mass Ω(M log_k Q).These properties supply the scale and number of requests needed by the lower-bound argument.
- The adversarial workload: The adversarial workload runs R = log_k Q + 1 rounds, repeatedly frees a random fraction of existing request classes, and adds requests of a common size in each round.Each round frees a uniformly random 0.1 fraction before adding m/s_r requests of size s_r.
- Block analysis: Efficient packing makes reuse unlikely because all constituent fragments are unlikely to have been deallocated, so the allocator must either waste space initially or allocate substantial new space.This dichotomy drives the lower bound by forcing a constant fraction of allocated volume into new space.
- Block analysis: The proof tracks cumulative allocation volume in aligned blocks, showing that bounded per-block usage would force the allocator to consume many round-r blocks.The quantity ψ*(B) equals total allocation volume placed in block B through round r.
5 Lower Bounds for Aggregate Fragmentation
This section extends the lower-bound analysis from per-request to aggregate fragmentation and examines the especially restrictive regime k = 1 + ε. It proves lower bounds that, together with the paper’s upper bounds, are tight.
- Theorem 5.1 gives a lower bound for every k-expected-aggregate fragmentation algorithm with k > 1 over workloads whose volume high-water mark lies in a prescribed interval.The proof assumes a lower memory usage than the target bound and constructs a workload violating the aggregate-fragmentation constraint.
- Proof strategy: The proof iteratively applies Theorem 4.1 across R = log(M_max/M_min) rounds, using requests that force expected fragment counts above 2k.The constructed workload preserves the required volume range while accumulating retained requests.
- Proof strategy: The aggregate-fragmentation contradiction occurs when more than kQ expected fragments are simultaneously live for a workload with request high-water mark Q.This directly violates the definition of k-expected aggregate fragmentation.
- Tightness: The lower bounds are tight because Theorem 5.1 and Corollary 3.4 together establish that all upper bounds in Section 6 match them.
- Near-one fragmentation: For k = 1 + ε, any randomized online algorithm incurs competitive ratio Ω(log log M + log ε^-1) on some workload with volume high-water mark at most M.This combines the general aggregate lower bound with a separate Ω(1 + log ε^-1) bound.
6 Upper Bounds for Aggregate Fragmentation
The section develops deterministic online allocators for aggregate fragmentation, including known- and unknown-M settings. With (1+ε)-aggregate fragmentation, the competitive ratio is O(1 + log ε−1) when M is known and O(1 + log log(M(W)/M0(W)) + log ε−1) when it is unknown.
- Known M: O(1 + logq ε−1) is achieved by a deterministic algorithm using (1+ε)-aggregate fragmentation when M is known and request sizes are powers of q.For q = 2, the power-of-q assumption is without loss of generality up to a factor-of-two change to M.
- Known M: The algorithm A(M) keeps each request either whole or splits it into fragments capped at ε−1M/eQ(t), then places fragments by first-fit.Its effective fragment sizes sum to at most 2M for all live fragments.
- Known M: The type-segmentation invariant places every type-j fragment within the first j + 1 memory segments.Since fragment types are bounded by logq ε−1 + 1, the high-water mark is O(M(1 + logq ε−1)).
- Unknown M: O(1 + logk log(M(W)/M0(W))) is achieved deterministically with k-aggregate fragmentation for k ≥ 2 when M is unknown.The guarantee applies to workloads satisfying M(W) ≥ M0.
- Unknown M: O(1 + log log(M(W)/M0(W)) + log ε−1) is achieved deterministically with (1 + ε)-aggregate fragmentation when M is unknown and M(W) ≥ M0.The construction processes successive volume scales using phase-dependent algorithms.
A Generalizing to Average Fragmentation
The section compares memory-average and cumulative-average fragmentation with per-request fragmentation through workload transformations. These reductions show that the corresponding models inherit the relevant per-request bounds.
- Memory-average fragmentation: Memory-average fragmentation is defined as the high-water mark of live fragments divided by live requests.The section proves that an expected memory-average bound of k implies an expected per-request bound of k.
- Memory-average fragmentation: A workload that frees all requests except one can convert an expected per-request excess into an expected memory-average excess.This supplies the contradiction used in Claim A.1.
- Cumulative-average fragmentation: Cumulative-average fragmentation is defined as total fragments ever created divided by total requests ever allocated.Claim A.2 transfers a memory-high-water-mark bound from per-request fragmentation to cumulative-average fragmentation.
- Cumulative-average fragmentation: Repeatedly requesting and freeing a request transforms an algorithm with cumulative-average fragmentation at most k into one whose expected fragmentation for that request is at most k.The construction then continues with the original workload.
- Reduction: The transformed per-request and average-fragmentation workloads have the same expected memory high-water mark.This establishes the claimed transfer for an arbitrary algorithm with cumulative-average fragmentation at most k.
B Reducing Theorem 4.1 to Theorem 4.5
The section reduces the lower-bound analysis to selective, aligned, equal-fragment algorithms through simulations and controlled request-size scaling. Each reduction preserves or upper-bounds the relevant memory high-water mark.
- Reduction steps: A request-fragmenting algorithm with at most k fragments in expectation reduces to a 1/4-selective algorithm using at most 4k fragments deterministically.The reduction ignores requests exceeding the deterministic fragment threshold, with probability at most 1/4.
- Reduction steps: A 1/4-selective algorithm using at most k pieces reduces to one using k equal-sized fragments, with S(B,W) ≤ S(A,4W).The construction simulates requests four times larger and subdivides usable fragments.
- Reduction steps: A 1/4-selective algorithm with 2^i equal-sized fragments reduces to an aligned-even-fragmentation algorithm with S(B,W) ≤ S(A,2W).Each simulated fragment contains the aligned block into which the reduced algorithm allocates.
- Conclusion: The reductions conclude that Theorem 4.1 can be reduced to Theorem 4.5 under power-of-two and power-of-k assumptions.Rounding k, M, and Q preserves the asymptotic lower bound.