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

by

@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.

More Related Contents:

  1. Make first letter of a string upper case (with maximum performance)
  2. Generating permutations of a set (most efficiently)
  3. Benchmarking small code samples in C#, can this implementation be improved?
  4. How to pass values across the pages in ASP.net without using Session
  5. Is String.Contains() faster than String.IndexOf()?
  6. For vs. Linq – Performance vs. Future
  7. What is quicker, switch on string or elseif on type?
  8. Most efficient way to insert Rows into MySQL Database
  9. What is the real overhead of try/catch in C#?
  10. Why does the c# compiler emit Activator.CreateInstance when calling new in with a generic type with a new() constraint?
  11. File.Copy vs. Manual FileStream.Write For Copying File
  12. Performance of nested yield in a tree
  13. C# / F# Performance comparison
  14. C# – Which is the best alternative to ‘switch on type’? [duplicate]
  15. How can I programmatically limit my program’s CPU usage to below 70%?
  16. String Interpolation vs String.Format
  17. How performant is StackFrame?
  18. True Unsafe Code Performance
  19. Why is Parallel.ForEach much faster then AsParallel().ForAll() even though MSDN suggests otherwise?
  20. Does String.GetHashCode consider the full string or only part of it?
  21. Why is this F# code so slow?
  22. async await performance?
  23. Fastest way to check if string contains only digits in C#
  24. How slow is Reflection
  25. Is it better to execute many sql commands with one connection, or reconnect every time?
  26. Is the conditional operator slow?
  27. Why is this faster on 64 bit than 32 bit?
  28. Fastest implementation of log2(int) and log2(float)
  29. Fastest way to remove first char in a String
  30. Left bit shifting 255 (as a byte)

Leave a Comment