.NET 4.0+Terminating Parallel Loops
The fourth part of the Parallel Programming in .NET tutorial looks at the early termination of parallel loops. Unlike sequential loops, which can be exited with the break command, there are considerations when stopping loops that run on multiple cores.
Early Loop Termination
All of the standard loops provided by C#, namely the for, foreach and while loops, give you the ability to exit a loop early using the break command. When encountered, the loop stops immediately, any remaining iterations are cancelled and the program continues with the command following the loop. This is useful when it is inefficient to continue with the loop. For example, if you are looping through a set of values searching for a specific item, you can exit the loop when the item is found.
The following for loop continues until a value that is greater than or equal to 15 is found. Iterations 16 to 20 are cancelled by the break.
for (int i = 1; i <= 20; i++)
{
Console.Write(i + " ");
if (i >= 15)
{
Console.WriteLine("Break on {0}", i);
break;
}
}
/* OUTPUT
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Break on 15
*/Early Termination of Parallel Loops
When you are working with parallel loops it is not as simple to exit early. As multiple iterations of the loop may be running in parallel, exiting from one iteration on one processor must be synchronised with other iterations that are executing on other cores. If the parallel operations were immediately stopped, it is possible that data would be left in an inconsistent state so the other iterations will always continue running. This means that the early termination of a parallel loop will usually give different results to exiting a sequential version.
Parallel Loop State
In this article we'll see how to exit from parallel loops and some of the associated side effects. The first problem that you may encounter is that the break command that is used with sequential loops is not available for their parallel counterparts. The following code will therefore not compile:
Parallel.For(1, 20, i =>
{
Console.WriteLine(i);
if (i >= 15)
{
Console.WriteLine("Break on {0}", i);
break;
}
});The break command is unavailable because, as mentioned previously in the tutorial, parallel loops are provided by static methods of the Parallel class, rather than as part of the C# language. The break command is a C# keyword that only works with C# loops. To co-ordinate the iterations of parallel loops, including breaking out of those loops as required, we must use an instance of the ParallelLoopState class.
The ParallelLoopState class enables iterations of parallel For loops and ForEach loops to interact with each other. You cannot instantiate the class directly. Instead, you add a second parameter to the lambda expression that defines the body of the loop. The loop method creates the loop state object automatically and gives you access to it via the second parameter. You can then use the methods of the ParallelLoopState object to exit from loops or to obtain information set in other iterations.
Using ParallelLoopState.Break
The first of the ParallelLoopState methods is Break. This is similar to the break statement of the sequential loops. The code below shows the method in action. Here we've recreated the loop from the above sequential code. The parallel loop decomposes the iterations according to the number of available cores. It then processes each iteration, checking if the loop control value is greater than or equal to fifteen. When such a value is found, the Break method is executed. Note that the ParallelLoopState variable, named "pls", is not instantiated directly.
Parallel.For(1, 20, (i, pls) =>
{
Console.Write(i + " ");
if (i >= 15)
{
Console.WriteLine("Break on {0}", i);
pls.Break();
}
});
/* OUTPUT
1 2 3 4 5 6 7 8 9 10 11 12 19 Break on 19
13 14 15 Break on 15
*/The results of the loop are interesting. In the comment in the code sample you can see a set of results generated using a dual-core processor. You can see that the Break method was executed twice, which you may not have expected. Also, values above fifteen were outputted, which would not happen with the sequential version of the loop.
One core started working from the iteration where the loop control variable had a value of one. It continued processing iterations 2, 3 and so on. Another core started with iteration 19. When the if statement checked the value it was found to be greater than or equal to fifteen so the Break method was called. However, the loop did not stop executing at this point.
The core that started working first continued processing until it also reached a value that was greater than or equal to fifteen. It then too called the Break method. At this point the loop stopped altogether.
The reason for this behaviour is that the Break method attempts to mimic the break command of sequential loops. Specifically, it tries to ensure that all of the iterations that would have been executed sequentially will be processed in the parallel loop. When any core calls Break, the iteration number is recorded in the ParallelLoopState object. This becomes the number of the last iteration that can possibly be executed. Other threads of execution will continue working until they reach this iteration number or encounter another Break statement, which will lower the number further.
The overall result is that all of the iterations that would have been processed in a sequential loop should be processed in the parallel version. However, many more iterations may be executed in the parallel loop. It is also possible that the same parallel loop may run a different set of iterations on separate executions. You should consider these possibilities whenever you create a parallel loop that may terminate early.
26 August 2011