Thread-safe BitArray

Question

Notes:

• supports 64-bit platforms only
• ulong used where negative values make no sense
• library functions are assumed to be correct (whether they actually do what I want or not is a subject for another post)
• the thread-safe implementation will ideally be refactored so that it ends up in another class but this way makes it easier for me to ensure correctness during development

This is my first real adventure in writing a thread-safe class. With the above notes taken into account, did I screw anything up in a way that might violate my thread-safe claim or am I performing any unncessary operations?

Code:

public sealed class BitVector : IEnumerable<bool>
{
    private readonly long[] m_bits;
    private readonly bool m_isThreadSafe;
    private readonly ulong m_length;

    private long m_version = 0L;

    public bool this[long index] {
        get {
            return this[checked((ulong)index)];
        }
        set {
            this[checked((ulong)index)] = value;
        }
    }
    [CLSCompliant(false)]
    public bool this[ulong index] {
        get {
            if (m_length > index) {
                if (m_isThreadSafe) {
                    return BTConcurrent.AtomicRead(ref m_bits[(index / 64UL)]).IsBitSet(checked((int)index.Mod64()));
                }
                else {
                    return m_bits[(index / 64UL)].IsBitSet(checked((int)index.Mod64()));
                }
            }
            else {
                throw new ArgumentOutOfRangeException(paramName: nameof(index));
            }
        }
        set {
            if (m_length > index) {
                if (value) {
                    if (m_isThreadSafe) {
                        unchecked { BTConcurrent.AtomicIncrement(ref m_version); }

                        BTConcurrent.AtomicSetBit(ref m_bits[unchecked(index / 64UL)], checked((int)index.Mod64()));
                    }
                    else {
                        m_bits[unchecked(index / 64UL)].SetBit(checked((int)index.Mod64()));
                    }
                }
                else {
                    if (m_isThreadSafe) {
                        unchecked { BTConcurrent.AtomicIncrement(ref m_version); }

                        BTConcurrent.AtomicClearBit(ref m_bits[unchecked(index / 64UL)], checked((int)index.Mod64()));
                    }
                    else {
                        m_bits[unchecked(index / 64UL)].ClearBit(checked((int)index.Mod64()));
                    }
                }
            }
            else {
                throw new ArgumentOutOfRangeException(paramName: nameof(index));
            }
        }
    }
    public long Length {
        get {
            return checked((long)UnsignedLength);
        }
    }
    [CLSCompliant(false)]
    public ulong UnsignedLength {
        get {
            return m_length;
        }
    }

    [CLSCompliant(false)]
    public BitVector(ulong length, long initBitPattern, bool isThreadSafe) {
        m_bits = new long[((length / 64UL) + Convert.ToUInt64(length.Mod64().IsPositive()))];
        m_isThreadSafe = isThreadSafe;
        m_length = length;

        if (initBitPattern != 0L) {
            SetAll(initBitPattern);
        }
    }
    [CLSCompliant(false)]
    public BitVector(ulong length, bool isThreadSafe) : this(length, 0L, isThreadSafe) { }
    [CLSCompliant(false)]
    public BitVector(ulong length) : this(length, false) { }

