CxxUtils::ConcurrentBitset Class Reference

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

#include <ConcurrentBitset.h>

Inheritance diagram for CxxUtils::ConcurrentBitset:

Collaboration diagram for CxxUtils::ConcurrentBitset:

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

Public Types
typedef size_t	bit_t
	A bit number. More...

Private Types
typedef unsigned long	Block_t
	Internal type used to hold the bitset data. More...

Static Private Attributes
static const size_t	BLOCKSIZE = sizeof(Block_t) * CHAR_BIT
	Size, in bits, of Block_t. More...
static const size_t	MASK = BLOCKSIZE-1
	Mask to select out the bit offset within one Block_t. More...

Constructors, destructors, assignment.
	ConcurrentBitset (bit_t nbits=0)
	Constructor. More...
	ConcurrentBitset (const ConcurrentBitset &other)
	Copy constructor. More...
	ConcurrentBitset (std::initializer_list< bit_t > l, bit_t nbits=0)
	Constructor from an initializer list. More...
	ConcurrentBitset (ConcurrentBitset &&other)
	Move constructor. More...
	~ConcurrentBitset ()
	Destructor. More...
ConcurrentBitset &	operator= (const ConcurrentBitset &other)
	Assignment. More...
ConcurrentBitset &	operator= (ConcurrentBitset &&other)
	Move. More...
void	emptyGarbage ()
	Clean up old versions of the set. More...

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

Detailed Description

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.

Definition at line 145 of file ConcurrentBitset.h.

Member Typedef Documentation

bit_t

typedef size_t CxxUtils::ConcurrentBitset::bit_t

A bit number.

Definition at line 168 of file ConcurrentBitset.h.

Block_t

typedef unsigned long CxxUtils::ConcurrentBitset::Block_t

private

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.

Definition at line 155 of file ConcurrentBitset.h.

lock_t

typedef std::lock_guard<mutex_t> CxxUtils::ConcurrentBitset::lock_t

private

Definition at line 1075 of file ConcurrentBitset.h.

mutex_t

typedef std::mutex CxxUtils::ConcurrentBitset::mutex_t

private

Mutex used for synchronization when switching to a new implementation object.

Definition at line 1074 of file ConcurrentBitset.h.

Constructor & Destructor Documentation

ConcurrentBitset() [1/4]

CxxUtils::ConcurrentBitset::ConcurrentBitset

(

bit_t

nbits = 0

)

Constructor.

Parameters

nbits

Initial number of bits to allocate for the map.

Definition at line 26 of file ConcurrentBitset.cxx.

  : m_impl (new (nbits) Impl (nbits))
{
}

ConcurrentBitset() [2/4]

CxxUtils::ConcurrentBitset::ConcurrentBitset

(

const ConcurrentBitset &

other

)

Copy constructor.

Parameters

other

Container to copy.

The copy is not atomic. If a non-atomic update is simultaneously made to other, then the copy may have this update only partially completed.

Definition at line 39 of file ConcurrentBitset.cxx.

  : m_impl (new ((*other.m_impl).nbits()) Impl ((*other.m_impl)))
{
}

ConcurrentBitset() [3/4]

CxxUtils::ConcurrentBitset::ConcurrentBitset	(	std::initializer_list< bit_t >	l,
		bit_t	nbits = 0
	)

Constructor from an initializer list.

Parameters

List	of values to set.
nbits	Number of bits to allocate for the map. If 0, then set the size based on the maximum value in the list.

This allows setting specific bits in the set, like

ConcurrentBitset bs { 1, 5, 10};

Definition at line 56 of file ConcurrentBitset.cxx.

{
  if (nbits == 0) {
    // Set the size of the set based on the maximum value in the list.
    auto max_it = std::max_element (l.begin(), l.end());
    if (max_it != l.end()) {
      nbits = *max_it + 1;
    }
    // Round up.
    nbits = (nbits + BLOCKSIZE-1) & ~MASK;
  }
  m_impl = new (nbits) Impl (nbits);
  for (bit_t b : l) {
    set (b);
  }
}

ConcurrentBitset() [4/4]

CxxUtils::ConcurrentBitset::ConcurrentBitset

(

ConcurrentBitset &&

other

)

Move constructor.

Parameters

other

Container to move.

