Bitsy is an itsy-bitsy bit vector with rank and select support, whose rank and select data structures have a combined space overhead of 3.40% in its default (fastest) configuration.
The requirements to build Bitsy are a C++20 compiler (GCC/Clang), CMake (v3.16+) and a build system (Ninja, GNU Make, etc.). To build Bitsy follow the steps below:
# Fetch a copy of Bitsy if not already present
git clone https://github.com/dsalwasser/Bitsy.git
cd Bitsy
# Actually build Bitsy
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallelBy default, the PDEP instruction is used. If Bitsy is running on a machine that
has a slow PDEP instruction, then we recommend disabling this feature by adding
the CMake flag -DBITSY_USE_PDEP=Off, as alternative implementations will be
faster. Processors with a slow PDEP instruction are for example Zen 1 and Zen 2
generation AMD processors. On the other hand, all Intel processors and AMD
processors after the Zen 2 generation have a fast PDEP instruction.
Furthermore, huge pages are used by default to improve performance. Thus, an
attempt is first made to allocate 2-MiB-sized huge pages and if this does not
work (e.g., if it is not supported by the system), normal pages are allocated
instead. However, if you do not want to use huge pages for some reason, this
can be switched off with the additional CMake flags -DBITSY_HUGE_PAGES=Off.
Also, the compiler flag -mtune=native is used by default. If Bitsy is
not compiled on the machine on which it is executed, the flag can be disabled
by adding the additional CMake flag -DBUILD_WITH_MTUNE_NATIVE=Off. However,
we recommend compiling Bitsy on the machine on which it is executed using
-mtune=native to improve performance.
We provide the ads_programm application to answer queries for a bit vector
stored in a file and to write the corresponding answers to an output file. To
use this application, first compile Bitsy by following the above steps and then
run:
./build/apps/ads_programm <input_file> <output_file>