Is BitArray faster in C# for getting a bit value than a simple conjuction with bitwise shift?

Question

1). var bitValue = (byteValue & (1 << bitNumber)) != 0;

2). using System.Collections.BitArray with a Get(int index) method

• What is faster?
• In what situations for the .NET projects BitArray could be more useful than a simple conjunction with the bitwise shift?

Sebastian

Using System.Diagnostics.Stopwatch you could time if it's faster. It's best to try it in as close to the production environment as possible. – Rupertruperta

Answer 1

@Jonathon Reinhart,

your benchmark is unfortunately inconclusive. It does not take into account the effects of possible lazy-loading, caching and/or prefetching (by the CPU, the host OS and/or the .NET runtime).

Shuffle the order of the tests (or call the test methods multiple times) and you might notice different time measurments.

I did your original benchmark built with "Any CPU" platform target and .NET 4.0 client profile, running on my machine with a i7-3770 CPU and 64-bit Windows 7.

What i got was this:

Testing with 10000000 operations:
   A UInt32 bitfield took 484 ms.
   A BitArray (32) took 459 ms.
   A List<bool>(32) took 393 ms.

which is pretty much in line with your observations.

However, executing the BitArray test before the UInt32 test yielded this:

Testing with 10000000 operations:
   A BitArray (32) took 513 ms.
   A UInt32 bitfield took 456 ms.
   A List<bool>(32) took 417 ms.

By looking at the times for the UInt32 and BitArray tests you will notice that the measured time does not seem to be connected to the tests themselves, but rather to the order in which the tests are run.

To alleviate these side effects at least a little bit, i executed the test methods twice in each program run with the following results.

Test order UInt32, BitArray, BoolArray, UInt32, BitArray, BoolArray:

Testing with 10000000 operations:
   A UInt32 bitfield took 476 ms.
   A BitArray (32) took 448 ms.
   A List<bool>(32) took 367 ms.

   A UInt32 bitfield took 419 ms.  <<-- Watch this.
   A BitArray (32) took 444 ms.    <<-- Watch this.
   A List<bool>(32) took 388 ms.

Test order BitArray, UInt32, BoolArray, BitArray, UInt32, BoolArray:

Testing with 10000000 operations:
   A BitArray (32) took 514 ms.
   A UInt32 bitfield took 413 ms.
   A List<bool>(32) took 379 ms.

   A BitArray (32) took 444 ms.    <<-- Watch this.
   A UInt32 bitfield took 413 ms.  <<-- Watch this.
   A List<bool>(32) took 381 ms.

Looking at the second invocations of the test methods, it appears that at least on i7 CPUs with up-to-date .NET runtime, the UInt32 test is faster than the BitArray test, while the BoolArray test is still being the fastest.

(I apologize that i had to write my response to Jonathon's benchmark as an answer, but as a new SO user i am not allowed to comment...)

EDIT:

Instead of shuffling the order of test methods, you might try putting a Thread.Sleep(5000) or similar right before calling the first test...

Also the original test seems to put the UInt32 test at disadvantage, because it includes a boundary check "if (bitnum < 0 || bitnum > 31)", which is executed 30 million times. None of the other two tests include such a boundary check. However, this is actually not the whole truth, since both the BitArray and the bool array do boundary checks internally.

Although i didn't test, i expect that eliminating the boundary checks will make the UInt32 and BoolArray tests perform similarly, but that would not be a good proposition for a public API.

Magna

You should really run all your tests entirely separate and independent of each other and not just run one the next then the next. – Humerus

@Seph, you are correct. For a proper benchmark, this would be the way to go. However, the code i wrote was just meant to demonstrate the famous principle "You don't measure what you think you are measuring" ;) – Magna

Answer 2

BitArray is going to be able to handle an arbitrary number of boolean values, whereas a byte will hold only 8, int only 32, etc. This is going to be the biggest difference between the two.

Also, BitArray implements IEnumerable, where a integral type obviously does not. So it all depends on the requirements of your project; if you need an IEnumerable or array-like interface, then go with the BitArray.

I would actually use a bool[] over either solution, simply because it is more explicit in what kind of data you're keeping track of. T

BitArray or bitfield will use approximately 1/8th the space of a bool[] because they "pack" 8 boolean values into a single byte, whereas a bool by itself will take up the whole 8-bit byte. The space advantage of using a bitfield or BitArray isn't going to matter though until you being storing lots of bools. (The math is left up to the reader :-))

---

Benchmark

Results: For my primitive test environment, it appears that BitArray is a bit faster, but is on the same order of magnitude as doing it yourself with an integral type. Also tested was a bool[], which was unsurprisingly the fastest. Accessing single bytes in memory is going to be less complex than accessing individual bits in different bytes.

Testing with 10000000 operations:
   A UInt32 bitfield took 808 ms.
   A BitArray (32) took 574 ms.
   A List<bool>(32) took 436 ms.

Code:

