BitArray vs bool[]

[vc-74]

I'm currently working on a case where I have to find the best collection to hold a collection of bits indexed by an integer. This collection will be used frequently and contain 100 to 10K bits most of the time. Read/write access should be as fast as possible.

I've run the benchmark below which creates different bit collections and counts the number of bits which value is true. My conclusions are:

• Using bool[] is more than twice faster than using BitArray
• BitArray allocates ~8 times less than bool[] as expected
• BitArray Gen0 GC is ~8 times less than bool[] as expected
• The BitArray performance improvements detailed in Performance Improvements in .NET 5 only apply when the same bool[] is used to create a BitArray which has little value in my case since bits are always different (my understanding is that this is only helpful in a singleton BitArray scenario?)
• Linq is not a good option in such scenarios

My question is, considering this benchmark, is higher pressure on GC with better performance a better option or is it going to introduce GC performance issues down the line?

Side question: is there a reason why BitArray does not implement IEnumerable<bool>?

[MemoryDiagnoser]
[InProcess]
public class BitCollectionSetBitCountTests
{
    /// <summary>
    /// Number of elements in a bit collection.
    /// </summary>
    [Params(100, 1_000, 10_000)]
    public int Count;

    /// <summary>
    /// Create and initialize an array of <see cref="bool"/>
    /// and count the number of true elements.
    /// </summary>
    [Benchmark(Baseline = true)]
    public void BooleanArray()
    {
        bool[] bits = new bool[Count];

        for (int i = 0; i < bits.Length; i++)
        {
            bits[i] = IsEven(i);
        }

        int setBitCount = 0;

        for (int i = 0; i < bits.Length; i++)
        {
            if (bits[i])
            {
                setBitCount++;
            }
        }
    }

    private static bool IsEven(int x) => ((x % 2) == 0);

    /// <summary>
    /// Create and initialize a <see cref="BitArray"/> using a loop
    /// and count the number of true elements using a loop.
    /// </summary>
    [Benchmark]
    public void BitArrayLoopInitializationLoopCount()
    {
        BitArray bitArray = new(Count);

        for (int i = 0; i < bitArray.Count; i++)
        {
            bitArray[i] = IsEven(i);
        }

        int setBitCount = 0;

        for (int i = 0; i < bitArray.Count; i++)
        {
            if (bitArray[i])
            {
                setBitCount++;
            }
        }
    }

    /// <summary>
    /// Create and initialize a <see cref="BitArray"/> from a <see cref="bool"/> array
    /// and count the number of true elements using a loop.
    /// </summary>
    [Benchmark]
    public void BitArrayArrayInitializationLoopCount()
    {
        bool[] bits = Enumerable.Range(0, Count).Select(IsEven).ToArray();
        BitArray bitArray = new(bits);

        int setBitCount = 0;

        for (int i = 0; i < bitArray.Count; i++)
        {
            if (bitArray[i])
            {
                setBitCount++;
            }
        }
    }

    /// <summary>
    /// Create and initialize a <see cref="BitArray"/> from a <see cref="bool"/> array
    /// and count the number of true elements using Linq.
    /// </summary>
    [Benchmark]
    public void BitArrayArrayInitializationLinqCount()
    {
        bool[] bits = Enumerable.Range(0, Count).Select(IsEven).ToArray();
        BitArray bitArray = new(bits);

        int setBitCount = Enumerable.Range(0, Count).Where(i => bitArray[i]).Count();
    }
}

[Joe4evr]

• Using bool[] is more than twice faster than using BitArray

I wonder if this could be due to bounds-check removal on arrays in general. Could you set up a benchmark that accesses elements at a number of random indices, instead of a linear walk?

[vc-74]

@Joe4evr Interesting suggestion, I guess replacing:

for (int i = 0; i < bits.Length; i++)

with

foreach (int i in Enumerable.Range(0, bits.Length))

should prevent this optimization?

[Joe4evr]

