Bitarray vs. bool[]

Question

What is the advantage of using a Bitarray when you can store your bool values in a bool[]?

System.Collections.BitArray biArray = new System.Collections.BitArray(8);
biArray[4] = true;

bool[] boArray = new bool[8];
boArray[4] = true;

The bool[] seems a little more handy to me, because there exist more (extension) methods to work with a array instead of a BitArray.

_{I expected to find an existing question here on Stack Overflow about this, but I didn't.}

Behl

Presumably the value lies in the bitwise methods (.Or, .Xor, etc.) contained in BitArray. – Enthrone

Check This question and answers. Could be useful. – Liquorice

Answer 1

BitArray is compact and allows you to perform bitwise operations. From the MSDN forum:

A BitArray uses one bit for each value, while a bool[] uses one byte for each value. You can pass to the BitArray constructor either an array of bools, an array of bytes or an array of integers. You can also pass an integer value specifying the desired length and (optionally) a boolean argument that specifies if the individual bits should be set or not.

Sgraffito

Answer 2

There's a memory/performance tradeoff. BitArray will store 8 entries per byte, but accessing a single entry requires a bunch of logical operations under the hood. A bool array will store each entry as one byte and thus taking up more memory, but requiring fewer CPU cycles to access.

Essentially, BitArray is a memory optimization over bool[], but there's no point in using it unless memory is sparse.

I created a simple performance test. Inverting 500 million elements using BitArray takes 6 seconds on my machine:

const int limit = 500000000;
var bitarray = new BitArray(limit);
for (var i = 0; i < limit; ++i)
{
    bitarray[i] = !bitarray[i];
}

The same test using a bool array takes about 1.5 seconds:

const int limit = 500000000;
var boolarray = new bool[limit];
for (var i = 0; i < limit; ++i)
{
    boolarray[i] = !boolarray[i];
}

Equality

Do you really think that doing a mask-and-compare is cheaper than doing another indirection? What about if the part of the array accessed with the bool[] isn't currently in CPU cache? – Treytri

Good point, Jon. Cache misses are expensive, meaning BitArray will perform a lot better when accessing elements close to each other. – Equality

BitVector32 even more so, but it's limited in length. – Treytri

Added some performance measures to the answer. Incomplete tests, sure, but the plain array still has the best performance is this case. – Equality

That's a completely different test with BitVector32, testing a completely incomparable functionality. The one with BitArray meanwhile wastes time on a pointless loop, when I fix that loop to the more realistic approach of just calling bitarray.Not() I get around 0.05s, compared to 0.8 seconds for the bool array (which doesn't have a .Not() method, so still needs the loop). – Treytri

I removed the BitVector32 test after reading up on what it actually does. The purpose of the test is to measure access time, not necessarily inverting. If random access is what we're measuring, the array is quicker than the BitArray. – Equality

Yes, but random-access is not always what one is doing, so it's not correct to say that the trade-off is just one of memory vs time. BitArray is very often faster, because it handles .Not, .And and so on much faster than an array of bools does. – Treytri

(Also, truly random access is different to sequential access). – Treytri