## 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