An Evaluation of Search Tree Techniques in the Presence of Caches

Caches play an increasingly important role in determining the overallprogram performance on modern architectures. To be able to makeeducated choices between the algorithms for specific applications, weneed to understand not only their theoretical complexity but alsotheir behavior in the presence of caches. In this paper, we evaluatethe performance of two broad classes of search tree algorithms in thepresence of a cache hierarchy: move commonly accessed items closer tothe root (move-to-front) and keep the tree balanced (keep-it-balanced). The move-to-front technique tries to improve theperformance for the common case by reducing the number of operationsrequired to retrieve commonly accessed items. The keep-it-balancedtechnique tries to improve worst-case performance by reducing themaximum number of operations required to look up an item in thetree. For each class, we consider both classical algorithms andvariants that have been optimized for a cache hierarchy. To drive ourevaluation, we use a suite of synthetic datasets that vary in thedegree of locality found in the request stream and the operationmix. Our results show that, for all but very highly skewed workloads,keep-it-balanced algorithms perform significantly better thanmove-to-front algorithms. We present an analytical performancemodel that uses easily computed characteristics of a dataset topredict which class of algorithms is likely to perform better for thatdataset.