Exiting from Parallel Loops Early

Stephen Toub - MSFT

Exiting out of loops early is a fairly common pattern, one that doesn’t go away when parallelism is introduced.  To help simplify these use cases, the Parallel.For and Parallel.ForEach methods support several mechanisms for breaking out of loops early, each of which has different behaviors and targets different requirements.

Exceptions

In a sequential loop, an exception thrown from the loop causes the looping construct to immediately cease.  For our parallel loops, we’ve chosen to get as close to this as is possible while still being reliable and predictable.  This means that when an exception is thrown out of an iteration of a Parallel loop, the loop attempts to prevent additional iterations from starting, though it allows already started iterations to complete.  Once all iterations have ceased, the loop gathers up any exceptions that have been thrown, wraps them in a System.AggregateException and throws that aggregate out of the loop.  For cases where individual operations may run for a long time (and thus may delay the loop’s exit), overloads of Parallel.For and Parallel.ForEach exist that provide a ParallelLoopState instance to the body; this instance exposes an IsExceptional property, which indicates whether another iteration has thrown an unhandled exception.  Iterations may cooperatively check this property, allowing a long-running iteration to cooperatively exit early when it detects that another iteration has failed.

While this exception logic does support exiting out of a loop early, it is not the recommended mechanism for doing so; rather, it exists purely to assist in exceptional cases, cases where you breaking out early wasn’t an intentional part of the algorithm.  As is the case with sequential constructs, exceptions should not be relied upon for control flow.

Note that this exceptions behavior isn’t optional: there’s no way to tell the looping construct to delay the rethrowing of exceptions until the loop has completed, just as there’s no built-in way to do that with a sequential for loop.  If you wanted that behavior with a for loop, you’d likely end up writing code like the following:

var exceptions = new Queue<Exception>();
for(int i=0; i<N; i++)
{
    try
    {
        … // loop body goes here
    }
    catch(Exception exc) { exceptions.Enqueue(exc); }
}
if (exceptions.Count > 0) throw new AggregateException(exceptions);

If this is the behavior you desire, that same manual handling is also possible using Parallel.For:

var exceptions = new ConcurrentQueue<Exception>();
Parallel.For(0, N, i=>
{
    try
    {
        … // loop body goes here
    }
    catch(Exception exc) { exceptions.Enqueue(exc); }
});
if (!exceptions.IsEmpty) throw new AggregateException(exceptions);

Stop and Break

The ParallelLoopState referred to in the previous section on exceptions provides additional support for exiting loops early.  This support comes in the form of two methods and two properties: Stop(), Break(), IsStopped, and LowestBreakIteration.

If a loop iteration calls Stop, the loop will attempt to prevent more iterations from starting.  Once there are no more iterations executing, the loop will return successfully (i.e. without an exception).  The return type of Parallel.For and Parallel.ForEach is a ParallelLoopResult struct: if Stop caused the loop to exit early, this result’s IsCompleted property will return false.  As with exceptions, where an IsExceptional property enables other running iterations to cooperatively detect an exception from another iteration, the IsStopped property enables an iteration to detect when another iteration has called Stop.

Break is very similar to stop, except it provides extra guarantees.  Whereas Stop informs the loop that no more iterations need be executed such that the loop can cease execution as soon as possible, Break informs the loop that no iterations after the current one (e.g. where the iteration number is higher, or where the data comes after the current element in the data source) need be run, but that iterations prior to the current one still need to be run.  Break may be called from multiple iterations, and the lowest iteration from which Break was called is the one that takes effect; this iteration number can be retrieved from the ParallelLoopState’s LowestBreakIteration property, a nullable value.

If the ParallelLoopResult’s IsCompleted property returns true, all of the iterations were processed.  If IsCompleted returns false and LowestBreakIteration.HasValue is false, Stop was used to exit the loop early.  If IsCompleted returns false and LowestBreakIteration.HasValue is true, Break was used to exit the loop early.

Stop is typically useful for unordered search scenarios, where the loop is looking for something and can bail as soon as it finds it.  Break is typically useful for ordered search scenarios, where all of the data up until some point in the source needs to be processed, with that point based on some search criteria.

CancellationToken

All of the previous mentioned mechanisms are based on the body of the loop exiting early, i.e. the body of the loop may throw an unhandled exception, may call Stop, or may call Break.  Sometimes, however, we want an entity external to the loop to be able to terminate the loop; this is known as cancellation.

Cancellation is supported in parallel loops through the new System.Threading.CancellationToken type introduced in .NET 4.0.  Overloads of all of the methods on Parallel accept a ParallelOptions instance, and one of the properties on ParallelOptions is a CancellationToken.  Simply set this CancellationToken property to the CancellationToken that should be monitored for cancellation, and provide that options instance to the loop’s invocation.  The loop will monitor the token, and if it finds that cancellation has been requested, it will again stop launching more iterations, wait for all existing iterations to complete, and then throw an OperationCanceledException.

Employing Multiple Exit Strategies

It’s possible that multiple exit strategies could all be employed concurrently; we’re dealing with parallelism after all.  In such cases, exceptions always win: if an unhandled exception has occurred, the loop will always propagate those exceptions, regardless of whether Stop or Break was called or whether cancellation was requested. 

If no exceptions occurred but the CancellationToken was signaled and either Stop or Break was used, there’s a potential race as to whether the loop will notice the cancellation prior to exiting.  If it does, the loop will exit with an OperationCanceledException.  If it doesn’t, it will exit from the Stop/Break as explained above.

Note, though, that Stop and Break may not be used together.  If the loop detects that one iteration called Stop while another called Break, the invocation of whichever method ended up being invoked second will result in an exception being thrown.

Finally, for long running iterations, there are multiple properties an iteration might want to check to see whether it should bail early: IsExceptional, IsStopped, LowestBreakIteration, etc.  To simplify this, ParallelLoopState also provides a ShouldExitCurrentIteration property, which consolidates all of those checks.  The loop itself checks this value prior to invoking iterations.

0 comments

Discussion is closed.

Feedback usabilla icon