How to temporarily synchronize in a Parallel.ForEach loop?

Question

So here's a minimal version of code that works, but is inefficient:

Parallel.ForEach(list, x =>
{
    doThing1(x);
});

Thing1Done = true;

Parallel.ForEach(list, x =>
{
    doThing2(x);
});

Thing2Done = true;

Parallel.ForEach(list, x =>
{
    doThing3(x);
});

Thing3Done = true;

Intuitively, I'd like to run all 3 "things" within the same loop, but they must be able to synchronize temporarily to update the respective Thing*n*Done property.

Pseudocode for this idea as follows:

Parallel.ForEach(list, x =>
{
    doThing1(x);
    // wait for doThing1 to be completed for all other elements in list
    Thing1Done = true;

    doThing2(x);
    // wait for doThing2 to be completed for all other elements in list
    Thing2Done = true;

    doThing3(x);
    // wait for doThing3 to be completed for all other elements in list
    Thing3Done = true;
});

So for example, it's necessary that doThing1() finishes its execution for every member of list before Thing1Done is set to true. doThing2() can only begin after Thing1Done has been set.

Each individual step is not overly expensive, and I'm concerned about the overhead involved with the naive approach. What is the best way to efficiently solve this task, assuming that the overhead involved in initializing the threads is my largest concern? I'd also like to avoid busy waiting (where the thread spins in a while loop doing nothing useful until some flag is set to true) if at all possible.

I am willing to write something more general if the Parallel library cannot do what I want.

Answer 1

You could use the Barrier threading syncronization primitive:

var barrier = new Barrier(list.Count);

var options = new ParallelOptions()
{
    MaxDegreeOfParallelism = list.Count,
    TaskScheduler = new ThreadPerTask()
};

Parallel.ForEach(list, options, x =>
{
    doThing1(x);
    // wait for doThing1 to be completed for all other elements in list
    barrier.SignalAndWait();

    doThing2(x);
    // wait for doThing2 to be completed for all other elements in list
    barrier.SignalAndWait();

    doThing3(x);
    // wait for doThing3 to be completed for all other elements in list
    barrier.SignalAndWait();
});

The SignalAndWait method signals the completion of an item, and waits until all items have completed (until the ParticipantsRemaining property becomes zero). After that the CurrentPhaseNumber property is incremented, all threads are unblocked simultaneously, and are free to race towards the next milestone.

This is an extremely inefficient way to process the items of the list, because it requires a dedicated thread per item. You will need a custom TaskScheduler in order to implement this setup, like the one shown below:

public class ThreadPerTask : TaskScheduler
{
    protected override void QueueTask(Task task)
    {
        new Thread(() => this.TryExecuteTask(task))
        {
            IsBackground = true
        }.Start();
    }

    protected override bool TryExecuteTaskInline(Task task,
        bool taskWasPreviouslyQueued) => false;

    protected override IEnumerable<Task> GetScheduledTasks() { yield break; }
}

IMHO your first approach, the one that uses multiple consecutive Parallel.ForEach loops, is the correct way to solve this problem.

Answer 2

As mentioned in the comments, your second example will have enormous overhead since it would require using one thread per item, and that will probably be more threads than are available in the threadpool, so new threads will need to be created, but the rate new threads are created are limited. So I would expect terrible performance. At least assuming you have many items to process.

If the requirements are that doThing1 need to have been completed for all items before doThing2 starts, then I do not think you can do much better than multiple sequential parallel-loops. I would not expect the overhead of this approach to be all to bad, since it will use the threadpool rather than spawning new threads.

It is possible a custom partitioner might help, or pre-split your list into chunks and process each chunk in parallel. By default parallel loops try to split the work into partitions, and try to adapt the size of these partitions to balance overhead with process-utilization. But If you have prior knowledge of the kind of work to do you can probably do a better job yourself. As always when talking about performance, you will probably need to measure to see what alternative is faster.

If you split the work into chunks similar to the number of processors you could perhaps use a model similar to your second example. But I'm unsure if it has any actual advantages.