A Custom BitArray

Alex Harbuzenko · 2 May 2008 · C#, Interlocked, wow

Imagine a situation where we have a few hundred variables, each marked with some number. Also imagine that we need to know which of these objects have changed and which haven’t.
The simplest approach is to keep an array of boolean values and set true or false at the index that corresponds to the variable’s number. To make things more convenient, we can wrap our variables in properties and update the array’s state right inside the set accessor.

public int Variable10
{
    get { return m_variable10; }
    set
    {
        m_variable10 = value;
        m_changed[10] = true;
    }
}

Things get complicated once we need to keep a counter of changed fields. At first glance it looks trivial — just add an m_count++ to every set accessor..

But what happens if we need to change the variable’s value several times? We can’t just increment the counter blindly in that case, so we need a simple check:

public int Variable10
{
    get { return m_variable10; }
    set
    {
        m_variable10 = value;
        if (!m_changed[10])
        {
            m_changed[10] = true;
            m_count++;
        }
    }
}

Unlike the previous version, this code is no longer safe under multithreading: if m_changed[10] was still false at the moment of the check, and right after that another thread performs the same operation, the counter will get incremented twice.
There are several ways to solve this:

• use a lock before the check, or pair it with a second check (the double-check pattern)
• don’t increment the counter at assignment time — instead walk the array and count the true values whenever needed
• use the Interlocked methods

The locking approach is fairly simple and reliable (double-check pattern):

public int Variable10
{
    get { return m_variable10; }
    set
    {
        m_variable10 = value;
        if (!m_changed[10])
            lock (m_syncRoot)
                if (!m_changed[10])
                {
                    m_changed[10] = true;
                    m_count++;
                }
    }
}

Its only real drawback is that the operations can end up being fairly costly. The double check rules out unnecessary locking in most cases, so for ordinary applications this option is preferable.

Walking the array and counting true values is prone to synchronization problems: if one of the values changes while we’re iterating, we get an incorrect or stale result. Locking the array during the walk doesn’t help either, because we’d then need to add locking at the point where it’s modified as well:

public int Variable10
{
    get { return m_variable10; }
    set
    {
        m_variable10 = value;
        lock (m_syncRoot)
                m_changed[10] = true;
    }
}
...
int count = 0;
lock (m_syncRoot)
foreach(bool bvalue in m_changed)
    if (bvalue)
        count++;

That’s fairly expensive and not very elegant.

The Interlocked-based option turns out to be the fastest and most successful solution:

public int Variable10
{
    get { return m_variable10; }
    set
    {
        m_variable10 = value;
        if (Interlocked.CompareExchange(ref m_changed[10], true, false)
                                     == false)
            Interlocked.Increment(ref m_count);
    }
}

If we need maximum performance and aren’t fussing over every single byte of memory, this is perfectly fine. But what if paranoia makes us reach for a calculator to compute how much memory our array takes up? Each array element gets a whole byte allocated to it, which is 7 bits of overhead per entry — a true/false value can be stored in a single bit, yet it takes up 8! That’s 700 bits of overhead for every hundred elements — a whopping 88 bytes! 🙂
This is where the System.Collections.BitArray class comes to the rescue. Its usage syntax is the same as a regular bool[] array. You can swap the array for a BitArray without much trouble and use either of the first two approaches we covered above.
A pretty natural question comes up — what’s stopping the Interlocked approach from working together with BitArray? Let’s look more closely at this line

Interlocked.CompareExchange(ref m_changed[10], true, false)

The first parameter is a reference to the element the operation will act on. If we’re using a bool[] array, ref m_changed[10] correctly takes the address of the given element. With BitArray, the [] operator can only return or write a value — there’s no question of taking a reference to it at all.
In this situation, the correct thing to do would be to go back to the first approach for the counter — the double-check with locking — but this blog wasn’t built for people who like easy paths and trivial solutions 🙂
We’ll implement our own BitArray with the ability to set and read the bits we need using Interlocked operations.

I’ll skip describing the standard boilerplate parts here and lay out the most important part of the new class:

public bool this[int index]
{
    get { return ((m_array[index / 0x20] & (1 << (index % 0x20))) != 0); }
    set
    {
        if (value)
            m_array[index / 0x20] |= 1 << (index % 0x20);
        else
            m_array[index / 0x20] &= ~(1 << (index % 0x20));
    }
}

There’s not much to comment on here: the byte’s address in the array equals index / 32, and the bit’s address within the byte is index % 32. With this operator we get a full functional equivalent of BitArray. The next task is to write and read bits using Interlocked methods. .Net doesn’t allow this out of the box, but in the previous article http://blog.runserver.net/2008/04/interlockedorandexchangeadd-net.html we came up with the InterlockedOr and InterlockedAnd methods.
I won’t go into detail and will just give the code for our own BitArray right away, which tries to set or clear a bit and returns the bit’s old value:

public bool TrySet(int index, bool value)
{
    if (value)
    {
        int iValue = 1 << (index % 0x20);
        return
         (InterlockedOr(ref m_array[index / 0x20], iValue) & iValue) != 0;
    }
    else
    {
        int iValue = ~(1 << (index % 0x20));
        return
         (InterlockedAnd(ref m_array[index / 0x20], iValue) & iValue) != 0;
    }
}

With this, we can rewrite the third version of the counter:

public int Variable10
{
    get { return m_variable10; }
    set
    {
        m_variable10 = value;
        if (m_changed.TrySet(10, true) == false)
            Interlocked.Increment(ref m_count);
    }
}

So we’ve ended up with a way of tracking changes to indexed variables that’s optimal both in performance and memory usage.
You might ask why anyone would need this at all, so let me give two simple examples:
1. We have an object read from a DB with a large number of fields, and for each record we want the UPDATE statement to only touch the fields that actually changed, not all of them.
2. We need to send the changes to some large object over the network. In that case it’s convenient to send, in a single packet, the number of changed fields, the bitmask of changes (the guts of our BitArray), and the changes themselves.

The second example isn’t made up — it’s used in some modern MMOGs, including World Of Warcraft and the RunWoW emulator.