performance - 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?

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.