Coalesced "bit"-thread-safe vector

Question

As far as I know:

vector<bool> involves coalescing vector elements, that is: V[i] occupies a single bit, instead of sizeof(bool) bytes.
"Coalesced" vector<bool> is not "bit"-thread-safe, meaning that concurrent writes, even to different positions, do not guarantee the absence of data races (a nice discussion around the standardized "vector" vector<bool> is to be found here).
It would be great, but no: vector<std::atomic_bool> does not involve low-level coalescing.
Even using std::bitset is not bit-thread-safe (here).

Given all of that, here is my question: how would you implement a coalesced vector<bool> such that concurrent writes to different position/bits are thread-safe?

How important is space usage ? One way would be to use a vector and store zeros and ones. But yeah, 32 (64?) times the storage cost. — Jeffrey, Jul 19 '19 at 14:18
My question is precise: I need each bool to be represented with a single bit. — grd, Jul 19 '19 at 14:21

eerorika · Answer 1 · 2019-07-19T14:31:01.200

2

You can use general concurrency patterns with locks. Do take into consideration that the space saving are probably gained at the cost of runtime performance.

Example:

std::vector<bool> b(size);
std::mutex m;

//modify:
{
    std::lock_guard lock(m);
    b[0] = true;
}

// read
{
    std::lock_guard lock(m);
    std::cout << b[0];
}

You can use std::shared_mutex if you want shared read locking.

edited Jul 19 '19 at 14:31

answered Jul 19 '19 at 14:25

eerorika

232,697
12
197
326

The answer could be improve by stating the runtime cost. IMO, it would make it as efficient as a single-thread version. But yeah, maybe performance is not important – Jeffrey Jul 19 '19 at 14:31
@Jeffrey I just happened to add mention of runtime cost less than a minute before your comment (i.e. probably while you were typing). It's "as efficient as single threaded version" only if the thread does nothing else other than access the vector. In fact, it will be slower due to the syncrhonisation. But if access to the structure is infrequent, and if it is large enough to have significant space saving, this might in theory be efficient. – eerorika Jul 19 '19 at 14:34
yeah, agreed, +1. Maybe I'm stuck in my high-performance world :-) – Jeffrey Jul 19 '19 at 14:35

score 0 · Answer 2 · answered Jul 19 '19 at 15:21

@eerorika provide the simplest answer if you need a vector. If you want a highly efficient structure, though, you can use an std::array<std::atomic<uint32_t>>. Then you can avoid locking altogether:

template<int size>
class FastBits
{
public:
    void set(unsigned int pos, bool value)
    {
        if (value)
        {
            mValues[pos / 32] |= (1 << (pos % 32));
        }
        else
        {
            mValues[pos / 32] &= ~(1 << (pos % 32));
        }
    }
    bool get(unsigned int pos)
    {
        return mValues[pos / 32] & (1 << (pos % 32));
    }

private:
    std::array<std::atomic<uint32_t>, (size + 31) / 32> mValues;
};

#include <iostream>
int main()
{
    constexpr int size = 10;
    FastBits<size> f;

    f.set(8, true);
    std::cout << f.get(8) << std::endl;

    f.set(8, false);
    std::cout << f.get(8) << std::endl;
}

Coalesced "bit"-thread-safe vector

2 Answers2