boost::dynamic_bitset<> demonstrate poor performance on bit operation since it uses internally an std::vector and allocates on any operation that produces a new bitset, such as bitwise and.

std::vector<> does not allocate on bit operations and, according to our benchmarks, is about 100 times faster that boost::dynamic_bitset<>. Unfortunately, its size must be specified in compile time and, therefore, is not suitable for our purposes.

We need to implement a new dynamic bitset which is:

• uses inlined storage for small bitsets (e.g. <= 64 bits) and, therefore, never allocates on operations with small bitsets
• provides comparable performance to std::bitset<> on small bitsets.

• faster than boost::dynamic_bitset<> on bitsets of any sizes.