No concurrent access may be in progress on other. After this returns, other can only be deleted.

Definition at line 82 of file ConcurrentBitset.cxx.

{
  other.emptyGarbage();
  Impl* impl = other.m_impl;
  other.m_impl = nullptr;
  m_impl = impl;
}

~ConcurrentBitset()

CxxUtils::ConcurrentBitset::~ConcurrentBitset

(

)

Destructor.

Definition at line 94 of file ConcurrentBitset.cxx.

{
  delete m_impl;
  emptyGarbage();
}

Member Function Documentation

all()

bool CxxUtils::ConcurrentBitset::all

(

)

const

Return true if all bits in the set are 1.

any()

bool CxxUtils::ConcurrentBitset::any

(

)

const

Return true if there are any 1 bits in the set.

begin()

const_iterator CxxUtils::ConcurrentBitset::begin

(

)

const

Return a begin iterator.

capacity()

bit_t CxxUtils::ConcurrentBitset::capacity

(

)

const

The number of bits that this container can hold.

clear()

ConcurrentBitset& CxxUtils::ConcurrentBitset::clear

(

)

Clear all bits in the set.

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

count() [1/2]

bit_t CxxUtils::ConcurrentBitset::count

(

)

const

Count the number of 1 bits in the set.

count() [2/2]

size_t CxxUtils::ConcurrentBitset::count

(

bit_t

bit

)

const

Test to see if a bit is set.

Parameters

bit	Number of the bit to test.

Returns

1 if the bit is set; 0 otherwise.

Returns 0 if bit is beyond the end of the set.

empty()

bool CxxUtils::ConcurrentBitset::empty

(

)

const

Return true if there are no 1 bits in the set.

emptyGarbage()

void CxxUtils::ConcurrentBitset::emptyGarbage

(

)

Clean up old versions of the set.

The insert and assignment operations may need to grow the set. The original version of the set is not deleted immediately, since other threads may still be accessing it. Call this when no other threads can be accessing old versions in order to clean them up.

Definition at line 148 of file ConcurrentBitset.cxx.

{
  lock_t lock (m_mutex);
  for (Impl* p : m_garbage) {
    free (p);
  }
  m_garbage.clear();
}

end()

const_iterator CxxUtils::ConcurrentBitset::end

(

)

const

Return an end iterator.

erase()

ConcurrentBitset& CxxUtils::ConcurrentBitset::erase

(

bit_t

bit

)

Turn off one bit.

Parameters

bit	The bit to turn off.

Does nothing if bit beyond the end of the set.

expand()

void CxxUtils::ConcurrentBitset::expand ( bit_t  new_nbits )

private

Expand the container.

Parameters

new_nbits

The desired new size of the container.

expandOol()

void CxxUtils::ConcurrentBitset::expandOol ( bit_t  new_nbits )

private

Expand the container: out-of-line portion.

Parameters

new_nbits

The desired new size of the container.

Definition at line 162 of file ConcurrentBitset.cxx.

{
  // Need to take out the lock.
  lock_t lock (m_mutex);
  // Check the size again while we're holding the lock.
  bit_t nbits = (*m_impl).nbits();
  if (new_nbits > nbits) {
    // We need to expand.  Allocate a new implementation and initialize it,
    // copying from the existing implementation.
    Impl* i = new (new_nbits) Impl (*m_impl, new_nbits);
 
    // Remember that we need to delete the old object.
    m_garbage.push_back (m_impl);
 
    // Publish the new one.
    m_impl = i;
  }
}

find()

const_iterator CxxUtils::ConcurrentBitset::find

(

bit_t

bit

)

const

If bit bit is set, return an iterator pointing to it.

Otherwise, return an end iterator.

Parameters

bit	Bit number to test.

flip() [1/2]

ConcurrentBitset& CxxUtils::ConcurrentBitset::flip

(

)

Flip the state of all bits in the set.

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

flip() [2/2]

ConcurrentBitset& CxxUtils::ConcurrentBitset::flip

(

bit_t

bit

)

Flip the value of one bit.

Parameters

bit	The bit to turn flip.

Does nothing if bit beyond the end of the set.

insert() [1/4]

ConcurrentBitset& CxxUtils::ConcurrentBitset::insert	(	bit_t	bit,
		bit_t	new_nbits = 0
	)

