#bit-vector #indexing #index #bits #bit

indexed_bitvec

An indexed bitvector with (hopefully) fast rank and select operations

6 stable releases

4.0.1 Jan 13, 2019
2.4.0 Jan 1, 2019
2.3.0 Dec 24, 2018
2.0.0 Jul 22, 2018

#2277 in Data structures


Used in 2 crates

Apache-2.0

130KB
3K SLoC

Indexed Bitvector

Build status Latest version Documentation

This library provides an indexing system for bitvectors which should hopefully allow fast rank and select operations.

This library is based on the design proposed by Zhou, Andersen and Kaminsky in Space–Efficient, High–Performance Rank & Select Structures on Uncompressed Bit Sequences.

Timings

Timings were made:

  • Using criterion for the timing
  • For a 1GB vector (slightly larger in fact)
  • Compiled in release mode
  • With LTO, codegen-units 1, non-incremental build
  • With RUSTFLAGS='-C target-cpu=native'
  • CPU: Intel® Core™ i7-7700K CPU @ 4.20GHz
Operation Time
build_index ~200ms
count ~2ns
rank ~55ns
select ~110ns

The use of target-cpu is likely to have a significant effect on the speed of the operations as it allows llvm & rust to use vectorisation & popcount instructions that might be available, so consider working out how to compile for the specific cpu you want to run the program on.

The timing of building the index has not been left in the code, as criterion does so many iterations to time it that it makes running the benchmarks take 15 minutes.

See also

I think there is an implementation of the same approach in a Haskell succinct vector library.

Zhou, Andersen and Kaminsky. Space–Efficient, High–Performance Rank & Select Structures on Uncompressed Bit Sequences

Dependencies

~0.3–1.1MB
~22K SLoC