Parallel for Loop in C#

UPDATE - April 14^th, 2009

I updated the for loop code to include better math for smaller numbers of iterations, to make sure the work falls evenly on all threads. This is courtesy of Richard Massey (a coworker) who reviewed the code after I was finished.

"For large lists, it was working fine but in the case of small list where the processing of each item is very long, it had an uneven distribution of the tasks to each thread. So for example, if you had 9 long operations and 5 threads to do them, the distribution was (1, 1, 1, 1, 5). The new distribution would be (2, 2, 2, 2, 1)."

Since I talked about this the other day in the car with some coworkers, I thought I’d send out this spike… it’s only got the contiguous for loop in it, but it has its uses.

Some examples:

Searching REALLY large collections – by breaking the collection into chunks and then processing those chunks, you can loop through really large collections a lot faster, generally finding results sooner than you would with a linear for loop.

Large amounts of processing in for loops – if you have a for loop that contains a large amount of processing in the body, you can push some of that out onto different threads using this parallel loop.

Something to keep in mind is that since this uses separate threads to execute whatever body you’ve passed in, the body should be made thread safe before it you use it.

Also, you should consider that most linear searching or linear processing done in a regular for loop will outperform the method contained in my sample here, simply because the cost of threading is not exactly cheap. You’ll need to make the determination as to when you should use a parallel for like this one.

You’ll also notice the CountDown class that is included at the bottom of this post. This is like a ResetEvent that waits until a certain number of signals have been received before exiting out of the blocking Wait() call.

-- Results from the test app included at the bottom of this post:

Building initial array of 10000000 length...
Searching for ' 9000000.'...
Running parallel search...
Found This Is My Value: 9000000.
Search completed in: 00:00:00.9960000
Parallel for completed in : 00:00:01.2400000
Running linear search...
Found This Is My Value: 9000000.
Search completed in: 00:00:01.9480000
Linear for completed in : 00:00:02.1540000

Most of this stuff is either directly out of Joe Duffy’s book “Concurrent Programming on Windows”, which is totally awesome, or, like the CountDown class, something that I had to make in order to get the parallel for working.

public static void ContiguousPFor(int begin, int end, Action<int> body, int threads)
{
    if ((end - begin) < threads) // can't split this work up anymore
        threads = end;

    int chunkSize = (end - begin) / threads;
    int chunkRemainder = (end - begin) % threads;

    CountDown latch = new CountDown(threads);

    for (int i = 0; i < threads; i++)
    {
        ThreadPool.QueueUserWorkItem(delegate(object o)
        {
            try
            {
                int currentChunk = (int)o;

                int start = begin + currentChunk * chunkSize + Math.Min(currentChunk, chunkRemainder);
                int finish = start + chunkSize + (currentChunk < chunkRemainder ? 1 : 0);

                for (int j = start; j < finish; j++)
                {
                    body(j);
                }
            }
            finally
            {
                latch.Signal();
            }
        }, i);
    }

    latch.Wait();
}

public class CountDown
{
    int initialCount;
    int currentCount;

    AutoResetEvent mainAre = new AutoResetEvent(false);

    public int InitialCount
    {
        get { return initialCount; }
    }

    public CountDown(int count)
    {
        initialCount = count;
    }

    public void Wait()
    {
        while (mainAre.WaitOne())
        {
            if (currentCount >= initialCount)
                break;
        }
    }

    public void Signal()
    {
        Interlocked.Increment(ref currentCount);

        mainAre.Set();
    }

    public void Reset(bool triggerWait)
    {
        Reset(triggerWait, initialCount);
    }

    public void Reset(bool triggerWait, int newCount)
    {
        Interlocked.Exchange(ref currentCount, initialCount + 1); // just in case
        mainAre.Set(); // trigger wait

        Reset(newCount);
    }

    public void Reset(int newCount)
    {
        initialCount = newCount;
        Reset();
    }

    public void Reset()
    {
        Interlocked.Exchange(ref currentCount, 0);
    }        
}

Here's a sample console app that I used to test the for loop's speed. You can play with the numbers and see what kind of boost you get (sometimes a lot, sometimes none at all, depending on the numbers).

static void Main(string[] args)
{
    string[] values = new string[10000000];
    string findValue = " 9000000.";

    Console.WriteLine("Building initial array of {0} length...", values.Length);

    for (int j = 0; j < values.Length; j++)
    {
        values[j] = string.Format("This Is My Value: {0}.", j.ToString());
    }            

    start:

    Console.WriteLine("Searching for '{0}'...", findValue);

    Console.WriteLine("Running parallel search...");

    DateTime start = DateTime.Now;

    ParallelFor.ContiguousPFor(0, values.Length, (Action<int>)delegate(int i)
    {
        if (values[i].Contains(findValue))
        {
            Console.WriteLine("Found {0}", values[i]);
            Console.WriteLine("Search completed in: {0}", DateTime.Now - start);
        }
    }, 4);

    Console.WriteLine("Parallel for completed in : {0}", DateTime.Now - start);

    Console.WriteLine("Running linear search...");

    start = DateTime.Now;

    for (int i = 0; i < values.Length; i++)
    {
        if (values[i].Contains(findValue))
        {
            Console.WriteLine("Found {0}", values[i]);
            Console.WriteLine("Search completed in: {0}", DateTime.Now - start);
        }
    }

    Console.WriteLine("Linear for completed in : {0}", DateTime.Now - start);

    Console.WriteLine("Press any key to exit or press 'Z' to do it again...");

    if (Console.ReadKey().Key == ConsoleKey.Z)
    {
        Console.WriteLine("");
        goto start;
    }
}