Memory Access Analysis and Optimization Approaches On Splay Trees

Splay trees, a type of self-adjusting search tree, are introduced and analyzed. Since they have been widely used in search problems, any performance improvements will yield great benefits. First, the paper introduces some background about splay trees and memory hierarchies. Then, it presents two heuristic algorithms, based on research in reference affinity and data regrouping. These algorithms have good locality, reduce memory transfers, and decrease cache miss rates on different architectures. Finally, the paper evaluates the performance gain of these algorithms on random inputs and Spec2K benchmark programs