cseq_benchmark is the program (by Piotr Beling) for benchmarking compact sequences and bitmaps.

It can test the listed algorithms contained in the following crates:

• cseq: Elias-Fano (experimental);
• bitm: rank and select queries on bit vectors;
• sucds: rank and select queries on bit vectors;
• succinct: rank and select queries on bit vectors;
• sux: select queries on bit vectors;
• vers (only if compiled with vers-vecs feature): rank and select queries on bit vectors.

Please run the program with the --help switch to see the available options.

Below you can find instruction for installing cseq_benchmark and reproducing experiments performed with it, which can be found in published or under review papers. Note that these instructions have been tested under GNU/Linux and may require some modifications for other systems.

Installation

cseq_benchmark can be compiled and installed from sources. To do this, a Rust compiler is needed. The easiest way to obtain the compiler along with other necessary tools (like cargo) is to use rustup.

Please follow the instructions at https://www.rust-lang.org/tools/install.

Once Rust is installed, just execute the following to install cseq_benchmark with native optimizations:

RUSTFLAGS="-C target-cpu=native" cargo install --features=vers-vecs cseq_benchmark

The --features=vers-vecs flag enables compilation of the non-portable vers crate. It should be omitted in case of compilation problems.

Reproducing experiments from the papers

Rust libraries and programs focused on succinct data structures

(Piotr Beling Rust libraries and programs focused on succinct data structures submitted to SoftwareX)

Results for structures that support rank and select queries on bit vectors, included in libraries written in Rust (we used rustc 1.75.0 to compile), can be obtained by running:

cseq_benchmark -f -t 60 -c 20 -q 10000000 -u 1000000000 -n 500000000 bv
cseq_benchmark -f -t 60 -c 20 -q 10000000 -u 1000000000 -n 100000000 bv

Notes:

• The -t 60 -c 20 switches force a long testing time (60s for warming up + about 60s for performing each test + 20s cooling/sleeping between tests). They can be omitted to get results faster, but averaged over fewer repetitions.
• The -f switch causes the results to be written to files. It also can be skipped, as the results are printed to the screen anyway.

The results for the methods contained in SDSL2 (which is written in C++; we used clang 14.0.6 to compile) can be obtained using the program available at https://github.com/beling/benchmark-succinct (the page also contains compilation instructions) by running:

rank_sel 1000000000 500000000 60 10000000
rank_sel 1000000000 100000000 60 10000000

Benchmark results

Notes on benchmarks of structures supporting rank and select queries on bit vectors

• We do not distinguish rank₀ from rank₁ as each is trivially computable from the other.
• In a bit vector with adversarial distribution and n ones, 99% of them occupy the last n indices.
• Versions of the tested crates: bitm 0.4.1, succinct 0.5.2, sucds 0.8.1, sux 0.2.0, vers 1.1.0.
• Structures supporting select marked with * use or are integrated with (in the case of vers RsVec) the corresponding rank structure and the space overhead given for them is additional.
• We conducted the benchmarks using: long measurement (t=60) and cooling (c=20) times, 10⁷ random query arguments, AMD Ryzen 5600G @3.9GHz CPU and compilation with native optimizations enabled.

Rank for uniform distribution of ones in the bit vector

Select₁ for uniform distribution of ones in the bit vector

Select₀ for uniform distribution of ones in the bit vector

Rank for adversarial distribution with 99% of ones near the end of the vector

Select₁ for adversarial distribution with 99% of ones near the end of the vector

Select₀ for adversarial distribution with 99% of ones near the end of the vector