ConcurrentBitset.h File Reference

Variable-sized bitset allowing (mostly) concurrent access. More...

#include "CxxUtils/atomic_fetch_minmax.h"
#include "CxxUtils/features.h"
#include "CxxUtils/ones.h"
#include <climits>
#include <vector>
#include <algorithm>
#include <iterator>
#include <atomic>
#include <mutex>
#include <memory>
#include <type_traits>
#include <cstddef>
#include <bit>
#include "CxxUtils/ConcurrentBitset.icc"

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	CxxUtils::reference
	A reference to one bit in a set. More...
class	CxxUtils::const_iterator
	Iterator over all 1 bits in the set. More...
class	CxxUtils::Impl
	Implementation object. More...

Namespaces
namespace	CxxUtils

Functions
Constructors, destructors, assignment.
Variable-sized bitset allowing (mostly) concurrent access. This class represents a set of bits. One can think of such an object as either like a std::bitset or like a std::set<unsigned>. This class provides basically the union of the two interfaces. In a few cases, the same method has different semantics in the two interfaces, most notably size(). We follow here the semantics that we would get from std::set<unsigned>. (Rationale: The motivation for this class is to replace the existing use of unordered_set<unsigned> for auxid_set_t. Supplying the same interface makes this easier to drop in as a replacement. However, in some cases, the set operations as provided by a bitset-like interface can be much more efficient, so we'd want to provide those as well.) The size of the bitset is specified at runtime, to the constructor. Most operations do not change the size. However, the insert() methods, as well as operator=, may be used to grow the size of the set. Most methods can execute completely concurrently. However, the methods which can change the size of the container, insert() and operator=, are not compatible with other concurrent writes. (Concurrent reads are ok, though.) Some methods can operate on the entire set (e.g., clear()). Such methods may run concurrently with others, but they will not necessarily be atomic: other threads may be able to see the operation partially completed. An iterator is provided that iterates over all bits that are set (like iterating over a set<unsigned>). When the container is expanded, the internal representation needs to be reallocated. The old object is not, however, deleted immediately, as other threads may still be referencing it. If if some point you know that no threads can be referencing old versions any more, you can clean them up by calling emptyGarbage (otherwise, all versions will be deleted when the set object is destroyed). Some notes on motivation: The use case that motivated this class was auxid_set_t, which tells which auxiliary variables are available for a given container. This is logically a relatively sparse set of relatively small integers. (Maximum value is ~2000, with a set having ~100 entries.) This had been implemented as a std::unordered_set<size_t>, but this was not entirely satisfactory. First, in some cases, there was a significant overhead in inserting and deleting items from the set. Second, unordered_set does not allow concurrent reading and writing. This meant that we ended up maintaining thread-local copies of each set, which adds extra overhead and complexity. The threading issue suggests that we would like to use a container that allows readers to run currently with at least one writer. The fact that the maximum value to be stored in these sets is not too large suggests that a bitmap might be a good representation, as long as the time required to iterate over the set doesn't blow up due to the sparseness of the map. To study this, a reconstruction job was instrumented to dump out all unique auxid_set_t values. This corpus was then used to run a set of timing tests for different set implementations. This test is built into the ConcurrentBitset unit test, and the corpus is available in the CxxUtils package. Run like: .../ConcurrentBitset_test.exe --perf .../CxxUtils/share/auxids.uniq Set implementations that have been tested so far include: std::set std::unordered_set concurrent_unordered_set, from TBB ck_hs, from ConcurrencyKit ck_bitmap, from ConcurrencyKit ConcurrentBitset Representative results (times in seconds; lower is better): |--------------------------+------+------+---------+--------| | | fill | copy | iterate | lookup | |--------------------------+------+------+---------+--------| | set | 0.92 | 0.66 | 10.95 | 0.53 | | unordered_set | 1.63 | 0.93 | 6.56 | 0.50 | | concurrent_unordered_set | 1.79 | 1.70 | 9.55 | 1.20 | | ck_hs | 0.78 | 0.83 | 18.92 | 0.88 | | ck_bitmap | 0.13 | 0.21 | 5.52 | 0.05 | | ConcurrentBitset | 0.31 | 0.06 | 4.48 | 0.08 | |--------------------------+------+------+---------+--------| For this workload, the bitmaps are the clear winner. Implementation notes: The implementation here is inspired by ck_bitmap from ConcurrencyKit (http://concurrencykit.org/), though the code is all new. ck_bitmap itself isn't suitable because it doesn't allow for the set to grow, and also because it's a pure C interface, while we want something with a C++ style interface (and in particular something which supports interfaces close to unordered_set<size_t> in order to ease migration). The bitset is stored as an array of std::atomic<Block_t> objects, where Block_t is the largest unsigned type for which atomic is lockless. This is stored in a separate implementation object in order to allow the container to grow. The implementation object has a fixed-size header followed by the variable-size array of blocks. To speed up iteration for the typical case of a sparse set, we maintain a `high-water' mark, m_hwm, which is the index of the highest block that might have a bit set. m_hwm can only increase unless the set is cleared. */ class ConcurrentBitset { private: Forward declaration of implementation class. class Impl; / Internal type used to hold the bitset data. / The bitset is an array of std::atomic<Block_t>. / This type should generally be the largest unsigned type for which / std::atomic is lockless. typedef unsigned long Block_t; / Size, in bits, of Block_t. static const size_t BLOCKSIZE = sizeof(Block_t) * CHAR_BIT; / Mask to select out the bit offset within one Block_t. static const size_t MASK = BLOCKSIZE-1; static_assert (std::atomic<Block_t>::is_always_lock_free); public: / A bit number. typedef size_t bit_t; /**
	CxxUtils::ConcurrentBitset (bit_t nbits=0)
	Constructor.
	CxxUtils::ConcurrentBitset (const ConcurrentBitset &other)
	Copy constructor.
	CxxUtils::ConcurrentBitset (std::initializer_list< bit_t > l, bit_t nbits=0)
	Constructor from an initializer list.
	CxxUtils::ConcurrentBitset (ConcurrentBitset &&other)
	Move constructor.
	CxxUtils::~ConcurrentBitset ()
	Destructor.
ConcurrentBitset &	CxxUtils::operator= (const ConcurrentBitset &other)
	Assignment.
ConcurrentBitset &	CxxUtils::operator= (ConcurrentBitset &&other)
	Move.
void	CxxUtils::emptyGarbage ()
	Clean up old versions of the set.
Size, bit testing
bit_t	CxxUtils::capacity () const
	The number of bits that this container can hold.
bit_t	CxxUtils::count () const
	Count the number of 1 bits in the set.
bit_t	CxxUtils::size () const
	Count the number of 1 bits in the set.
bool	CxxUtils::test (bit_t bit) const
	Test to see if a bit is set.
size_t	CxxUtils::count (bit_t bit) const
	Test to see if a bit is set.
bool	CxxUtils::empty () const
	Return true if there are no 1 bits in the set.
bool	CxxUtils::none () const
	Return true if there are no 1 bits in the set.
bool	CxxUtils::all () const
	Return true if all bits in the set are 1.
bool	CxxUtils::any () const
	Return true if there are any 1 bits in the set.
Single-bit manipulation.
ConcurrentBitset &	CxxUtils::set (bit_t bit)
	Turn on one bit.
ConcurrentBitset &	CxxUtils::reset (bit_t bit)
	Turn off one bit.
ConcurrentBitset &	CxxUtils::erase (bit_t bit)
	Turn off one bit.
ConcurrentBitset &	CxxUtils::flip (bit_t bit)
	Flip the value of one bit.
ConcurrentBitset &	CxxUtils::set (bit_t bit, bool val)
	Set the value of one bit.
Set operations.
ConcurrentBitset &	CxxUtils::clear ()
	Clear all bits in the set.
ConcurrentBitset &	CxxUtils::reset ()
	Clear all bits in the set.
ConcurrentBitset &	CxxUtils::set ()
	Turn on all bits in the set.
ConcurrentBitset &	CxxUtils::flip ()
	Flip the state of all bits in the set.
ConcurrentBitset &	CxxUtils::operator&= (const ConcurrentBitset &other)
	AND this set with another set.
ConcurrentBitset &	CxxUtils::operator|= (const ConcurrentBitset &other)
	OR this set with another set.
ConcurrentBitset &	CxxUtils::operator^= (const ConcurrentBitset &other)
	XOR this set with another set.
ConcurrentBitset &	CxxUtils::operator-= (const ConcurrentBitset &other)
	Subtract another set from this set.
ConcurrentBitset	CxxUtils::operator~ () const
	Return a new set that is the complement of this set.
Comparison.
bool	CxxUtils::operator== (const ConcurrentBitset &other) const
	Test two sets for equality.
bool	CxxUtils::operator!= (const ConcurrentBitset &other) const
	Test two sets for inequality.
Insert.
ConcurrentBitset &	CxxUtils::insert (bit_t bit, bit_t new_nbits=0)
	Set a bit to 1.
template<class ITERATOR, typename = typename std::enable_if< std::is_base_of< typename std::forward_iterator_tag, typename std::iterator_traits<ITERATOR>::iterator_category >::value>>
ConcurrentBitset &	CxxUtils::insert (ITERATOR beg, ITERATOR end, bit_t new_nbits=0)
	Set several bits to 1.
ConcurrentBitset &	CxxUtils::insert (std::initializer_list< bit_t > l, bit_t new_nbits=0)
	Set several bits to 1.
ConcurrentBitset &	CxxUtils::insert (const ConcurrentBitset &other)
	Turn on bits listed in another set.
Array-like element access.
bool	CxxUtils::operator[] (bit_t bit) const
	Return the value of one bit.
Iterator operations.
const_iterator	CxxUtils::begin () const
	Return a begin iterator.
const_iterator	CxxUtils::end () const
	Return an end iterator.
const_iterator	CxxUtils::find (bit_t bit) const
	If bit bit is set, return an iterator pointing to it.

Implementation.
typedef std::mutex	CxxUtils::mutex_t
	Mutex used for synchronization when switching to a new implementation object.
typedef std::lock_guard< mutex_t >	CxxUtils::lock_t
std::atomic< Impl * >	CxxUtils::m_impl
	The current implementation object.
std::vector< Impl * >	CxxUtils::m_garbage
	Old implementation objects, pending deletion.
mutex_t	CxxUtils::m_mutex
	Mutex protecting the container.
static bit_t	CxxUtils::nBlocks (bit_t nbits)
	Find number of blocks needed to hold a given number of bits.
Impl *	CxxUtils::newImpl (bit_t nbits)
	Create a new, uninitialized implementation object.
void	CxxUtils::expand (bit_t new_nbits)
	Expand the container.
void	CxxUtils::expandOol (bit_t new_nbits)
	Expand the container: out-of-line portion.

Detailed Description

Variable-sized bitset allowing (mostly) concurrent access.

Author

scott snyder snyde.nosp@m.r@bn.nosp@m.l.gov

Date

Nov, 2017

Definition in file ConcurrentBitset.h.