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

Reviewer: Gerald David Chandler

This paper describes the many types of dynamic memory allocation strategies and discusses the many possible implementation algorithms for each. Perhaps the most commonly used strategy is first-fit, in which a list is maintained of the memory blocks that can be allocated; the block allocated in response to a request is the first on the list that is large enough to satisfy the request. Before 1968, the usual algorithm used to implement first-fit used a linked list to maintain the list of free blocks; subsequently, many alternatives have appeared. Brent presents an algorithm that divides the free space into fixed size segments; within a segment, blocks are linked in the standard manner. The novel aspect of his approach is to maintain an index to the segments that contains the largest block starting in each segment. The index itself makes use of the same data structure that heap sort is based on—an array representing a binary tree in which the descendants of node N are in array elements 2 N and 2 N + 1. Through the use of this index, the time for allocating or disposing of an element is reduced from O( B) to O(log B) where B is the number of active blocks. A simulation-based comparison of the indexed approach with the standard linked algorithm indicates that the new algorithm is faster for B greater than 100. An appendix contains the complete Pascal code that implements the algorithm. Because this program is clearly written, a separate, earlier presentation of pseudocode appears to be unnecessary. As with the programs, the paper itself is clear and well organized. It is worth reading. As a last thought, I wonder why the editors of the journal printed this paper a long four years after it was accepted, while the paper on page 345 in the same issue appears only five months after acceptance.