So I was reading an article by John Siracusa on arstechnica.com about  Snow Leopard recently and he had a great segment about Apple’s new Grand Central Dispatch technology. The idea of GCD is to allow developer’s to easily multithread code without having to do all the work that I had to go through. Before I get into that though let’s cover the basis of what GCD is. First of all GCD is a low level means of handling threads automatically. When developing for a multiprocesser system developers don’t have much knowledge of what the current system state is. Sure I have four cores, but how many are available? Once you let GCD know you want something threaded it can farm out the work for you. No checking for number of processor cores or if hyperthreading is available. Sweet.

Grand Central Dispatch also allows you to multithread in just a few lines of code. John does a great job of explaining it so hit the link above and read up if you want more in depth information on the technology. The short version is that blocks + GCD = multithreading bliss.

So all of this got me thinking about my previous article on multithreading a workload and how I could improve it. One thing that would make sense would be to use a stack instead of splitting my list up into equal parts. A stack is like a pile of paper. You can pull things off the top of the stack and expose the page underneath. So if I passed the same stack to each thread then the threads would peel off the work bit by bit until the stack was gone.

• Once the stack is empty then the threads will terminate themselves.
• I could add work to the stack as it is being processed (of course being careful that the threads don’t terminate before I am done collecting work)
• I don’t have to worry about one subset of work finishing faster than another.

So let’s run a little pseudo code for this framework:

private void Multithread()
{
  Stack<int> stack = new Stack<int>(100); //stack of 100 something
  for (int i = 0; i < 100; i++) { stack.Push(i); } //fill the stack
  Thread[] threads = new Thread[System.Environment.ProcessorCount];

  //Create the threads and pass the same stack to each one
  for (int i = 0; i < threads.Length; i++)
  {
       threads[i] = new Thread(delegate() {
                      DoSomething(stack);
                    });
       threads[i].Start();
  }
<pre style="font: normal normal normal 12px/18px Consolas, Monaco, 'Courier New', Courier, monospace;">   //wait for execution to finish
  foreach (Thread thread in threads) { thread.Join(); }</pre>
}

And our worker function which will terminate once the stack has emptied

private void DoSomething(Stack<int> stack)
{
 while (stack.Count > 0)
 {
    int j = stack.Pop();
    Debug.Print(j.ToString());
 }
 return;
}

Recently I was faced with a prescreening programming question that involved a straightforward problem with one caveat that made it significantly more difficult. I had to compute some 800 trillion+ solutions in as close to 20ms as possible. It only took me a couple days to write an algorithm that could theoretically solve the answer… but it would have taken weeks to run. Eventually I figured out the shortcut to get my run time to less than a second, but carving away each tenth of a second thereafter took some creativity. One obvious way of making up some time would be to make use of the near ubiquity of multicore processors these days. Fortunately the workload was simple enough to split up. I had a large list of objects and I had to do “something” to each element. By splitting the list and farming out the workload to the number of processors in the system I carved off a nice 40% time savings on a segment of my project. Again we will be working in C#.

Jump to final code

Generally the code flows like this:

1. Add references
2. Find the number of processors on the current system
3. Split your workload into pieces
4. Create a thread for each piece
5. Wait for the threads to complete before continuing main program execution.

First off add a reference to the System.Threading namespace

using System.Threading;

Next find the number of processors

int numProcs = System.Environment.ProcessorCount;

For my workload I am splitting a list into equal parts. I have to ensure that when I split the list I don’t repeat any of the elements, nor do I leave any elements behind if the list isn’t evenly divisible by the number of processors in the system. It would also be more efficient to check the length of the list and see if it is worthwhile to multithread it. If you only have one list item then multiple threads aren’t going to do you much good.

List<N> myList = new List<N>();
int iRange = list.Count / numProcs;       //# of elements in the list to get
int iStart, iEnd;                        //portion of list that we will get

//for each processor get a piece of the workload
for (int i = 0; i < iProcs; i++) {
     //set start and end values to get
     iStart = iRange * i;
     if (i == iProcs - 1)  //for last processor use the rest of the list
          iEnd = buildRows.Count - iStart;
     else
          iEnd = iRange;

     //Get the subset of list items
     List<N> listSubset = myList.GetRange(iStart, iEnd);
}

Now for the multithreaded part. You create a new thread by creating a new Thread object and specifying a ThreadStart. A ThreadStart represents a method in your program and acts as a delegate. A delegate is an object that refers to a method and can call a method. In this example I want to execute a method on each item in my list. So I create a delegate that points to this method. There are multiple ways to set this up, but the most straightforward way I found is in this example code.

Thread myThread = new Thread(
     delegate() {
          foreach (N item in listSubset) { item.DoSomething();  }
     }
);

You call thread.Start() to begin executing the delegate. However, your main application thread will continue running simultaneously. If you want to wait for all your worker threads to finish before continuing with the main thread you must call thread.Join();. This tells the current thread to wait for the specified thread to finish. Let’s tie everything together now.

private void MultiThreadWorkLoad(List<N> myList) {
    int numProcs = System.Environment.ProcessorCount; //number of processors
    int iRange = buildRows.Count / iProcs;   //# of elements in the list to get
    int iStart, iEnd;       //portion of list that we will get
    Thread[] threads = new Thread[iProcs];      //array of threads

     //for each processor get a piece of the workload
     for (int i = 0; i < numProcs; i++) {
          //range of values to get
          iStart = iRange * i;
          if (i == numProcs - 1)  //for last processor use the rest of the list
               iEnd = buildRows.Count - iStart;
          else
               iEnd = iRange;

          List<N> listSubset = buildRows.GetRange(iStart, iEnd);
          Thread myThread = new Thread(
              delegate() {
                      foreach (N item in listSubset) { item.DoSomething();  }
              }
          );
          myThread.Start();
          threads[i] = myThread;
    }

    //all threads should complete before we continue with main program execution
    foreach (Thread thread in threads) { thread.Join(); }
}