Possibly? I was more thinking to just draw 10 or 20 (or however many you'd like) numbers out of a hat and write those accesses out in the benchmarks. No loop at all.

_ = bits[28];
_ = bits[42];
// etc

[vc-74]

Your assumption was correct.
I've run the tests below and BitArray is now faster when a bool[] is passed to its constructor (BitArrayArrayInitializationLoopCount). It seems to defeat the purpose though, since creating the bool[] allocates the space BitArray tries to save... Maybe a constructor like BitArray(int length, IEnumerable<bool> values) would be the best of both worlds.

In any case, the performance trade-off of BitArrayLoopInitializationLoopCount is now much more acceptable especially in the 10K case.

[MemoryDiagnoser]
[InProcess]
public class BitCollectionSetBitCountTests
{
    /// <summary>
    /// Number of elements in a bit collection.
    /// </summary>
    [Params(100, 1_000, 10_000)]
    public int Count;

    [GlobalSetup]
    public void GlobalSetup()
    {
        _indices = Enumerable.Range(0, Count);
    }
    private IEnumerable<int> _indices = null!;

    /// <summary>
    /// Create and initialize an array of <see cref="bool"/>
    /// and count the number of true elements.
    /// </summary>
    [Benchmark(Baseline = true)]
    public void BooleanArray()
    {
        bool[] bits = new bool[Count];

        foreach (int i in _indices)
        {
            bits[i] = IsEven(i);
        }

        int setBitCount = 0;

        foreach (int i in _indices)
        {
            if (bits[i])
            {
                setBitCount++;
            }
        }
    }

    private static bool IsEven(int x) => ((x % 2) == 0);

    /// <summary>
    /// Create and initialize a <see cref="BitArray"/> using a loop
    /// and count the number of true elements using a loop.
    /// </summary>
    [Benchmark]
    public void BitArrayLoopInitializationLoopCount()
    {
        BitArray bitArray = new(Count);

        foreach (int i in _indices)
        {
            bitArray[i] = IsEven(i);
        }

        int setBitCount = 0;

        foreach (int i in _indices)
        {
            if (bitArray[i])
            {
                setBitCount++;
            }
        }
    }

    /// <summary>
    /// Create and initialize a <see cref="BitArray"/> from a <see cref="bool"/> array
    /// and count the number of true elements using a loop.
    /// </summary>
    [Benchmark]
    public void BitArrayArrayInitializationLoopCount()
    {
        bool[] bits = _indices.Select(IsEven).ToArray();
        BitArray bitArray = new(bits);

        int setBitCount = 0;

        foreach (int i in _indices)
        {
            if (bitArray[i])
            {
                setBitCount++;
            }
        }
    }

    /// <summary>
    /// Create and initialize a <see cref="BitArray"/> from a <see cref="bool"/> array
    /// and count the number of true elements using Linq.
    /// </summary>
    [Benchmark]
    public void BitArrayArrayInitializationLinqCount()
    {
        bool[] bits = _indices.Select(IsEven).ToArray();
        BitArray bitArray = new(bits);

        int setBitCount = _indices.Where(i => bitArray[i]).Count();
    }
}

[Clockwork-Muse]

Why not just one of the other constructors, and not allocate the boolean array at all? Eg, there's the BitArray(int length) constructor.

[vc-74]

This is what is done in the BitArrayLoopInitializationLoopCount test which is ~10% slower than the bool[] implementation not using BitArray whereas the test passing a bool[] in parameter to BitArray's constructor (BitArrayArrayInitializationLoopCount) is ~10% faster.

[tannergooding]

Since the Length is growable, it restricts our ability to do certain optimizations and that means we have enforced bounds checks that can't readily be elided.

We could potentially have some CollectionsMarshal API that lets you get the raw Span<bool>, but I don't think there is much else that can be done with what we have today.

Conceptually some specialized Array which is int capacity; int count; T Item0; ... would work, but that would require quite a bit of JIT/VM work to make possible, as it would effectively be a new array type. It would however make it safe to do one bounds check for List, BitArray, and other similar types.

[vc-74]

Thanks for the reply @tannergooding. In my case, I don't mutate BitArray instances once constructed and initialized. An immutable BitArray would be nice since performance is IMO often important in scenarios where bits are involved.

[JanTamis]

you could copy the code from https://source.dot.net/#System.Collections/System/Collections/BitArray.cs,19ad3f494f0dc7f6 and mutate it to you needs.

[vc-74]

@JanTamis Thanks for the reply. I could but I don't think it's worth the effort so I'll stick to it. BitArray may also be further optimized in the future.