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(); }
}

This entry was posted on Monday, September 28th, 2009 at 12:18 am and is filed under C#, Software Development. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.