On the External Storage Fragmentation Produced
by First-Fit and Best-Fit Allocation Strategies

Published comparisons of the external fragmentation
produced by first-fit and best-fit memory 
allocation have not been consistent.  Through simulation,
a series of experiments were performed in order 
to obtain better data on the relative performance of
first-fit and best-fit and a better understanding 
of the reasons underlying observed differences. The
time-memory-product efficiencies of first-fit and 
best-fit were generally within 1 to 3 percent of each
other.  Except for small populations, the size 
of the request population had little effect on allocation
efficiency.  For exponential and hyperexponential 
distributions of requests, first-fit outperformed best-fit;
but for normal and uniform distributions, 
and for exponential distributions distorted in various
ways, best-fit outperformed first-fit.  It is 
hypothesized that when first-fit outperforms best-fit,
it does so because first-fit, by preferentially 
allocating toward one end of memory, encourages large blocks
to grow at the other end.  Sufficient contiguous 
space is thereby more likely to be available for relatively
large requests.  Results of simulation experiments 
supported this hypothesis and showed that the relative
performance of first-fit and best-fit depends 
on the frequency of request.  When the coefficient of
variation of the request distribution is greater 
than or approximately equal to unity, first-fit outperformed best-fit.

CACM August, 1975

Shore, J. E.

storage fragmentation, dynamic memory allocation, first-fit, best-fit

3.73 4.32 4.35

CA750801 JB January 9, 1978  9:41 AM

2095	4	2734
2218	4	2734
2218	4	2734
2498	4	2734
2596	4	2734
2734	4	2734
2734	4	2734
2902	4	2734
2911	4	2734
3000	4	2734
3000	4	2734
1879	5	2734
2095	5	2734
2734	5	2734
2734	5	2734
2734	5	2734
2902	5	2734
2911	5	2734
2983	5	2734
1051	6	2734
1062	6	2734
1184	6	2734
1211	6	2734
1552	6	2734
1879	6	2734
1879	6	2734
273	6	2734
2435	6	2734
2435	6	2734
2498	6	2734
2596	6	2734
2734	6	2734
2734	6	2734
2734	6	2734
2747	6	2734
2768	6	2734
2773	6	2734
2983	6	2734