4. A Comparison of Cache Aware and Cache Oblivious Static Search Trees Using Program Instrumentation

An experimental comparison of cache aware and cache oblivious static search tree algorithms is presented. Both cache aware and cache oblivi-ous algorithms outperform classic binary search on large data sets because of their better utilization of cache memory. Cache aware algorithms with implicit pointers perform best overall, but cache oblivious algorithms do almost as well and do not have to be tuned to the memory block size as cache aware algorithms require. Program instrumentation techniques are used to compare the cache misses and instruction counts for implementa-tions of these algorithms. The performance of an algorithm when implemented is a function of many factors: its theoretical asymptotic performance, the programming language chosen, choice of data structures, the configuration of the target machine, and many other factors. One factor that is becoming more and more impor