✓ Uses Rust 2018 edition
|4.0.1||Jan 13, 2019|
|2.4.0||Jan 1, 2019|
|2.3.0||Dec 24, 2018|
|2.0.0||Jul 22, 2018|
#198 in Algorithms
177 downloads per month
Used in packed_integer_array
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 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
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.
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