A paper by Andrew Appel.
The conclusion of this paper may seem trivial at first: A very old and simple algorithm for garbage collection gives very good results when the physical memory is much larger than the number of reachable cells.
However get this the overhead associated with allocating and collecting cells from the heap can be reduced to less than one instruction per cell by increasing the size of physical memory.
Whether trivial or surprising, it is worth reading.
Posted to implementation by Ehud Lamm on 5/1/01; 8:25:05 AM