Efficient implementation of the first-fit strategy for dynamic storage allocation

68. R. P. Brent, Efficient implementation of the first-fit strategy for dynamic storage allocation, Australian Computer Science Communications 3 (1981), 25-34. Also appeared as Report TR-CS-81-05, DCS, ANU, February 1981, 10 pp.

Technical Report: pdf (1221K).

Abstract

We describe an algorithm which efficiently implements the first-fit strategy for dynamic storage allocation. The algorithm imposes a storage overhead of only one word per allocated block (plus a few percent of the total space used for dynamic storage), and the time required to allocate or free a block is O(log W), where W is the maximum number of words allocated dynamically. The algorithm is faster than many commonly used algorithms, especially when many small blocks are allocated, is relatively easy to implement in a low-level programming language, and could be used to provide runtime support for high-level languages such as Pascal.

Comments

A revision appeared as [89]. For related work see [90, 91].

Go to next publication

Return to Richard Brent's index page