BitLib

This repository acts as an efficient replacement of std::vector<bool>. It provides implementations of many of the functions in <algorithms> optimized for containers of bits, in addition to providing a bit_vector class which has roughly the same interface as std::vector<bool>.

This project is built on "bit iterators" developed by Vincent Reverdy and many of the implementations in include/bit-algorithms come from some of my previous work with Vincent here.

Example

The code below is from example/src/example1.cpp. While the type of word that the bitvector is built off of is templated and you can use any unsigned type, it is likely that you'll want to use uint64_t or another 64 bit unsigned type, as that will leverage the most bit-parallelism.

#include <iostream>
#include "bitlib/bitlib.hpp"

int main() {
    bit::bit_vector<unsigned char> bv1 ("011111010010");
    std::cout << "Original bitvec:  " << bv1.debug_string() << std::endl;
    // Original bitvec:  01111101 0010

    // Same behavior as std::reverse
    bit::reverse(bv1.begin(), bv1.end());
    std::cout << "Reversed bitvec:  " << bv1.debug_string() << std::endl;
    // Reversed bitvec:  01001011 1110

    // Same behavior as std::rotate
    bit::rotate(bv1.begin(), bv1.begin() + 3, bv1.end());
    std::cout << "Rotated bitvec:   " << bv1.debug_string() << std::endl;
    // Rotated bitvec:   01011111 0010

    // Same behavior as the corresponding std::vector::push_back and std::vector::insert
    bv1.push_back(bit::bit0);
    bv1.insert(bv1.end(), 10, bit::bit1);
    std::cout << "Extended bitvec:  " << bv1.debug_string() << std::endl;
    // Extended bitvec:  01011111 00100111 1111111

    return 0;
}

Installation

BitLib is a header-only libarary. Currently, the BitLib library requires at least -std=c++17.

CMake

You can automatically fetch the library using Cmake's FetchContent.

include(FetchContent)
FetchContent_Declare(
    bitlib
    GIT_REPOSITORY https://github.com/bkille/bitlib.git
    GIT_TAG origin/master
)
FetchContent_MakeAvailable(bitlib)

add_executable(example example.cpp)
target_link_libraries(example bitlib::bitlib)

Manual include

Alternatively, you can copy the include/bitlib directory to somewhere in your include path.

SIMD support, testing and benchmarking

