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

89. R. P. Brent, Efficient implementation of the first-fit strategy for dynamic storage allocation, ACM Trans. on Programming Languages and Systems 11 (1989), 388-403. Also appeared as Report CMA-R33-84, Centre for Mathematical Analysis, ANU, August 1984, 26 pp.

Abstract: dvi (3K), pdf (72K), ps (25K).

Paper: pdf (1034K).

Abstract

We describe an algorithm that 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, and it has good worst-case behaviour. It is relatively easy to implement and could be used internally by an operating system, or to provide run-time support for high-level languages such as Pascal and Ada. A Pascal implementation is given in the Appendix (a Fortran implementation also exists).

Comments

A preliminary version appeared eight years earlier as [68]. The long delay was partly due to an administrative error (the paper was accepted but misfiled in the editor's office). For related work see [90, 91].

Go to next publication

Return to Richard Brent's index page