Set a bit to 1.

Expand the set if needed.

Parameters

bit	Number of the bit to set.
new_nbits	Hint for new size of set, if it needs to be expanded.

If bit is past the end of the container, then the container will be expanded as needed.

This operation is incompatible with any other simultaneous writes to the same set (reads are ok).

insert() [2/4]

ConcurrentBitset& CxxUtils::ConcurrentBitset::insert

(

const ConcurrentBitset &

other

)

Turn on bits listed in another set.

Parameters

other

Set of bits to turn on.

This is the same as operator|=, except that if the size of other is larger than this set, then this set will be expanded to match other.

This operation is incompatible with any other simultaneous writes to the same set (reads are ok).

insert() [3/4]

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::ConcurrentBitset::insert	(	ITERATOR	beg,
		ITERATOR	end,
		bit_t	new_nbits = 0
	)

Set several bits to 1.

Expand the set if needed.

Parameters

beg	Start of range of bits to set.
end	End of range of bits to set.
new_nbits	Hint for new size of set, if it needs to be expanded.

The iteration range should be over something convertible to bit_t. If any bit is past the end of the container, then the container will be expanded as needed.

This operation is incompatible with any other simultaneous writes to the same set (reads are ok).

Example:

std::vector<bit_t> bits { 4, 10, 12};
CxxUtils::ConcurrentBitset bs = ...;
bs.insert (bits.begin(), bits.end());

insert() [4/4]

ConcurrentBitset& CxxUtils::ConcurrentBitset::insert	(	std::initializer_list< bit_t >	l,
		bit_t	new_nbits = 0
	)

Set several bits to 1.

Expand the set if needed.

Parameters

l	List of bits to set.
new_nbits	Hint for new size of set, if it needs to be expanded.

If any bit is past the end of the container, then the container will be expanded as needed.

This operation is incompatible with any other simultaneous writes to the same set (reads are ok).

Example:

std::vector<bit_t> bits { 4, 10, 12};
bs.insert ({4, 10, 12});

nBlocks()

static bit_t CxxUtils::ConcurrentBitset::nBlocks ( bit_t  nbits )

staticprivate

Find number of blocks needed to hold a given number of bits.

Parameters

nbits

The number of bits.

newImpl()

Impl* CxxUtils::ConcurrentBitset::newImpl ( bit_t  nbits )

private

Create a new, uninitialized implementation object.

Parameters

nbits

Number of bits to allocate.

This will allocate memory for the Impl object, but will does not run the constructor.

none()

bool CxxUtils::ConcurrentBitset::none

(

)

const

Return true if there are no 1 bits in the set.

operator!=()

bool CxxUtils::ConcurrentBitset::operator!=

(

const ConcurrentBitset &

other

)

const

Test two sets for inequality.

Parameters

other

The other set to test.

operator&=()

ConcurrentBitset& CxxUtils::ConcurrentBitset::operator&=

(

const ConcurrentBitset &

other

)

AND this set with another set.

Parameters

other

The other set.

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

operator-=()

ConcurrentBitset& CxxUtils::ConcurrentBitset::operator-=

(

const ConcurrentBitset &

other

)

Subtract another set from this set.

Parameters

other

The other set.

This is the same as (*this) &= ~other;

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

operator=() [1/2]

ConcurrentBitset & CxxUtils::ConcurrentBitset::operator=

(

ConcurrentBitset &&

other

)

Move.

Parameters

other

Bitset from which to move.

No concurrent access may be in progress on other. After this returns, other can only be deleted.

Definition at line 126 of file ConcurrentBitset.cxx.

{
  if (this != &other) {
    emptyGarbage();
    other.emptyGarbage();
    delete m_impl;
    Impl* impl = other.m_impl;
    other.m_impl = nullptr;
    m_impl = impl;
  }
  return *this;
}

operator=() [2/2]

ConcurrentBitset & CxxUtils::ConcurrentBitset::operator=

(

const ConcurrentBitset &

other

)

Assignment.

Parameters

other

Bitset from which to assign.

The copy is not atomic. If a non-atomic update is simultaneously made to other, then the copy may have this update only partially completed.

Definition at line 108 of file ConcurrentBitset.cxx.

