c# bitarray index of positive bits

Question

I have a c# BitArray that is fairly large (500,000) in length, and I am trying to get the index of all the positive bits set in the array. currently I am achieving this by:

public int[] GetIndexesForPositives()
{
    var idIndexes = new int[GetPositiveCount + 1];
    var idx = 0;
    for (var i = 0; i < Length; i++)
        {
            if (Get(i))
            {
                idIndexes[idx++] = i;
            }
        }
    return idIndexes;
}

I create an empty array of the size of known positive bits, then i lopp over the bitarray and add the index value to the return array.

This means I have to perform 500,000 loops over the array and its not exactly fast. (takes around 15ms).

I know the BitArray uses an integer array under the covers (i used it to write the GetPositiveCount function - via an alogrithm I got off stack), I wonder if there is an algorythm to do this aswell?

Answer 1

The answer from @Seph in https://stackoverflow.com/a/7415891/264022 is really nice, but it can be done a bit faster yet.

1. First count the number of bits
2. Unroll the inner loop (check 4 bits at a time) 2b. Make a construct, so that the JIT makes a jump table instead of a bunch IFs (This becomes the only unpredictable branch)
3. Use safe C# pointer magic to avoid out of bounds checks

Result is about 3-4x faster than the already fast version from @Seph.

  public static int[] GetIndexesForPositives(ulong[] _array)
  {
     var thisArray = _array;

     var c2 = 0ul;
     for (var i = 0; i < thisArray.Length; i++)
     {
        var v = thisArray[i];
        //from http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
        v = v - ((v >> 1) & (ulong)~(ulong)0/3);                           // temp
        v = (v & (ulong)~(ulong)0/15*3) + ((v >> 2) & (ulong)~(ulong)0/15*3);      // temp
        v = (v + (v >> 4)) & (ulong)~(ulong)0/255*15;                      // temp
        var c = (ulong) (v * ((ulong) ~(ulong) 0 / 255)) >> (sizeof(ulong) - 1) * 8; // count
        c2 += c;
     }
     if (c2 == 0) return Array.Empty<int>();

     var idIndexes = new int[c2];
     ref var idxref = ref idIndexes[0];
     for (var i = 0; i < thisArray.Length; i++)
     {
        var v = thisArray[i];

        for (var j = 0; j < 64; j += 4)
        {
           if (v == 0)
              break;
           var b = ((byte)v) & 0b1111;
           var actualIndex = i * 64 + j;
           switch (b)
           {
           case 0: break;
           case 0b001:
              idxref = (actualIndex);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;
           case 0b010:
              idxref = (actualIndex+1);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;
           case 0b011:
              idxref = (actualIndex);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+1);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;
           case 0b100:
              idxref = (actualIndex + 2);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;
           case 0b101:
              idxref = (actualIndex);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+2);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;
           case 0b110:
              idxref = (actualIndex+1);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+2);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;
           case 0b111:
              idxref = (actualIndex);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+1);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+2);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;
           case 0b1000: 
              idxref = (actualIndex+3);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;
           case 0b1001:
              idxref = (actualIndex);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+3);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;
           case 0b1010:
              idxref = (actualIndex+1);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+3);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;
           case 0b1011:
              idxref = (actualIndex);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+1);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+3);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;
           case 0b1100:
              idxref = (actualIndex + 2);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+3);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;
           case 0b1101:
              idxref = (actualIndex);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+2);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+3);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;
           case 0b1110:
              idxref = (actualIndex+1);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+2);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+3);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;
           case 0b1111:
              idxref = (actualIndex);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+1);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+2);
              idxref = ref Unsafe.Add(ref idxref, 1);
              idxref = (actualIndex+3);
              idxref = ref Unsafe.Add(ref idxref, 1);
              break;

           }

           v >>= 4;
        }
     }
     return idIndexes;
  }

Answer 2

If you are able to get a int array underlying the BitArray, this should provide much better performance:

Assuming you don't know the number of bits that are set:

public static int[] GetIndexesForPositives()
{
    var idIndexes = new List<int>();
    System.Reflection.FieldInfo field = data.GetType().GetField("m_array", System.Reflection.BindingFlags.NonPublic | System.Reflection.BindingFlags.Instance);
    int[] values = field.GetValue(data) as int[];

    for (var i = 0; i < values.Length; i++)
    {
        int _i = values[i];
        if (_i != 0)
        {
            for (var j = 0; j < 32; j++)
            {
                if ((_i & (1 << j)) != 0)
                {
                    idIndexes.Add(i * 32 + j);
                }
            }
        }
    }
    return idIndexes.ToArray();
}

