Cache-Oblivious Searching and Sorting

Benchmark Results

Key to interpret the plots of this directory:

• po = searching with layout-policy implementation
• pu = searching with pure-c implementation
• sort = sorting
• all = measurements of funnelsort, introsort, and 4-way mergesort
• d = measurements of funnelsort for different values of d


• si = successful lookups of elements of increasing value
• sr = successful lookups of random elements
• src = successful lookups of random elements in a repetitive cycle
• u = unsuccessful lookups


• CPU = CPU time measurements
• WALL = Wall-clock time measurements
• BRCN = Conditional-branch instruction counts
• BRMSP = Branch misprediction counts
• L1A = Level 1 cache access counts
• L1M = Level 1 cache miss counts
• L2M = Level 2 cache miss counts
• PAGEFAULTS = Page fault counts