Indexed Bitvector
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