Implementing the Async Pattern and the my threading bug...
Recently I spent some time working on some Design Guidelines around implementing the async pattern. Here is the code I came up with (I’d love your feedback on it BTW)…
public class Fibonacci
{
private delegate void GenerateFibonacciCallback(int count, ICollection<decimal> fibList);
private GenerateFibonacciCallback generateFibonacciCallback;
public Fibonacci()
{
generateFibonacciCallback = new GenerateFibonacciCallback(GenerateFibonacciSeries);
}
/// <summary>
/// Return the Nth fibonacci number
/// </summary>
public decimal GenerateFibonacciNumber(int n)
{
if (n < 0) throw new ArgumentException("n must be > 0");
if (n == 0 || n == 1) return 1;
return GenerateFibonacciNumber(n - 1) + GenerateFibonacciNumber(n - 2);
}
/// <summary>
/// Generate a series of the first count Fibonacci numbers
/// </summary>
/// <param name="count">number of fibonacci numbers to generate </param>
/// <param name="fibList">collection to add them into</param>
public void GenerateFibonacciSeries(int count, ICollection<decimal> fibList)
{
for (int i = 0; i < count; i++)
{
decimal d = GenerateFibonacciNumber(i);
lock (fibList)
{
fibList.Add(d);
}
}
}
/// <summary>
/// Starts the process of generating a series of the first count Fibonacci
/// numbers and returns
/// </summary>
public IAsyncResult BeginGenerateFibonacciSeries(int count, ICollection<decimal> fibList, AsyncCallback callback, object state)
{
return generateFibonacciCallback.BeginInvoke(count, fibList, callback, state);
}
/// <summary>
/// Blocks until the process of generating a series of the first count Fibonacci numbers
/// completes
/// </summary>
public void EndGenerateFibonacciSeries(IAsyncResult asyncResult)
{
generateFibonacciCallback.EndInvoke(asyncResult);
}
}
And some sample code to call it:
Fibonacci fib = new Fibonacci();
List<decimal> fibList = new List<decimal>();
IAsyncResult ar = fib.BeginGenerateFibonacciSeries(40, fibList, null, null);
int i = 0;
while (!ar.IsCompleted)
{
if (i < fibList.Count)
{
Console.WriteLine("{0,3} -- {1}", i, fibList[i]);
i++;
}
else
{
Thread.Sleep(0);
}
}
//need to call End to ensure that I get exceptions
fib.EndGenerateFibonacciSeries(ar);
Console.WriteLine("All Async opperations completed");
//print any left in the list to print
while (i < fibList.Count)
{
Console.WriteLine("{0,3} -- {1}", i, fibList[i]);
i++;
}
Console.WriteLine("Press return to continue");
Console.ReadLine();
Works like a charm on my laptop… but when I happened to run it from my 64bit machine I get output like this:
…
16 -- 1597
17 -- 2584
18 -- 4181
19 -- 6765
20 -- 0
21 -- 17711
22 -- 0
23 -- 46368
24 -- 75025
25 -- 0
26 -- 0
27 -- 0
…
What is going on? How can the exact same binary work on my laptop but give very bogus answers on my 64 bit machine?
The answer, as my blog title implies is that the code above has a latent threading bug. Although this bug could theoretically happen on my laptop, in practice it only shows up on my 64bit machine because it is truly hyperthreaded…There is a latent bug in the sample code calling the Fibonaccia class which only shows itself in a hyperthreaded environment. The problem is that I don’t protect all access to the shared memory (fibList)… So a race happens in List<T>.Add()… the counter is being incremented and the assignment are not done as an atomic operation.. thus we see the default value (0) printed out rather than the real value when a context switch happens between them. The fix is simple, just lock on the same monitor used in the GenerateFibonacciSeries()method.
while (!ar.IsCompleted)
{
lock (fibList)
{
while (i < fibList.Count)
{
Console.WriteLine("{0,3} -- {1}", i, fibList[i]);
i++;
}
}
}
With 64bit, hyperthreading and multicore becoming much more mainstream in the coming years, these types of issues will be more common making it more important than ever to careful review of all memory shared among threads is in order. A couple of take aways:
(1) Multithreading is hard – even when hidden in the async pattern. Purely coincidentally, I just reviewed an excellent article from one of the CLR architects on this very subject. It is still in the early stages now, but I will certainly link to it when it goes live. His basic gist is that you should keep your locking simple as you can… protect ALL access to any shared memory with as few locks as possible. That is why I lock over the if-branch as well as the call to the indexer even though it is *very* unlikely that a race with fibList.Count will cause any sort of problem.
(2) Even though it should be obvious that no amount of testing will find all these issues… this still a great excuse to ask you boss for a new machine so you can test on the latest hardware! ;-) I am running the latest RC of Windows XP Pro x64. It will be shipping very soon…
Based on some very good and clear feedback from BradC and lexp, I made an improvement to calling code above.
**
Based on a comment from a reader, i changed the delegate to use the Callback postfix..