Bits¶
Sometimes it can be benefitial to work with bits directly instead of boolean values because they are very compact and many bits can be processed at the same time. This document describes some of the utilities available for working with dynamically-sized bitsets.
Before choosing to work with individual bits instead of bools, keep in mind that there are also downsides which may not be obvious at first.
- Writing to separate bits in the same int is not thread-safe. Therefore, an existing vector of bool can't necessarily be replaced with a bit vector when it is written to from multiple threads. Read-only access from multiple threads is fine though.
- Writing an individual element is more expensive when the array is in cache already, because changing a bit is always a read-modify-write operation on the integer containing the bit.
- Reading an individual element is more expensive when the array is in cache already, because additional bit-wise operations have to be applied after the corresponding int is read.
BitVector¶
The most common type to use when working with bits is blender::BitVector (source). It's a dynamically growing contiguous array of bits. As such it has similarities to blender::Vector<bool>, but also std::vector<bool>. In contrast to both, BitVector has an API that is more optimized for dealing with bits.
Just like blender::Vector, BitVector also supports an inline buffer. This is especially benefitial here, because many bits can be stored directly in the BitVector without significantly increasing its size.
/* Construct bit vector with 500 bits which a false/0 by default. */
BitVector<> values(500, false);
/* Setting a bit. */
values[10].set();
/* Setting a bit to a specific value. */
values[10].set(true);
/* Resetting a bit. */
values[10].reset();
/* Check if a bit is set. */
values[10].test();
/* It's also possible to use implicit conversions instead. */
if (values[10]) { /* ... */ }
BitRef¶
It's not possible to have a pointer or reference to specific bit with standard C++. Instead, there are the BitRef and MutableBitRef types (source) which can reference individual bits.
Those are also the types returned when accessing a specific index in BitVector.
BitSpan¶
Just like it's not possible to reference a single bit with standard C++, it's also not possible to reference a span of bits. Instead, one can use BitSpan and MutableBitSpan (source).
Additionally, there are also BoundedBitSpan and MutableBoundedBitSpan. Those are like normal bit spans but enforce specific constraints on the alignment of the span. These additional constraints allow bit spans to be processed more efficiently than in the most general case. For more details on the exact constraints, check the is_bounded_span function.
It's generally recommended to work with bit spans that follow these constraints if possible for best performance.
BitSpan Operations¶
There are three core operations that can be performed on bit spans: 1. Mix multiple bit spans together in some way and store the result in another bit span. 2. Check if any bit is set. 3. Iterate over all set bits.
BLI_bit_span_ops.hh (source) offers utilities for these operations.
BitVector<> vec1(500);
BitVector<> vec2(500);
BitVector<> result(500);
/* Or vec1 into result. */
result |= vec1;
/* Invert result bits. */
bits::invert(result);
/* Check if two bit spans have common bits set. */
bits::has_common_set_bits(vec1, vec2);
/* Iterate over set bits. */
bits::foreach_1_index(result, [&](const int64_t i) { /* ... */ });
/* Perform custom function on bits. */
bits::mix_into_first_expr([](bits::BitInt result,
bits::BitInt vec1,
bits::BitInt vec2) { return result ^ (vec1 | vec2); },
result,
vec1,
vec2);
BitGroupVector¶
BitGroupVector (source) allows storing a fixed number of bits for each element. For example, this could be used to store a bit for each attribute for each vertex in a mesh.
In some sense, this data structure is also 2D bit vector that can dynamically grow on one axis.
BitGroupVector is designed so that the each bit group fullfills the requirements of bounded bit spans (BoundedBitSpan). As such, they can be processed efficiently.