Possible to use Interlocked.CompareExchange with a Bit?

Question

I have an array of ints that track the completion of 10,000 concurrent tasks, where the value is either 1 or 0. I think it would be more efficient if this array was an array of Bits and each concurrent thread used interlocked.CompareExchange (or similar) to alter a single bit.

How should I approach this if Interlocked doesn't have an overload for "bit"?

Answer 1

You can fake it with Interlocked.CompareExchange(ref int, int, int) in a loop, but I don't think it would be more efficient:

private static void SetBit(ref int valueToUpdate, int bitToSet)
{
   while (true)
   {
      int oldValue = valueToUpdate;
      int newValue = oldValue | bitToSet;
      int result = Interlocked.CompareExchange(ref valueToUpdate, newValue, oldValue);
      if (result == oldValue) break;
   }
}

Answer 2

I do not think you can do it with bits using Interlocked. You would have to switch to an array of ints, I believe, so that each bit is within its own int.

Interlocked.CompareExchange compares only for equality whereas you need to compare just a single bit of that int which you cannot do unless you use some other concurrency strategy to protect other changes to the int the bit resides within.

Answer 3

You need thread-safe constructs to track the completion of the concurrent tasks. Hence interlocked constructs are always faster than locks (because they don't need locks), you should use the static methods from the Interlocked-class with integers (0 as equivalent for false and 1 for true for example).

Jeffrey Richter does the same as he discribes in his book "CLR via C#" in chapter 28 "Primitive Thread Synchronization Constructs". He introduces own lock implementations based on Interlocked constructs in his Wintellect.PowerThreading library as well and gives an excellent explanation as well as time comparisons of his own implementations and those included in the .net framework.

Answer 4

First, no, all Interlocked functions work on memory addresses, and individual bits are not addressable.

So what to do instead?

I would investigate two options:

• don't bother with the array at all: have a simple counter, and InterlockedIncrement it each time a task completes. And to see if all tasks are done, just check if the value has reached 10,000 yet.
• alternatively, use the array, in order to minimize (false) data sharing. But then you shouldn't try to pack it densely. Go the opposite way. Ensure that each entry ends up on a separate CPU cache line, so that tasks running in parallel won't fight over the same cache lines. (And then, since tasks all write to separate locations, they won't even have to set their "done" flag with an expensive Interlocked operation.)

I don't know which is fastest. Benchmark it, if performance matters. :)