The cache performance of algorithms is becoming more and more important as the ratio of processor speed to memory speed increases. Cache miss penalties are often more than 100 cycles and they are growing. Analyzing the cache performance of common memory access patterns leads to a better understanding of the performance of algorithms in practice. In this talk we investigate the cache performance of the simple memory access pattern of traversing a contiguous block of memory. In particular, we analyze iterative mergesort, preorder tree traversal, and frequency counting. Mergesort is an example of an algorithm that does simple left-to-right traversals. Preorder tree traversal is an example of an algorithm that does a permutation traversal. Frequency counting is an example of an algorithm that does a traversal interacting with random accesses. To validate the analysis we use trace driven cache simulation.
This is joint work with Anthony LaMarca of Xerox PARC and Jim Fix of the University of Washington.