Memory Cache and Lisp: Faster list processing via automatically rearranging memory

The speed of modern computers can be increased by organizing computations so that memory access patterns correspond more closely to the memory cache-loading patterns implemented in the hardware. Rearranging code and data are each possible. Here we concentrate on automatic rearrangement of data, and examine the belief, common in some technical circles, that modern generational copying garbage collectors (GC) will improve data caching by relocating and compressing data, as a matter of normal processing. Since GC routines tend to be very well-tested and quite robust, if this belief can be confirmed by benchmarks, a GC could be a “free ” way of reliably speeding up programs in practice. In fact, our tests show this speedup phenomenon can be measured in some but not all sample Lisp programs. A novelty in our tests (at least when this paper was written) was using a full Lisp system linked to free software (PAPI) to access hardware machine registers. PAPI allows us to count cache misses during full-speed computation. We conclude that after a GC cache misses may be significantly reduced in some examples. Reorganization by GC speeds up computation by as much by a factor of 4, but in some cases the effect is negligible (or may even slow computation slightly). In any case, no extra effort is required of the programmer or user to take advantage of the potential speedup.