class Program
{
    static void Main(string[] args)
    {
        Random r = new Random();
        r.Next(1000);

        const int N = 10000000;

        Console.WriteLine("Testing with {0} operations:", N);

        Console.WriteLine("   A UInt32 bitfield took {0} ms.", TestBitField(r, N));
        Console.WriteLine("   A BitArray (32) took {0} ms.", TestBitArray(r, N));
        Console.WriteLine("   A List<bool>(32) took {0} ms.", TestBoolArray(r, N));

        Console.Read();
    }


    static long TestBitField(Random r, int n)
    {
        UInt32 bitfield = 0;

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < n; i++) {

            SetBit(ref bitfield, r.Next(32), true);
            bool b = GetBit(bitfield, r.Next(32));
            SetBit(ref bitfield, r.Next(32), b);
        }
        sw.Stop();
        return sw.ElapsedMilliseconds;
    }

    static bool GetBit(UInt32 x, int bitnum) {
        if (bitnum < 0 || bitnum > 31)
            throw new ArgumentOutOfRangeException("Invalid bit number");

        return (x & (1 << bitnum)) != 0;
    }

    static void SetBit(ref UInt32 x, int bitnum, bool val)
    {
        if (bitnum < 0 || bitnum > 31)
            throw new ArgumentOutOfRangeException("Invalid bit number");

        if (val)
            x |= (UInt32)(1 << bitnum);
        else
            x &= ~(UInt32)(1 << bitnum);
    }



    static long TestBitArray(Random r, int n)
    {
        BitArray b = new BitArray(32, false);     // 40 bytes

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < n; i++) {

            b.Set(r.Next(32), true);
            bool v = b.Get(r.Next(32));
            b.Set(r.Next(32), v);
        }
        sw.Stop();
        return sw.ElapsedMilliseconds;
    }



    static long TestBoolArray(Random r, int n)
    {
        bool[] ba = new bool[32];

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < n; i++) {

            ba[r.Next(32)] = true;
            bool v = ba[r.Next(32)];
            ba[r.Next(32)] = v;
        }
        sw.Stop();
        return sw.ElapsedMilliseconds;
    }
}

Chitin

I've removed the second question from the original post, and reopened. Interestingly, I've got a bunch of SetBit and GetBit functions in a current project that look just like these. – Pharynx

Also, it looks like your code tests the speed of the random number generator as well as the bit shifting. It wouldn't surprise me if the random number generation takes significantly longer. – Pharynx

@RobertHarvey You're correct, but I wasn't too concerned about it. A) The random number generation should be pretty constant, and it's done the same between all methods, so it can be ignored. B) To do this without timing the random number generation would be much more complex, and also not test the functionality is well. If you've got a different idea, I'd appreciate hearing it for sure. – Chitin

I ran your code unchanged on my machine, and got results of 1525ms and 1185ms, respectively. Then I changed your random r to an int everywhere, set it to zero, and ran it again. The results were 581ms and 209ms, suggesting that the BitArray is more than twice as fast, and Random is consuming 2/3 of the processing time. I got substantially the same results setting r to 31 (I used zero and 31 for the two runs). – Pharynx

One thing I've learned over the years about benchmarking jit-ed languages is that no one seems to do it right. There's a lot of 'external forces' hidden by the compiler that will affect your results. I pretty much doubt these tests are valid or conclusive. – Shores

@Shores Have any better ideas? – Chitin

I just came across this and wanted to add that saying that the space difference between an array of booleans and a BitArray will not matter until storing lots of bools can be misleading. I mean it depends on what we mean by lots of. Because a list or an array may run out of allocable memory before the theoretical limit. And most importantly, for me, the largest advantage of a BitArray is not the smaller space it requires to store the values ; it is that thanks to its tiny spacing it can store much more values than a bool array could. – Tombolo

It would be interesting to run the test on larger arrays. As you start outgrowing memory caches and eventually start paging to disk, BitArray's performance will look better and better. – Philippa

Also, I'm not sure why you say it's more explicit to use bool[] than a BitArray to store boolean values. To me, both structures seem equally intended for storing boolean values. I suppose people may be less familiar with BitArrays. – Philippa

@NeilWhitaker How often do you really run your systems to the point of zero free RAM? Time is money, and memory is very cheap. – Chitin

Solution of this problem on HackerRank times out if I create the solution using BitArray. It works in acceptable time limits only when I use bool[]. I'm getting a strong evidence from my pratical experience that bitArray is slower. Only advantage in case of BitArray is space saving ~ 1 byte per bool flag. – Derosa

Answer 3

Using BitArray for data that fits in-cache when expressed as a List does not make performance sense.

The benchmarks demonstrated point out the obvious: A List of Bools will perform faster than a BitArray due to lack of computation requirements.

However, the big problem with these tests is that they were run on an array size of 32. That means the entire array fits into cache. The cost of processing a LARGE collection of booleans is going to manifest when you start doing a lot of memory fetches.

A BitArray of 5000 items is going to perform very different compared to a List of 5000 items. The List will require 8x more memory reads than the BitArray.

