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..

Comments (19)

  1. sbjorg says:

    Writing multithreaded programs is hard indeed. That’s why there are dedicated efforts to shift the paradigm away from threads while preserving the concurrency.

    That being said, calling Thread.Sleep while holding the lock to the shared resource is a bad idea. It prevents the other thread from enqueuing any items. Thus, this code will give atrocious performance. Aside from the fact that fibonacci can be computed in O(n) and this sample does it O(n!).

  2. Bill Wagner says:

    I’ll echo the same comment on the lock: You should lock a smaller block, which would not include the Sleep() call. But, it’s a little trickier than it looks, because the lock would be around the if statement, but not the else predicate.

    while (!ar.IsCompleted)

    {

    decimal val;

    bool foundValue = false;

    lock (fibList)

    {

    if (i < fibList.Count)

    {

    val = fibList[ i ];

    i++;

    foundValue = true;

    }

    }

    if ( foundValue )

    Console.WriteLine("{0,3} — {1}", i, val);

    else

    Thread.Sleep(0);

    }

    Caveat: I haven’t tested on a hyper-threaded machine, because I don’t have the latest hardware (yet).

  3. Craig Stuntz says:

    Misleading error message:

    if (n < 0) throw new ArgumentException("n must be > 0");

    The message should say, "n must be >= 0" as n == 0 is allowed by the method’s contract.

  4. rama says:

    It is HyperThreading that showed the error, not necessarily 64-bit right? My question is would a 32-bit HT can produce the same problem??? or is there something different with 64-bit?

  5. John says:

    I agree that threading can be hard. I wrote, what I thought, was a very simple little thread in an ASP.NET app so that I could run a report in the background and display its progress while it was running. In Beta 1 of VS2005, it ran without any problems at all. When I upgraded to Beta 2, it crashed badly. I re-looked at my code and almost slapped myself — it was pretty bad…

    I had a class which, when created, automatically started up and then started processing [expecting a member property to be set]. That member variable was set on the NEXT LINE after the class was created. Something either sped up or slowed down, because that it was managing to get to the code where it needed that variable in the second thread before it hit the next line in the ASP code. Boy did I feel dumb after rereading that code!!

  6. BradC says:

    I know that your use of the Fibonnacci sequence in your example is simply as a way to demonstrate multithreading, but I do have some comments about the method you are using to generate your Fibonacci sequence:

    Your "GenerateFibonacciNumber" is a pretty standard implementation using recursion. Fib(n) = Fib(n-1) + Fib(n-2). That works fine, even though you are really generating each number twice (because Fib(n-1) will call Fib(n-2), but you are already generating Fib(n-2) directly).

    Your "GenerateFibonacciSeries", however, calls GenerateFibonacciNumber, which it really shouldn’t. When you need Fib(10), for example, you have already generated Fib 1-9, but when you call your recursive function, it has to REgenerate 1-9 to find out 10! By the time you get to 100, you’re generating an incredible number of extra loops. Just use 8 and 9 directly to generate 10.

    Unless, of course, your point is that you WANT it to take a long time to demonstrate the need to spawn additional threads, which is actually the whole point of the exercise… ok, I’ll stop now.

  7. Isn’t this your favorite interview question?

  8. Hey — don’t give away my secrets ;-)… For what it is worth I don’t usally make folks do an async version… unless of course they are interviewing for a developer marketing job 😉

  9. Yeah — everybody knows that our dev teams hire the folks who can’t code well enough to be in our product management org. 🙂

  10. lexp says:

    BradC is right – you are just wasting processor time. I hope you guys do not code real soft this way!

  11. Yes, of course BradC is right, this is just a demo to show you how to handle long running methods… I couldn’t think of a better way to make it long running 😉

  12. Sean Chase says:

    I have a P4 32-bit HT processor and I can’t get the race condition to happen. Hmmmmm.

    * checks CMOS settings to make sure its enabled in a panic *

  13. Yea, I gotta admit that I have only repro’ed this on my Intel x64 box… But keep in mind it *could* happen anywhere… Let me know if others get it to repro

  14. If the purpose of this example is to show how to handle long running methods then you should do something about the Thread.Sleep call, as sbjorg mentioned. Sleep(0) will not block the producer, but it’s still not the most efficient solution. For example if you have more than one processor the main (consumer) thread will spin at 100% CPU waiting for the next item to arrive.

    I think the cleanest solution would be to use Monitor.Wait and Monitor.Pulse/PulseAll to synchronize producer and consumer sides. But then the question arises of how to break out of wait when the delegate completes without producing all the numbers (e.g. may be it throws an exception). I think you could just throw away the ar.IsCompleted check, and have the producer set a flag (aborted=true) and signal the monitor before returning from GenerateFibonacciSeries.

  15. sbjorg says:

    It doesn’t matter on what platform it repros. Threading behavior is sensitive to so many factors, ranging from processor architecture, cpu speed, to services installed. The fact of the matter is that the original code was not threadsafe. Unfortunately, the second version was just plain bad. ‘Bill Wagner’ provided a good alternative, but I would prefer using semaphores. Of course, some wise soul in the .Net team deemed it unnecessary to implement semaphores. Go figure…

  16. zzz says:

    On Channel 9 Poll http://channel9.msdn.com/ShowPost.aspx?PostID=45628 "Multithreaded programming is.." 1/3 thinks it’s not too hard.

    I just keep wondering how many of that 1/3 are not doing it right..

  17. TTT says:

    That poll is interesting. Of that 1/3 how many have just written

    Thread t = new Thread(new ThreadStart(func));

    t.Start();

    t.Join();

    I guess this allows people to now say they are savvy in MT programming. In my opinion threading hasn’t changed one bit from _begintheadex at all. It’s easier to create threads, easier to work with logical threads but sync is still the same. Of these 1/3 I would be curious how deep in threading they are talking?