BitArray Thread Safety

Question

I am looking for information regarding the thread-safety of concurrent writes to the System.Collections.BitArray class.

Specifically, consider the following contrived example:

BitArray bits = new BitArray(1000000);

Parallel.For(0, bits.Count, i =>
{
    bits[i] = i % 3 == 0;
});

Instinct tells me that concurrent unlocked access would produce an incorrect result if two threads attempt to write to the same underlying integral value of the bitarray, yet I can not find any evidence to support it, and I have not encountered any problems during runtime.

Is this a safe operation?

If not, why am I not seeing this code fail or produce incorrect output?

Update

After further testing, I think the following test proves that using a BitArray in this example is not thread safe.

Using a bool[] on the other hand, does seem to be safe.

private static bool CompareBitArrays(BitArray a, BitArray b)
{
    if (a.Count != b.Count) return false;
    for (int i = 0; i < a.Count; i++)
    {
        if (a[i] != b[i]) return false;
    }
    return true;
}

static void Main(string[] args)
{
    int numElements = 1000000;

    //create single-threaded bitarray with certifiably correct values.
    BitArray controlGroup = new BitArray(numElements);
    for (int i = 0; i < numElements; i++)
    {
        controlGroup[i] = i % 3 == 0;
    }

    //create a BitArray and bool array of equal size and fill them using Parallel.For.
    BitArray bits = new BitArray(numElements);
    bool[] bools = new bool[numElements];

    Parallel.For(0, numElements, i =>
    {
        bits[i] = bools[i] = i % 3 == 0;
    });

    //Create a BitArray from the bool array
    BitArray boolBits = new BitArray(bools);

    //Check if they contain correct values
    bool isBitArrayCorrect = CompareBitArrays(controlGroup, bits); //FALSE
    bool isBoolArrayCorrect = CompareBitArrays(controlGroup, boolBits); //TRUE
}

As I mentioned, I suspect the reason to be that 32 values in the BitArray share the same integral value of the array.

Is this logic correct?

For the sake of question, please assume no threads other than those shown in the code are accessing the collection.

Answer 1

Look into BitArray.Set method code:

public void Set(int index, bool value)
{
    if (index < 0 || index >= this.Length)
    {
        throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
    }
    if (value)
    {
        this.m_array[index / 32] |= 1 << index % 32;
    }
    else
    {
        this.m_array[index / 32] &= ~(1 << index % 32);
    }
    this._version++; // this is definitely thread-unsafe
}

As far as you accessing collection member by index, without enumerating it, the only thread-unsafe line of code I see there, is the last line this._version++;.

But it is there, so, you can consider this code as thread-unsafe.

Answer 2

I think this quote from MSDN under BitArray should tell you everything you want to know:

This implementation does not provide a synchronized (thread safe) wrapper for a BitArray.

Enumerating through a collection is intrinsically not a thread-safe procedure. Even when a collection is synchronized, other threads can still modify the collection, which causes the enumerator to throw an exception. To guarantee thread safety during enumeration, you can either lock the collection during the entire enumeration or catch the exceptions resulting from changes made by other threads.

I have bolded the important bit. Any enumeration through the collection is not thread safe, any altering of elements is therefore also not threadsafe, you should lock the entire collection or use one of the Thread safe collections. (Though I'm not sure a BitArray exists)

Answer 3

I wrote a ThreadSafeBitArray class that performs better than a regular lock over BitArray class. Maybe someone will find it useful.

public class ThreadSafeBitArray
{
    private static int[] _cachedShifts;

    static ThreadSafeBitArray()
    {
        _cachedShifts = new int[32];

        for (int index = 0; index < 32; index++)
        {
            _cachedShifts[index] = ((int)1 << index);
        }
    }

    private int _length;
    private int[] _arr;

    public ThreadSafeBitArray(int length)
    {
        _length = length;
        _arr = new int[ToUnderlineLength(length)];
    }

    private int ToUnderlineLength(int length)
    {
        int underlineLength = length / 32;

        if (length % 32 != 0)
        {
            underlineLength++;
        }

        return underlineLength;
    }

    public int Length
    {
        get { return _length; }
    }

    public bool this[int index]
    {
        get
        {
            return (Interlocked.CompareExchange(ref _arr[index >> 5], 0, 0) & (_cachedShifts[index & 31])) != 0;
        }
        set
        {
            int prevValue;

            if (value)
            {
                do
                {
                    prevValue = Interlocked.CompareExchange(ref _arr[index >> 5], 0, 0);
                }
                while (Interlocked.CompareExchange(ref _arr[index >> 5], prevValue | (_cachedShifts[index & 31]), prevValue) != prevValue);
            }
            else
            {
                do
                {
                    prevValue = Interlocked.CompareExchange(ref _arr[index >> 5], 0, 0);
                }
                while (Interlocked.CompareExchange(ref _arr[index >> 5], prevValue & ~(_cachedShifts[index & 31]), prevValue) != prevValue);
            }
        }
    }
}