{
  if (this != &other) {
    const Impl* otherImpl = other.m_impl;
    expand (otherImpl->nbits());
    (*m_impl).assign (*otherImpl);
  }
  return *this;
}

operator==()

bool CxxUtils::ConcurrentBitset::operator==

(

const ConcurrentBitset &

other

)

const

Test two sets for equality.

Parameters

other

The other set to test.

operator[]() [1/2]

reference CxxUtils::ConcurrentBitset::operator[]

(

bit_t

bit

)

Return a reference to one bit.

Parameters

bit	The number of the bit to reference.

The reference will be invalidated by calls to insert() or operator=. Effects are undefined if bit is past the end of the set.

operator[]() [2/2]

bool CxxUtils::ConcurrentBitset::operator[]

(

bit_t

bit

)

const

Return the value of one bit.

Parameters

bit	The number of the bit to test.

operator^=()

ConcurrentBitset& CxxUtils::ConcurrentBitset::operator^=

(

const ConcurrentBitset &

other

)

XOR this set with another set.

Parameters

other

The other set.

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

operator|=()

ConcurrentBitset& CxxUtils::ConcurrentBitset::operator|=

(

const ConcurrentBitset &

other

)

OR this set with another set.

Parameters

other

The other set.

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

operator~()

ConcurrentBitset CxxUtils::ConcurrentBitset::operator~

(

)

const

Return a new set that is the complement of this set.

reset() [1/2]

ConcurrentBitset& CxxUtils::ConcurrentBitset::reset

(

)

Clear all bits in the set.

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

reset() [2/2]

ConcurrentBitset& CxxUtils::ConcurrentBitset::reset

(

bit_t

bit

)

Turn off one bit.

Parameters

bit	The bit to turn off.

Does nothing if bit beyond the end of the set.

set() [1/3]

ConcurrentBitset& CxxUtils::ConcurrentBitset::set

(

)

Turn on all bits in the set.

This operation is not necessarily atomic; a simultaneous read may be able to see the operation partially done.

set() [2/3]

ConcurrentBitset& CxxUtils::ConcurrentBitset::set

(

bit_t

bit

)

Turn on one bit.

Parameters

bit	The bit to turn on.

Does nothing if bit beyond the end of the set.

set() [3/3]

ConcurrentBitset& CxxUtils::ConcurrentBitset::set	(	bit_t	bit,
		bool	val
	)

Set the value of one bit.

Parameters

bit	The bit to turn set.
val	The value to which to set it.

Does nothing if bit beyond the end of the set.

size()

bit_t CxxUtils::ConcurrentBitset::size

(

)

const

Count the number of 1 bits in the set.

Note: If you regard this like a std::bitset, you would expect this to return the number of bits that the set can hold, while if you regard this like a set<bit_t>, then you would expect this to return the number of 1 bits. We follow the latter here.

test()

bool CxxUtils::ConcurrentBitset::test

(

bit_t

bit

)

const

Test to see if a bit is set.

Parameters

bit	Number of the bit to test.

Returns

true if the bit is set; false otherwise.

Returns false if bit is beyond the end of the set.

Member Data Documentation

BLOCKSIZE

const size_t CxxUtils::ConcurrentBitset::BLOCKSIZE = sizeof(Block_t) * CHAR_BIT

staticprivate

Size, in bits, of Block_t.

Definition at line 158 of file ConcurrentBitset.h.

m_garbage

std::vector<Impl*> CxxUtils::ConcurrentBitset::m_garbage

private

Old implementation objects, pending deletion.

Definition at line 1071 of file ConcurrentBitset.h.

m_impl

std::atomic<Impl*> CxxUtils::ConcurrentBitset::m_impl

private

The current implementation object.

Definition at line 1068 of file ConcurrentBitset.h.

m_mutex

mutex_t CxxUtils::ConcurrentBitset::m_mutex

private

Definition at line 1076 of file ConcurrentBitset.h.

MASK

const size_t CxxUtils::ConcurrentBitset::MASK = BLOCKSIZE-1

staticprivate

Mask to select out the bit offset within one Block_t.

Definition at line 161 of file ConcurrentBitset.h.

---

The documentation for this class was generated from the following files:

• ConcurrentBitset.h
• ConcurrentBitset.cxx