Cache Conscious Static Search

ccss.tar.gz (3KB)

Source code to the CCSS functions.

ccss_all.tar.gz (23KB)

Source code to the CCSS functions, binary search functions, Atom instrumentation code, driver code, and other miscellaneous functions. Plus shell scripts to generate, manipulate, and display the data written by the driver code. All barely documented.

paper.ps (542KB)

10-page paper discussing the CCSS versus the binary search.

Abstract

A cache conscious static search data structure is presented. The advantages and disadvantages of this data structure over traditional binary search are investigated. Cache simulations and execution timings demonstrate the performance gains in using this cache conscious design.

extras.ps (114KB)

Possibly interesting graphs that did not make it into the paper.