Details
-
Improvement
-
Status: Accepted
-
Major
-
Resolution: Unresolved
-
None
-
None
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:
- Split the iteration of items into 1 <= N <= num_worker_threads segments.
- Spawn N-1 additional temporary execution Processes (or re-use from a pool)
- Dispatch to these N-1 additional processes for them to perform their segment of the iteration.
- Perform the 1st segment on the current Process.
- 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:
- Split the iteration of items into 1 <= N <= num_worker_threads segments. Store these segments in a lock free queue.
- Spawn N-1 additional temporary execution Processes (or re-use from a pool)
- Perform the 1st segment on the current Process.
- Each process pulls a segment from the queue and executes a segment.
- 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.
Attachments
Issue Links
- is blocked by
-
MESOS-8256 Libprocess can silently deadlock due to worker thread exhaustion.
-
- Accepted
-
- is related to
-
MESOS-9234 Improve performance of offer fan-out in the master.
-
- Accepted
-
- links to