Using .Net 4 Parallel programming to speed up ForEach loops.

Background

Multi core processors started to become common place in consumer pc’s in 2006 with the introduction of Core Duo processors. These days its commonplace for even budget pc systems to have 4 or more cores with an i5 processor or up to 8 with an i7 processor.   In a server environment such as those hosting websites it’s possible to increase this even more with companies such as Dell offering 64 core servers.

A computer with multiple cores is capable of running several tasks in parallel, as opposed to waiting for a task to complete before running the next task. The problem is that traditional programming methods in languages such as c# don’t take advantage of these multiple cores and tend to run tasks in turn on one core while leaving the other cores idle.

This post will show the advantages, and potential disadvantages of one simple method to speed up a common programming loop.

ForEach loop

A foreach loop in programming is a way of traversing over multiple elements in a collection. An example would be a list of passengers in a software program used by a tour operator. If you wanted to send an email to every passenger a standard foreach loop would go through this list one passenger at a time and send the appropriate email.

 Sample ForEach loop
foreach (var passenger in listOfPassengers)
{
    SendEmail(passenger);
}

This executes this code on passenger at a time, as illustrated in the diagram below.

Foreach

If the software has access to multiple CPU cores why not divide this list between each core and let them all take a share of the work load?

Probably because it sounds terribly complicated, it’s not.

Parallel ForEach loop

The Parallel library was introduced in .Net version 4, and the simplest way to use this to find speed increases in software is the ForEach loop, and it’s easy to retrofit this into existing code.

The previous loop rewritten for Parallel programming.
      Parallel.ForEach(listOfPassengers, passenger
          => {
                 SendEmail(passenger);
             });

The Parallel.Foreach loop differs in that it uses delegates to create a method that is executed, but the code inside the curly brackets remains the same, which makes it very simple to implement in code that has already been written.

The difference in code execution on a multi core system is illustrated in the diagram below.

ParallelForEach

The Parallel.ForEach loop 1st allocates a portion of the list of passengers to each available core and then they loop through the list and do whatever actions our software is programmed to do. After they are all finished we can carry on with our program execution as usual.

An example

To prove this theory I developed a small console application that would calculate pi to an increasing number of places. The program would start by calculate it to one place and keep going till it had calculated to a 1000 places.

The 1st part of the program would do this with a normal ForEach loop. So one CPU core would take on all this work and do it sequentially.

const int maxIterations = 1000;
foreach (var iteration in Enumerable.Range(1, maxIterations))
{
       Console.WriteLine("Non-parallel calculating pi to {0} places", iteration);
       pi.CalculatePi(iteration);
}

The 2nd part of the program would do this with a Parallel.ForEach loop. So on my computer 4 CPU cores would share the work load between them.

Parallel.ForEach(Enumerable.Range(1, maxIterations) ,iteration =>
{
        Console.WriteLine("Parallel calculating pi to {0} places", iteration);
        pi.CalculatePi(iteration);
});

A timer would be set to run for the duration of the two loops above, and the results displayed.

The results

The standard c# ForEach loop took 18.3 seconds, the Parallel.ForEach loop took only 5.1 seconds.

3 and half times faster!

Do not use if order of execution matters!

There are potential drawbacks, and care and consideration does need to be taken when using parallel programming. For example if something later in the loop needs to know the result for something that has happened earlier in the loop, it may not have already happened yet due to the operations occurring concurrently rather than sequentially. They’re not necessarily happening in the order we expect.

Can Parallel.ForEach be slower?

Surprisingly in some circumstances, yes.

The 1st thing a Parallel.ForEach loop needs to do is share the work between the available cores, and this in itself takes processing power. If the time it takes to divide this work is longer than the potential benefits then this method can be slower than just looping through our foreach in the traditional way.

A real world example of this would be a teacher marking exam papers……

If a teacher has 120 exam papers to mark, and each one takes 10 minutes, then it’s going to take them 20 hours to mark these papers by themselves.

If they instead spent an hour finding 3 other teachers to help mark the exam papers then it would take them 20 hours divided by 4 (3 teachers plus them self) plus the hour spent finding these extra teachers. So it would take them just 6 hours. Almost 3 and a half times faster, just like the previous programming example.

If the next week the same teacher has only 7 exam papers to mark, and again each one takes 10 minutes, then it’s going to take them 1 hour and 10 minutes to mark these papers by themselves.

If they spent one hour finding 3 other teachers to help mark the exam papers then it would take 1 hour and 10 minutes divided by 4 (3 teachers plus them self) plus the hour spent finding these extra teachers.

So it would now take them 1 hour and 17.5 minutes, an increase of 7 and a half minutes over doing it by themselves.

In conclusion, the increase in speed has to outweigh the time spent allocating the work to other resources. But used wisely, parallel programming can have massive speed benefits with minimal extra time spent coding.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s