    [CLSCompliant(false)]
    public void And(long bitPattern, ulong count) {
        And(this, bitPattern, count);
    }
    public void AndAll(long bitPattern) {
        And(bitPattern, unchecked((ulong)m_bits.LongLength));
    }
    [CLSCompliant(false)]
    public void Clear(ulong count) {
        SetAll(0L, count);
    }
    public void ClearAll() {
        SetAll(0L, unchecked((ulong)m_bits.LongLength));
    }
    public IEnumerator<bool> GetEnumerator() {
        if (m_isThreadSafe) {
            var versionSnapshot = BTConcurrent.AtomicRead(ref m_version);

            for (var i = 0UL; i < UnsignedLength; i++) {
                if (versionSnapshot == BTConcurrent.AtomicRead(ref m_version)) {
                    yield return this[i];
                }
                else {
                    throw new InvalidOperationException(message: "data was mutated during enumeration, unable to continue");
                }
            }
        }
        else {
            for (var i = 0UL; i < UnsignedLength; i++) {
                yield return this[i];
            }
        }
    }
    [CLSCompliant(false)]
    public void Or(long bitPattern, ulong count) {
        Or(this, bitPattern, count);
    }
    public void OrAll(long bitPattern) {
        Or(bitPattern, unchecked((ulong)m_bits.LongLength));
    }
    [CLSCompliant(false)]
    public void Not(long bitPattern, ulong count) {
        Not(this, bitPattern, count);
    }
    public void NotAll(long bitPattern) {
        Not(bitPattern, unchecked((ulong)m_bits.LongLength));
    }
    [CLSCompliant(false)]
    public void SetAll(long bitPattern, ulong count) {
        Set(this, bitPattern, count);
    }
    public void SetAll(long bitPattern) {
        SetAll(bitPattern, ((ulong)m_bits.LongLength));
    }
    public void SetAll() {
        SetAll(-1L);
    }
    public void SetEven() {
        OrAll(6148914691236517205L /* equivalent to 1010....1010 */);
    }
    public void SetOdd() {
        OrAll(-6148914691236517206L /* equivalent to 0101....0101 */);
    }
    [CLSCompliant(false)]
    public void Xor(long bitPattern, ulong count) {
        Xor(this, bitPattern, count);
    }
    public void XorAll(long bitPattern) {
        Xor(bitPattern, ((ulong)m_bits.LongLength));
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
        return GetEnumerator();
    }

    private static void And(BitVector bitVector, long bitPattern, ulong count) {
        if (count > unchecked((ulong)bitVector.m_bits.Length)) {
            throw new ArgumentOutOfRangeException(paramName: nameof(count));
        }

        if (bitVector.m_isThreadSafe) {
            unchecked { BTConcurrent.AtomicIncrement(ref bitVector.m_version); }

            for (var i = 0UL; i < count; i++) {
                BTConcurrent.AtomicAndAssign(ref bitVector.m_bits[i], bitPattern);
            }
        }
        else {
            for (var i = 0UL; i < count; i++) {
                bitVector.m_bits[i] &= bitPattern;
            }
        }
    }
    private static void Not(BitVector bitVector, long bitPattern, ulong count) {
        if (count > unchecked((ulong)bitVector.m_bits.Length)) {
            throw new ArgumentOutOfRangeException(paramName: nameof(count));
        }

        if (bitVector.m_isThreadSafe) {
            unchecked { BTConcurrent.AtomicIncrement(ref bitVector.m_version); }

            for (var i = 0UL; i < count; i++) {
                BTConcurrent.AtomicNotAssign(ref bitVector.m_bits[i]);
            }
        }
        else {
            for (var i = 0UL; i < count; i++) {
                bitVector.m_bits[i] = (~bitPattern);
            }
        }
    }
    private static void Or(BitVector bitVector, long bitPattern, ulong count) {
        if (count > unchecked((ulong)bitVector.m_bits.Length)) {
            throw new ArgumentOutOfRangeException(paramName: nameof(count));
        }

        if (bitVector.m_isThreadSafe) {
            unchecked { BTConcurrent.AtomicIncrement(ref bitVector.m_version); }

            for (var i = 0UL; i < count; i++) {
                BTConcurrent.AtomicOrAssign(ref bitVector.m_bits[i], bitPattern);
            }
        }
        else {
            for (var i = 0UL; i < count; i++) {
                bitVector.m_bits[i] |= bitPattern;
            }
        }
    }
    private static void Set(BitVector bitVector, long bitPattern, ulong count) {
        if (count > unchecked((ulong)bitVector.m_bits.Length)) {
            throw new ArgumentOutOfRangeException(paramName: nameof(count));
        }

        if (bitVector.m_isThreadSafe) {
            unchecked { BTConcurrent.AtomicIncrement(ref bitVector.m_version); }

            for (var i = 0UL; i < count; i++) {
                BTConcurrent.AtomicWrite(ref bitVector.m_bits[i], bitPattern);
            }
        }
        else {
            for (var i = 0UL; i < count; i++) {
                bitVector.m_bits[i] = bitPattern;
            }
        }
    }
    private static void Xor(BitVector bitVector, long bitPattern, ulong count) {
        if (count > unchecked((ulong)bitVector.m_bits.Length)) {
            throw new ArgumentOutOfRangeException(paramName: nameof(count));
        }

        if (bitVector.m_isThreadSafe) {
            unchecked { BTConcurrent.AtomicIncrement(ref bitVector.m_version); }

            for (var i = 0UL; i < count; i++) {
                BTConcurrent.AtomicXorAssign(ref bitVector.m_bits[i], bitPattern);
            }
        }
        else {
            for (var i = 0UL; i < count; i++) {
                bitVector.m_bits[i] ^= bitPattern;
            }
        }
    }
}

