Suffix array searching: 40x faster binary search

This is a research project corresponding to this blog post. Code is not really intended to be used as-is as a dependency in other projects, and documentation is sub-par for that purpose.

It provides a static search tree data structure that can answer ‘binary search’ queries much faster, at the cost of 6% space overhead: given a list of n sorted integers and a list of queries, it returns for each query the first number that is at least the queried value.

It is on my to-do list, but with low priority, to make this into a nice standalone crate.

To reproduce experiments and plots, create the results and plots directories (the scripts expect them to exist).

1. Run the experiments: cargo run -r --bin bench -- --release.

   See cargo run -r --bin bench -- --help for more options.

   Note: To use SIMD, make sure to compile for your native CPU, e.g. by adding the following to .cargo/config.toml:

   [build]
   rustflags = ["-C", "target-cpu=native"]
       

2. To generate plots: python3 ./plot.py. This will error at some point that results-human-release.json isn’t found. To avoid that, comment out the last plot_blog() call.