I recently attended a job interview where I was asked the following question. For some time, it did not make sense to me, and so I attempted to hedge my bets by talking about a variety of issues that could result from the code in question. My answer was wrong.

The question was, what's wrong with this?

var tasks = new List<Task>();
var acc = 0;

for (var i = 0; i <= 100; i++)
{
    tasks.Add(Task.Run(() => acc++));
}

Task.WaitAll(tasks.ToArray());
Console.WriteLine(acc);

Note that this was drawn on a whiteboard without precise syntax; I have taken liberties in making this compile.

This will generally print the correct answer minus one, but it can be off by more than that. Changing the type of acc from int to long will substantially increase the error. The worst result I got was forty—which is sixty less than it should have been. Generally, long is about twice as bad as int.

Today, class, we're going to learn why that happens!

My thought process

One of the facts of which I am vaguely aware is that assigning a 32-bit value is an atomic operation. Whether or not that is true is architecture-dependent, and I can't quote chapter and verse, but here's what that means:

When reading or writing a 32-bit value like System.Int32, it isn't possible for some other thread to step in and write the same value at the same time. Like, you aren't going to be writing bit number seventeen while someone else is changing bit number three. That may not make sense, but consider that statement in contrast to the alternative. Let's talk about 64-bit values.

Reading (and writing, clearly) a 64-bit integer is not atomic. You may read the 32 least significant bits of 1_000_000_000, followed by the 32 most significant bits of 6, at which point the number you end up with is... Well, I'm guessing it's zero. Now you can see what I mean, right?

Anyway, what all this means is that I was half right: a single operation on a 32-bit value is atomic. There's a catch here, however.

What did I miss?

Incrementing a 32-bit value is not a single operation. There are two steps:

  1. Read the value.
  2. Write the value + 1.

Reading and writing are atomic, sure, but doing them both is not. (Note: most architectures today allow for an atomic form of this operation, but the compiler needs to actually ask for it.)

What this means is that Thread A may read a 6 and write a 7 at the same time as Thread B: they both read 6, and they both write 7. This does no one any good, because we've effectively lost one increment. This is exacerbated when dealing with 64-bit integers (remember the error got much bigger with them, right?), because the number of read/write operations is doubled.

It may be instructive to note that, at least in the case of 32-bit values, it is not possible for the actual result to be larger than the expected result. This is because of the mechanism by which the problem manifests.

How did I forget that?!

Basically, I was thinking about the standard implementation for IDisposable and how we are able to trust the assignment of a boolean value even where multiple threads may be accessing a given instance of a class: setting the value of a boolean is atomic.

...Note that I said "setting," not "reading and then setting." Oops.

Mitigation

This is easy to fix. Step one is basically, "don't increment a counter from multiple threads like this." Step two is the "if you must," caveat; it's a static class called System.Threading.Interlocked, and it provides interlocked (atomic) math operations on integral types. It also provides an atomic read for 64-bit ints.

var tasks = new List<Task>();
var acc = 0;

for (var i = 0; i < 100; i++)
{
    tasks.Add(Task.Run(() => Interlocked.Increment(ref acc));
}

Task.WaitAll(tasks.ToArray());
Console.WriteLine(acc);

So, the short version is that, no, you won't get the right answer, and that it's because reading the value and adding 1 to it are two different operations.

In other words, I owe Big E a beer.