If you do know the number of bits that are set you can do this instead:

public static int[] GetIndexesForPositives(int length)
{
    var idIndexes = new int[length];
    var idx = 0;
    System.Reflection.FieldInfo field = data.GetType().GetField("m_array", System.Reflection.BindingFlags.NonPublic | System.Reflection.BindingFlags.Instance);
    int[] values = field.GetValue(data) as int[];

    for (var i = 0; i < values.Length; i++)
    {
        int _i = values[i];
        if (_i != 0)
        {
            for (var j = 0; j < 32; j++)
            {
                if ((_i & (1 << j)) != 0)
                {
                    idIndexes[idx++] = i * 32 + j;
                }
            }
        }
}

My tests have these two working faster than your method, even the one that doesn't know how large the return array will be in the first place.

My results tested using a random BitArray of 50million records:

1) 25001063 records found in 50000000, took 1415.5752ms
2) 25001063 records found in 50000000, took 1099.67ms
3) 25001063 records found in 50000000, took 1045.6862ms
4) 25001063 records found in 50000000, took 745.7762ms"

1) is your code but using an arraylist instead of using some `GetPositiveCount` to get the output length.
2) is your code
3) is my (revised) first example
4) is my (revised) second example

edit: furthermore it is worth pointing out that this is a problem that could really benefit from being made multi-threaded. Break the ByteArray up into 4 parts and there you have 4 threads that could run checking the data at once.

Edit: I know this is already accepted but here's another bit you can do to improve performance if you know that most of the time your list will be very sparse:

for (var j = 0; j < 32; j++)
{
     if (_i == 0)
         break;
     if ((_i & (1)) != 0)
     {
         idIndexes.Add(i * 32 + j);
     }
     _i = _i >> 1;
 }

it is slightly slower when the list is >40% or more populated however if you know the list is always going to be 10% 1s and 90% 0s then this will run even faster for you.

Answer 3

You're fairly stuck with iterating 500,000 times. Intuitively: if every bit is set then you'll need to produce an array with 500,000 elements. You can reduce the number of outer iterations by a factor of 8 or 32 by accessing the underlying byte or int but then you'll still have to iterate the bits. Even a lookup table with 256 elements for every possible byte value won't help since you have to add the bit index.

However, if you have a lot of zero bits (sure hope you do) then an optimization is to simply adjust the loop counter by 8 or 32 if the underlying byte/int is 0. Since you know Get() will return 0. Also, use a List<> to avoid the expense of GetPostitiveCount.

Completely eliminating the need for this array and lazily retrieving the next bit set to 1 would be by far the best approach.

Answer 4

If you can swap out the BitArray from the BCL in favour of a "roll your own", you can do better than that. Here's a few things you can do:

1. Skip chunks of 64 that have no bits set
2. For chunks of 64 that do have bits, only enumerate the 1-bits instead of all bits using x & (x - 1) and your favourite fast 2log found here (using the naive 64-step method won't give any kind of speedup)
3. Keep an extra bitarray which stores, for each 64bit chunk, whether it is nonzero. Apply the technique from bullet 2 to that bitarray to skip whole ranges of zero's in one go.
4. Apply bullet 3 recursively for gigantic bitarrays

All four of these only help if the bitarray is expected to be sparse, and the worst case is still O(n) if it isn't sparse. If bullet 3 is applied until the top is a single ulong then it can in O(1) determine whether the entire bitarray is empty or not.

Answer 5

I would do something like this:

public int[] GetIndexesForPositives()
{
    var idIndexes = new LinkedList<int>();

    for (var i = 0; i < Length; i++)
        {
            if (Get(i))
            {
                idIndexes.Add(i);
            }
        }
    return idIndexes.ToArray();
}

If this is still not acceptable (because you walk the indizes again while doing ToArray) just use the same size for your result array and return the length of found indizes:

public int GetIndexesForPositives(out int[] indizes)
{
    indizes = new int[Length];
    var idI = 0;

    for (var i = 0; i < Length; i++)
        {
            if (Get(i))
            {
                indizes[idI++] = i;
            }
        }
    return idI;
}

Depending on if you really need all the indizes or only parts you might even consider something like this (but it will be less performant if you need every part - do some profiling yourself please):

public IEnumerable<int> GetIndexesForPositives()
{
    for (var i = 0; i < Length; i++)
        {
            if (Get(i))
            {
                yield return i;
            }
        }
}

this is assuming that your Get(i) is doing it's job and that your array is immutable.