# Fast Allocation and Deallocation with an Improved Buddy System

Technical Report, ALCOMFT-TR-03-3, ALCOM-FT, 15 pages, May 2003.

## Abstract

We propose several modifications to the binary buddy system for managing
dynamic allocation of memory blocks whose sizes are powers of two. The
standard buddy system allocates and deallocates blocks in Θ(lg *n*) time
in the worst case (and on an amortized basis), where *n* is the size of the
memory.
We present three schemes that improve the running time to *O*(1) time, where the
time bound for deallocation is amortized for the first two schemes.
The first scheme uses just one more word of memory than the standard
buddy system, but may result in greater fragmentation than necessary.
The second and third schemes have essentially the same
fragmentation as the standard buddy system, and use
*O*(2^{(1 + \sqrt{lg n}) lg lg n}) bits of auxiliary storage,
which is ω(lg^{k} *n*) but *o*(*n*^ε)
for all *k* ≥ 1 and ε > 0.
Finally, we present simulation results estimating the effect
of the excess fragmentation in the first scheme.

**Online version**
alcomft-tr-03-3.pdf (193 Kb)

**BIBT**_{E}X entry

@techreport{alcomft-tr-03-3,
author = "Gerth St{\o}lting Brodal and Erik D. Demaine and J. Ian Munro",
institution = "ALCOM-FT",
month = "May",
number = "ALCOMFT-TR-03-3",
pages = "15",
title = "Fast Allocation and Deallocation with an Improved Buddy System",
year = "2003"
}