Depending on the rest of your logic (how much branching you're doing and other operations), the difference could be small or quite large. Memory pre-fetches allow the CPU to pull the next predicted chunk of memory into cache while still processing the first chunk. If you are doing a clean straight-shot iteration of the data structure, you might not see a significant performance difference. On the other-hand, if you are doing some branching or operations that make it tough for the CPU to predict memory fetches, you're much more likely to see a performance difference.

Furthermore, things get murkier if you start talking about MULTIPLE Data Structures. What if your code relies on references to 100 different BitArrays? Ok now, we're talking about a lot more data even if the BitArrays themselves are small, and you're going to be jumping around to access the different BitArrays, so the access pattern is going to impact things.

Impossible to know true behavior without benchmarking in your particular algorithm/scenario.

Fere

Answer 4

If someone still looking for some different solution that is fast enough: I would suggest using aggressive inlining [MethodImpl(256)] on GetBit and SetBit methods. Also with look-up table of OR and XOR values for bit positions. Removing bit position check since System.IndexOutOfRangeException shall be enough to indicate error in bit position, and we need not to consume CPU for additional checks. Also if performing this on large number of elements, and debugging, would strongly suggest the use of [DebuggerHidden] attribute. DebuggerHidden attribute helps debugger skip debugging of methods marked with this attribute and speed-up the debug process.

Use code from the Jonathon Reinhart answer and add this methods and tests for TestBitFieldOpt and TestBitFieldOpt2.

    static readonly uint[] BITMASK = new uint[]
    {
        0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020, 0x00000040, 0x00000080,
        0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000, 0x00008000,
        0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000,
        0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000
    };

    static readonly uint[] BITMASK_XOR = new uint[]
    {
        0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFB, 0xFFFFFFF7, 0xFFFFFFEF, 0xFFFFFFDF, 0xFFFFFFBF, 0xFFFFFF7F,
        0xFFFFFEFF, 0xFFFFFDFF, 0xFFFFFBFF, 0xFFFFF7FF, 0xFFFFEFFF, 0xFFFFDFFF, 0xFFFFBFFF, 0xFFFF7FFF,
        0xFFFEFFFF, 0xFFFDFFFF, 0xFFFBFFFF, 0xFFF7FFFF, 0xFFEFFFFF, 0xFFDFFFFF, 0xFFBFFFFF, 0xFF7FFFFF,
        0xFEFFFFFF, 0xFDFFFFFF, 0xFBFFFFFF, 0xF7FFFFFF, 0xEFFFFFFF, 0xDFFFFFFF, 0xBFFFFFFF, 0x7FFFFFFF
    };

    static long TestBitFieldOpt(Random r, int n)
    {
        bool value;
        UInt32 bitfield = 0;
        var sw = Stopwatch.StartNew();
        for (int i = 0; i < n; i++)
        {
            SetBitOpt(ref bitfield, r.Next(32), true);
            value = GetBitOpt(bitfield, r.Next(32));
            SetBitOpt(ref bitfield, r.Next(32), value);
        }
        sw.Stop();
        return sw.ElapsedMilliseconds;
    }

    static long TestBitFieldOpt2(Random r, int n)
    {
        bool value;
        UInt32 bitfield = 0;
        var sw = Stopwatch.StartNew();
        for (int i = 0; i < n; i++)
        {
            bitfield = SetBitOpt2(bitfield, r.Next(32), true);
            value = GetBitOpt(bitfield, r.Next(32));
            bitfield = SetBitOpt2(bitfield, r.Next(32), value);
        }
        sw.Stop();
        return sw.ElapsedMilliseconds;
    }

    [MethodImpl(256)]
    static bool GetBitOpt(UInt32 bitfield, int bitindex)
    {
        return (bitfield & BITMASK[bitindex]) != 0;
    }

    [MethodImpl(256)]
    static void SetBitOpt(ref UInt32 bitfield, int bitindex, bool value)
    {
        if (value)
            bitfield |= BITMASK[bitindex];
        else
            bitfield &= BITMASK_XOR[bitindex];
    }

    [MethodImpl(256)]
    static UInt32 SetBitOpt2(UInt32 bitfield, int bitindex, bool value)
    {
        if (value)
            return (bitfield | BITMASK[bitindex]);
        return (bitfield & BITMASK_XOR[bitindex]);
    }

I've increased the number of tests by power of 10 (to get more realistic results), and the results of optimized code are pretty close to the fastest method:

    Testing with 100000000 operations:
    A BitArray (32) took      : 4947 ms.
    A UInt32 bitfield took    : 4399 ms.
    A UInt32 bitfieldopt      : 3583 ms.
    A UInt32 bitfieldopt2     : 3583 ms.
    A List<bool>(32) took     : 3491 ms.

Generally less variables on local stack, less branches, and pre-calculated values win most of the time. So get the book and pencil and shorten the math to have those less ... true inlining inside functions helps a lot, but better using [MethodImpl(256)] attribute on methods for readability/up-keep of source code, as presented above.

Hope this helps someone find solution for his problem(s).

Heilner