[MESOS-8587] Introduce a parallel for each loop (and other parallel algorithms).

• Type: Improvement
• Status: Accepted
• Priority: Major
• Resolution: Unresolved
• Component/s: libprocess
• Labels: performance
• Assignee: Unassigned
• Reporter: Benjamin Mahler
• Created: 15/Feb/18 19:49
• Updated: 15/Sep/18 20:56

Description

Consider the following code:

SomeProcess::func()
{
  foreach (const Item& item, items) {
    // Perform some const work on item.
  }
}

When items becomes very large, this code would benefit from some parallelism. With a parallel loop construct, we could improve the performance of this type of code significantly:

SomeProcess::func()
{
  foreach_parallel (items, [&](const Item& item) {
    // Perform some const work on item.
  });
}

Ideally, this could enforce const-access to the current Process for safety. An implementation of this would need to do something like:

1. Split the iteration of items into 1 <= N <= num_worker_threads segments.
2. Spawn N-1 additional temporary execution Processes (or re-use from a pool)
3. Dispatch to these N-1 additional processes for them to perform their segment of the iteration.
4. Perform the 1st segment on the current Process.
5. Have the current Process block to wait for the others to finish. (note need to avoid deadlocking the worker threads here! See MESOS-8256)

An alternative implementation would be to pull work from a shared queue:

1. Split the iteration of items into 1 <= N <= num_worker_threads segments. Store these segments in a lock free queue.
2. Spawn N-1 additional temporary execution Processes (or re-use from a pool)
3. Perform the 1st segment on the current Process.
4. Each process pulls a segment from the queue and executes a segment.
5. If the current Process finds the queue empty, it then needs to block waiting for outstanding segments to finish. Note that this cannot deadlock: if an item was pulled from the queue, a worker is executing it.

An example use case for this is the task reconciliation loops in the master:
https://github.com/apache/mesos/blob/1.5.0/src/master/master.cpp#L8385-L8419

This generalizes to many other algorithms rather than just iteration. It may be good to align this with the C++ Parallelism TS, which shows how many of the C++ algorithms have potential for parallel counterparts.

Issue Links

• is blocked by: MESOS-8256 Libprocess can silently deadlock due to worker thread exhaustion.
• is related to: MESOS-9234 Improve performance of offer fan-out in the master.
• links to: Extensions for Parallelism
• links to: HPX