SIMD support (enabled via Google's highway library) can be enabled by defining BITLIB_HWY. For example, with cmake, you can run cmake -DBITLIB_HWY=1. Other options can be found in the CMakeLists.txt file:

option(BITLIB_HWY "Build with google highway SIMD extensions" OFF)
option(BITLIB_BENCHMARK "Build bitlib benchmarks" OFF)
option(BITLIB_EXAMPLE "Build bitlib examples" OFF)
option(BITLIB_TEST "Build bitlib tests" OFF)
option(BITLIB_PROFILE "Buid simple example for profiling" OFF)
option(BITLIB_COVERAGE "Compute test coverage" OFF)

Usage

The goal of BitLib is to be as similar to the C++ STL as possible. The interface of most functions and classes are the same as they are in the STL. Instead of the values being bool, we have bit::bit_value, which can take on either bit::bit0 or bit::bit1.

Containers

Right now, the only container I have implemented is the bitvector. bit::bit_vector<WordType> is essentially a wrapper around std::vector<WordType>. The interfaces are nearly identical. In addition to the normal vector constructors, you can also provide a string to construct your bitvector:

using WordType = uint64_t;
bit::bit_vector<WordType> bvec1 ("011111010010");

While the type of word that the bitvector is built off of is templated and you can use any unsigned type, it is likely that you'll want to use uint64_t or another 64 bit unsigned type, as that will leverage the most bit-parallelism.

Algorithms

The algorithms again work in the same manner as the STL. The functions provided here have the same interface as those in the STL, however under the hood, they take advantage of bit-parallelism. It should be noted that if there is an STL algorithm that is not supported yet by BitLib, you can still use the STL implementation. For example:

using WordType = uint64_t;
bit::bit_vector<WordType> bvec1 ("011111010010");
bit::bit_vector<WordType> bvec2 = bvec1;
bit::equal(bvec1.begin(), bvec1.end(), bvec2.begin(), bvec1.end());
std::equal(bvec1.begin(), bvec1.end(), bvec2.begin(), bvec1.end()); // Also works, but much slower as it works bit-by-bit

For algorithms which take a function (i.e. bit::transform), the function should have WordType as the input types as well as the return type. For example, to compute the intersection of two bitvectors:

using WordType = uint64_t;
auto binary_op = std::bit_and<WordType>();

// Store the AND of bitvec1 and bitvec2 in bitvec3
auto bitret = bit::transform(
        bitvec1.begin(),
        bitvec1.end(),
        bitvec2.begin(),
        bitvec3.begin()
        binary_op); 

Iterators

The bit-iterators are the foundation of the library. In most cases, users will only need to work w/ the bit::bit_vector::begin() and bit::bit_vector::end() methods to obtain iterators. However, constructing a bit iterator from any address is also straightforward:

using WordType = uint64_t;
std::array<WordType, 4> wordArr = {1,2,3,4};
bit::bit_iterator<WordType*>(&(wordArr[0])); // Constructs a bit iterator starting from the first bit from the first word of the vector
bit::bit_iterator<WordType*>(&(wordArr[0]), 1); // Constructs a bit iterator from the second bit (position 1) of the first word of the vector

In order to grab the underlying word that a bit pointed to by a bit_iterator comes from, you can use the bit_iterator.base() function.

It is worth noting that the "position" of a bit always increases from LSB to MSB. For those looking to create their own algorithms from bit_iterators, this can be a common "gotcha". For example, shifting a word to the right by k will eliminate the first k bits of the container. This is only important to those implementing their own algorithms. bit::shift_* works as described in the documentation i.e. shift_right shifts the container towards end() and shift_left shifts the container towards begin().

       MSB|<-----|LSB
Position: 76543210
Value:    01010001 --> Sequence: 10001010


// bit::shift_right by 2
       MSB|<-----|LSB
Position: 76543210
Value:    01000100 --> Sequence: 00100010

Documentation

Given that the majority of the library is focused on having the same interface as the C++ STL iterators, containers, and algorithms, users should use the official STL documentation website. We do plan on adding our own documentation in the future, however.

Performance Benchmarks

I used Google's benchmark library for computing benchmarks. Each benchmark is formatted as {bit, BitArray, std}::function (size) [(alignment-tags)].

* `bit` is for this library, `BitArray` is for the popular C-based [BitArray library](https://github.com/noporpoise/BitArray), [dynamic_bitset](https://github.com/pinam45/dynamic_bitset) is a header-only library similar to Boost's dynamic_bitset, and`std` is the standard library operating on the infamous `vector<bool>`. 

• (size) denotes the size of the container in bits. small = 1 << 8, medium= 1 << 16, large = 1 << 24, huge = 1 << 31
• (alignment-tags) refers to the memory alignment of the bit-iterators. U means the iterator does not fall on a word boundary, R means the iterator is placed at random, and A means the iterator is aligned with a word boundary.

For example, bit::rotate (large) (ARA) refers to our library's implementation of the rotate algorithm operating on a container of 65536 bits, where first and last are aligned but n_first is selected at random.

---------------------------------------------------------------------------------------
Benchmark                                             Time             CPU   Iterations
---------------------------------------------------------------------------------------
bit::set (large)                                   1.90 ns         1.90 ns    367974893
dynamic_bitset::set (large)                        2.37 ns         2.37 ns    296837879
bitarray::set (large)                              2.19 ns         2.19 ns    319133940
std::set (large)                                   2.39 ns         2.39 ns    293135332
bit::shift_left (small)                            26.8 ns         26.8 ns     25929070
bit::shift_left (small) (UU)                       22.4 ns         22.4 ns     31233265
dynamic_bitset::shift_left (small)                 13.1 ns         13.1 ns     53627207
bitarray::shift_left (small)                       38.2 ns         38.2 ns     18339126
std::shift_left (small)                             345 ns          345 ns      2029283
bit::shift_left (large)                          371224 ns       371211 ns         1886
bit::shift_left (large) (UU)                     371536 ns       371530 ns         1880
dynamic_bitset::shift_left (large)               638896 ns       638880 ns         1097
bitarray::shift_left (large)                    3156273 ns      3156003 ns          222
std::shift_left (large)                       105227752 ns    105223527 ns            7
bit::shift_right (small)                           26.9 ns         26.9 ns     25976563
bit::shift_right (small) (UU)                      39.3 ns         39.3 ns