The storage requirement in precedence parsing
Eberhard Bertsch · Communications of the ACM · 1977
Figure 1 shows e, the mean request size for (truncated) exponentially distributed requests versus E, the time-memory product efficiency as defined in [2] (the plot essentially corresponds to Figure 2 in [2] although naturally all of the points are somewhat different).The total memory size was 32,768 and the memory-residence time of requests was uniformly distributed between 5 and 15 time units.Each point represents the mean of approximately 20 runs, where the clock time for each run varied from 500 to 5000.The standard deviation of each point was less than .006.The results of this simulation support the hypothesis mentioned by Shore, that "when first-fit outperforms best-fit, it does so because first-fit, by preferentially allocating [blocks] toward one end of memory, encourages large blocks to grow at the other end."The fact that next-fit is decidedly inferior to both firstfit and best-fit, implies that eliminating the preferential allocation of first-fit causes a loss of efficiency.Of course,