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