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