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