BLI_bit_vector.hh File Reference

#include "BLI_allocator.hh"
#include "BLI_bit_bool_conversion.hh"
#include "BLI_bit_span.hh"
#include "BLI_span.hh"

Go to the source code of this file.

Classes
class	blender::bits::BitVector< InlineBufferCapacity, Allocator >

Namespaces
namespace	blender
namespace	blender::bits

Functions
template<int64_t InlineBufferCapacity, typename Allocator >
BoundedBitSpan	blender::bits::to_best_bit_span (const BitVector< InlineBufferCapacity, Allocator > &data)
template<int64_t InlineBufferCapacity, typename Allocator >
MutableBoundedBitSpan	blender::bits::to_best_bit_span (BitVector< InlineBufferCapacity, Allocator > &data)

Detailed Description

A blender::BitVector is a dynamically growing contiguous arrays of bits. Its main purpose is to provide a compact way to map indices to bools. It requires 8 times less memory compared to a blender::Vector<bool>.

Advantages of using a bit- instead of byte-vector are:

• Uses less memory.
• Allows checking the state of many elements at the same time (8 times more bits than bytes fit into a CPU register). This can improve performance.

The compact nature of storing bools in individual bits has some downsides that have to be kept in mind:

• Writing to separate bits in the same int is not thread-safe. Therefore, an existing vector of bool can't easily be replaced with a bit vector, if it is written to from multiple threads. Read-only access from multiple threads is fine though.
• Writing individual elements is more expensive when the array is in cache already. That is because changing a bit is always a read-modify-write operation on the int the bit resides in.
• Reading individual elements is more expensive when the array is in cache already. That is because additional bit-wise operations have to be applied after the corresponding int is read.

Comparison to std::vector<bool>:

• blender::BitVector has an interface that is more optimized for dealing with bits.
• blender::BitVector has an inline buffer that is used to avoid allocations when the vector is small.

Comparison to BLI_bitmap:

• blender::BitVector offers a more C++ friendly interface.
• BLI_bitmap should only be used in C code that can not use blender::BitVector.

Definition in file BLI_bit_vector.hh.