EFFICIENT IMPLEMENTATION OF THE FIRST-FIT STRATEGY FOR DYNAMIC STORAGE ALLOCATION

RICHARD P. BRENT

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.

Comments

Only the Abstract is given here. The full paper appeared as [2], and a preliminary version appeared as [1].

References

1. R. P. Brent, “Efficient implementation of the first-fit strategy for dynamic storage allocation”, Proc. Fourth Australian Computer Science Conference, special issue of Australian Computer Science Communications 3 (1981), 25–34. rpb068.

2. 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, August 1984, 26 pp. rpb089.

Computer Sciences Laboratory, Australian National University, Canberra

1991 Mathematics Subject Classification. Primary 68P05; Secondary 68N15, 68P20. Key words and phrases. Algorithms, languages, performance, dispose, dynamic memory management,

dynamic storage allocation, first-fit strategy, heaps, new, trees.

CR Categories. D.4.2, D.4.8, E.2. The author thanks J. B. Hext, D. E. Knuth, and J. M. Robson for their comments on a preliminary

version [1] of this paper.

Received August 1984; revised September 1985; accepted October 1985. Copyright \begin{matrix}c \\ ◯ \end{matrix} 1989, ACM. Permission to copy without fee all or part of this material is granted provided

that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent. rpb089a typeset using AMS-L^{A}TEX