Runtime: Optimize BitArray

[mariuszkochanowski]

BitArray class needs optimization. The following implementation is 5 times faster than the implementation of netcore 2.2:

BitArray took 5958 ms
CustomBitArray took 1243 ms

```c#
using System;
using System.Collections;
using System.Diagnostics;
using System.Runtime.CompilerServices;

namespace ConsoleAppBenchmarks
{
public class CustomBitArray
{
public int Length { get; }

    public bool this[int index]
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        get
        {
            if(index >= Length) throw new ArgumentOutOfRangeException(nameof(index));

            int idx = index >> BitsPerItemLog2;

            return (_array[idx] & (1 << (index - (idx << BitsPerItemLog2)))) != 0;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        set
        {
            if (index >= Length) throw new ArgumentOutOfRangeException(nameof(index));
            int idx = index >> BitsPerItemLog2;

            if (value)
            {
                _array[idx] |= (1 << (index - (idx << BitsPerItemLog2)));
            }
            else
            {
                _array[idx] &= (~(1 << (index - (idx << BitsPerItemLog2))));
            }
        }
    }


    public CustomBitArray(int length)
    {
        Length = length;
        _array = new int[(length >> BitsPerItemLog2) + 1];
    }

    private const int BitsPerItemLog2 = 5;

    private readonly int[] _array;
}

class Program
{
    static void Main(string[] args)
    {
        const int iterations = 1000;
        const int length = 64 * 10000;

        Console.WriteLine("BitArray took {0} ms", TestBitArray(iterations, length));
        Console.WriteLine("CustomBitArray took {0} ms", TestCustomBitArray(iterations, length));
        Console.Read();
    }

    static long  TestBitArray(int iterations, int length)
    {
        var bitArray = new BitArray(length);
       Stopwatch sw = new Stopwatch();
       sw.Start();

       for (int j = 0; j < iterations; j++)
       {
           for (int i = 0; i < length;)
           {
               bitArray[i] = true;
               if (bitArray[i])
               {
                   i++;
               }
           }
        }
       sw.Stop();

       return sw.ElapsedMilliseconds;
    }

    static long TestCustomBitArray(int iterations, int length)
    {
        var bitArray = new CustomBitArray(length);

        Stopwatch sw = new Stopwatch();
        sw.Start();

        for (int j = 0; j < iterations; j++)
        {
            for (int i = 0; i < length;)
            {
                bitArray[i] = true;
                if (bitArray[i])
                {
                    i++;
                }
            }
        }
        sw.Stop();

        return sw.ElapsedMilliseconds;
    }



}

}
```

[danmosemsft]

@mariuszkochanowski we are always interested in performance optimizations, if we can preserve the API contract, and the complexity is acceptable. Are you interested in offering changes?

You might try master (3.0) first. there were some recent improvements: https://github.com/dotnet/corefx/pulls?q=is%3Apr+bitarray+is%3Aclosed

[vectorix]

Other ideas:
1) Add throw helper (compare disasm)
2) Eliminate array bounds checks (Unsafe.Add)
3) SetAll can also be optimized
4) Samwhoo's answer here may be more efficient and is branchless (needs benchmarking):
https://stackoverflow.com/questions/2633400/c-c-efficient-bit-array

void bitv_set(struct bitv *b, int bit) {
check_bounds(b, bit);
b->words[bit >> 5] |= 1 << (bit % BITS_PER_WORD);
}

void bitv_clear(struct bitv *b, int bit) {
check_bounds(b, bit);
b->words[bit >> 5] &= ~(1 << (bit % BITS_PER_WORD));
}

5) Get rid of BitsPerItemLog2 as it may incur a cache miss and put the constant in the code directly so that instruction cache prefetch would pick it up

[am11]

I think this was fixed by @omariom in dotnet/corefx#35364. See the Assembly listing for method BitArray:Set(int,bool):this under (collapsed) widgets Code generated BEFORE vs. Code generated AFTER. Get and Set inlined into the callers. Set was called with a constant value (true). in the original post.

This is not yet picked up by preview 3, but using latest master, I am getting:

BitArray took 3190 ms
CustomBitArray took 3401 ms

with:

#!/usr/bin/env sh

mkdir ~/dotnet3
curl -L https://dotnetcli.azureedge.net/dotnet/Sdk/master/dotnet-sdk-latest-linux-x64.tar.gz \
   | tar -xzvf - -C ~/dotnet3

~/dotnet3/dotnet new console -n test-34606 ; cd $_

curl -L https://api.github.com/repos/dotnet/corefx/issues/34606 \
   | jq -r '.body' | sed -n '/```c#/,$p' | head -n -1 | tail -n +2 > Program.cs

~/dotnet3/dotnet run -c Release

[danmosemsft]

curl -L https://api.github.com/repos/dotnet/corefx/issues/34606 \
| jq -r '.body' | sed -n '/```c#/,$p' | head -n -1 | tail -n +2 > Program.cs

Nice trick!