Answer 1

Thread Safety

This looks mildly terrifying... I'm going to assume that all the Atomic* methods in BTConcurrent are also themselves thread-safe.

Unless I'm missing something, your code is only thread-save on an individual entry (each ulong in m_bits) level (i.e. you can't end up with a 'broken' ulong), and is otherwise completely unsafe.

Multi-Entry Mutators

All of the methods which operate on multiple entries in m_bits are dodgy, because even though the individual operations may be thread safe, an And might 'overtake' an Or running at the same time from any index (i.e. it's unhelpful to ask which runs first), which doesn't sound like intended behaviour (and judging by the presence of GetEnumerator() is not.

That wasn't very clear, so a very simple example. If you start with 2 entries (ulongs) in m_bits, but 0UL, and then on separate threads run SetAll() and ClearAll(), it is possible to end up with any of four outcomes. Indeed, for n entries, the scheduling may run in such a way that a 'simultaneous' SetAll() and ClearAll() could produce any of the 2^n binary patterns possible.

I think we can all agree that calling SetAll() and ClearAll() should either results in nothing but 1s or nothing but 0s. It might be fun for you to try this situation out with a big BitVector or two, and many SetAll() ClearAll() calls, to see if you can get some crazy results. This is essentially the same reason you have methods for just to read/write a ulong, because on a 32bit machine, it is possible that one half of the 64bit number will be set by one thread, and then overwritten by another which then writes the other half, before that is overwritten by the original thread, leaving you with a 'broken' ulong. Incidentally, I can think of no reason why this code should be 64bit only, as long as you use proper atomic reads and writes (which I'm assuming those in BTConcurrent are) then it should work on any machine.

m_version

(I take it is only used for snapshotting?) In each of the mutators, you increment the m_version independently of changing m_bits: this means that there is time when the version is unchanged but the data has changed, which will breaks GetEnumerator. This means, if you start with all 0s, and call SetAll(), it will update the version before doing anything else. At this point, GetEnumerator() may run, remember this new version, and start yielding values (lots of 0s). SetAll() may overtake GetEnumerator(), and then GetEnumerator() will start yielding 1s.

As an aside, a comment somewhere explaining that m_version is meaningless without m_isThreadSafe set would be appreciated.

GetEnumerator()

This is faulty owing to the issues with m_version (i.e. may appear to run fine, but actually it is lying). However, even more fundamentally, you are checking m_version, and then returning a value. There is no reason that m_version and the data itself shouldn't change in this time.

How to fix it?

Easy locking

(My apologies if you've tried locking already and it's too slow; this is worth adding for other people).

A reliable, simple, and relatively difficult-to-get-wrong solution would be to throw locks at your code. C# has the lovely lock statement which makes this easy and keeps the code clean.

Essentially, it allows you to exclude other threads from access blocks of code whilst another 'holds' the lock (underneath it is monitors and lots of memory barriers). The simplest solution would be to just lock all your code which writes (reading is another kettle of fish) so that only one thread can change the state at a time.

For example:

private readonly object LocalLock = new object(); // per-instance mutex provider
private static void And(BitVector bitVector, long bitPattern, ulong count) {
    if (count > unchecked((ulong)bitVector.m_bits.Length)) {
        throw new ArgumentOutOfRangeException(paramName: nameof(count));
    }

    if (bitVector.m_isThreadSafe) {
        lock (LocalLock)
        {
            m_version++;

            for (var i = 0UL; i < count; i++) {
                bitVector.m_bits[i] &= bitPattern;
            }
        }
    }
    else {
        for (var i = 0UL; i < count; i++) {
            bitVector.m_bits[i] &= bitPattern;
        }
    }
}

Note that I've removed all the BTConcurrent stuff, because the lock keyword provides strong guarantees about memory access and such (which makes it relatively expensive, but easy and dependable).

Other than the costs of keeping the memory in sync, this simple locking scheme can leave threads stalled for a long time when in theory they could be doing work. If you lock your reads as well, then the enumerator will block writes (it won't ever fail, though!).

Complex 'Locking'

Using lock is easy, but can stall threads completely when they could be doing work. Ignoring reading for the moment, suppose an And is run just after an Or. In theory, you could Or one of the ulongs in m_bits, and then And it immediately afterwards, but with dumb locking, the And has to wait until the Or has modified every entry in m_bits.

Unfortunately, this is a non-trivial data-structure to make concurrent, so there is no 'just use CAS to make it faster' option, the cost won't be with the locks but with the blocking itself.

You could write some terrifying code that allows these operations to 'chase' each other along the array. This would be a lot of effort, and would require per-entry symbols to 'lock' on. The simplest solution would probably to have a per-entry version count, and use 'CAS' (Compare and Set (Exchange)) (See System.Threading.Interlocked) to efficiently block on each entry. This would only apply to those methods that modify multiple entries; the indexer would be different, and you'd have to decide the behaviour (you'd have to decide it before writing the other code, though, because it will definitely influence the implementation). Simply performing atomic operations as you are at the moment will not simply work because of issues with reading, even if the write-ordering is a non-issue.

Reading

You could make GetEnumerator() lock up the object and make a copy to ensure a complete and meaningful read (locking and yield return might create problems if you never fully consume the enumerable, but perhaps this is OK with you). If not, you need to check the version before reading (with a lock, to ensure any updates from that version are committed), and after reading, to ensure that it hasn't changed since that version would applied (this still needs a memory-barrier of some sort to ensure that your thread has the most up-to-date version, but wouldn't need a full lock).

Style

I've not seen m_ used in C# (C++ background?), you may want to check out the C# coding conventions, but the exposed API looks mostly fine.

Postamble

As far as I'm aware, a lot of accurate information about threading (C#/.NET) can be found here, and is, in my opinion, also very well written. It has lots of examples - which having written your code you'll be able to relate to and understand why they are important - that are worth going through. I should really go back and read it myself...

Thread Racing Pictures

This picture shows one interleaving

This picture shows another

This pictures shows the same with an added m_writer_count, which indicates when the data-structure is being modified, so that GetEnumerable can detect it and throw.

If you don't mind these kinds of errors, then there is no need for m_version, and judicious use of thread-safe atomic reads and writes as present in your original code is sufficient to prevent any 'broken' or 'corrupted' ulongs from being yielded by GetEnumerator.

Answer 2

You don't need perform divisions like index / 64UL (where index is ulong) in an unchecked context since overflow will never occur in this case. Also you don't need UL suffix for 64.

---

Are you sure you need such "big" types for indexers parameters as long and ulong? I would work with int and uint only since it is more than enough.

---

In CLS compliant version of the indexer you should check if argument is negative and cast it to ulong without checked context:

public bool this[long index]
{
    get
    {
        if (index < 0)
            throw new ArgumentOutOfRangeException(nameof(index), index, "Index is negative.");

        return this[(ulong)index];
    }
    set
    {
        if (index < 0)
            throw new ArgumentOutOfRangeException(nameof(index), index, "Index is negative.");

        this[(ulong)index] = value;
    }
}

---

Place opening curly braces on new line :)