Aarhus University Seal

Fast Allocation and Deallocation with an Improved Buddy System

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearch

  • Gerth Stølting Brodal
  • Erik D. Demaine, Massachusetts Institute of Technology, United States
  • J. Ian Munro, University of Waterloo, Canada
  • Department of Computer Science
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 Theta(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 omega(lgk n) but o(n^epsilon) for all k >= 1 and epsilon > 0. Finally, we present simulation results estimating the effect of the excess fragmentation in the first scheme.
Original languageEnglish
JournalActa Informatica
Pages (from-to)273-291
Publication statusPublished - 2005

See relations at Aarhus University Citationformats

ID: 230281