Bitarray VS bool[]

Question

I expected to find a existing question here on SO about this but i didn't.

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

Presumably the value lies in the bitwise methods (`.Or`, `.Xor`, etc.) contained in `BitArray`. — Kirk Woll, Nov 03 '15 at 13:21
Check [This question and answers](http://stackoverflow.com/questions/16471759/is-bitarray-faster-in-c-sharp-for-getting-a-bit-value-than-a-simple-conjuction-w). Could be useful. — LightBulb, Nov 03 '15 at 13:28

Kvam · Answer 1 · 2015-11-03T15:15:09.030

19

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.

Edit: Created a simple performance test. Inversing 500M 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];
}

edited Nov 03 '15 at 15:15

answered Nov 03 '15 at 13:25

Kvam

2,148
1
20
32

2

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? – Jon Hanna Nov 03 '15 at 14:44
Good point, Jon. Cache misses are expensive, meaning BitArray will perform a lot better when accessing elements close to each other. – Kvam Nov 03 '15 at 14:58
`BitVector32` even more so, but it's limited in length. – Jon Hanna Nov 03 '15 at 15:04
Added some performance measures to the answer. Incomplete tests, sure, but the plain array still has the best performance is this case. – Kvam Nov 03 '15 at 15:09
3

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). – Jon Hanna Nov 03 '15 at 15:21
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. – Kvam Nov 03 '15 at 15:27
1

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. – Jon Hanna Nov 03 '15 at 15:35
1

(Also, truly random access is different to sequential access). – Jon Hanna Nov 03 '15 at 15:35

Rahul Tripathi · Accepted Answer · 2015-11-03T13:28:57.583

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.

Bitarray VS bool[]

2 Answers2