[C++] Develop threading APIs to accommodate nested parallelism

[asfimport]

Tasks invoked in parallel may be able to submit their own subtasks, which in OpenMP and TBB documentation is often called "nested parallelism".

If a task blocks on the completion of subtasks, then outright deadlocks are possible – running tasks are all blocking on their subtasks, but the thread pool will not schedule any further tasks.

I suggest that such code have a way to indicate to the thread pool (if one is passed in) that it is blocking on the completion of other tasks so that further tasks can be run while the task waits for its child tasks to complete. One possible way to do this is to have a floating "soft limit" for concurrent tasks that can be incremented when tasks are waiting.

So if we normally allow 8 concurrent tasks, then this can be temporarily increased for each "suspended" task. Preferably we would provide some way for the dependent task group to "awaken" the suspended task so that it does not have to do any work while waiting for the task group to finish

Note this feature can also be used in tasks that are waiting for IO calls

Reporter: Wes McKinney / @wesm
Assignee: Weston Pace / @westonpace

Subtasks:

• [C++] Add ConcatMap, MergeMap, and an async-reentrant version of Map
• [C++] Create sequencing AsyncGenerator
• [C++] Create AsyncGenerator from Future<AsyncGenerator>
• [C++] Create enumerating generator
• [C++] Create Scanner interface
• [C++] Create basic AsyncScanner implementation

Related issues:

• [C++][Dataset] Expose a nested parallel option for Scanner::ToTable (is related to)
• [GLib][Ruby][Dataset] Remove bindings for internal classes (is related to)

PRs and other links:

• GitHub Pull Request #9607

_{Note: This issue was originally created as ARROW-7001. Please see the migration documentation for further details.}

[asfimport]

Wes McKinney / @wesm:
As a demonstration of the success of this, we should be able to run a task that spawns recursive subtasks to arbitrary nesting depth on a ThreadPool with size 1. This would also serve as a helpful stress performance test e.g. to see how quickly a recursively nested task chain with depth ~100 can be executed.

[asfimport]

Antoine Pitrou / @pitrou:
Ok, so the problem here is to have a task blocking on another, right? Otherwise, you can schedule a task from another task, and pass e.g. a callback to that new task. Not very pretty, but it works.

I still think it would be worthwhile discussing this on a higher level, i.e. which execution model we have in mind. In one execution model, IO is interspersed with computations in the same thread and therefore a way to signal that a task is blocking on some external completion is needed. In another execution model, you have a driver thread that does IO and pushes available data to pure-CPU workers.

[asfimport]

Wes McKinney / @wesm:
I think realistically we may need to support both styles of scheduling

To make the problem more concrete, I think we should focus on the needs of reading multiple files that are capable of parallelizing at the file level. For example, Parquet files. Not only do we parallelize at the column level, but within a thread reading a column, we perform IO calls which may block. Somehow we need to not block a CPU core on an IO call returning. Do we need to do a major refactoring? Or can the current code be retrofitted with a suspend-task-resume-task API that allows other tasks to be started when there is IO waiting.

Facebook's Folly library has a fibers / coroutines library that may provide some ideas about what kind of programming models make sense for certain applications

https://github.com/facebook/folly/tree/master/folly/fibers

[asfimport]

Wes McKinney / @wesm:
I'm not thinking this is going to be completed for 1.0.0 yet

[asfimport]

Anton Malakhov:
Please consider ideas from this blog: https://habr.com/en/company/intel/blog/542908/

[asfimport]

Weston Pace / @westonpace:
Thanks [~anton-malakhov] .  I took a look at the blog and oox looks like it can be useful.  I have been working on this issue and a slightly broader goal of removing all blocking I/O waits from the CPU thread pool (see https://docs.google.com/document/d/1tO2WwYL-G2cB_MCPqYguKjKkRT7mZ8C2Gc9ONvspfgo/edit?usp=sharing ).

 

I have been using an arrow::Result-aware implementation of std::future (arrow::Future) and using simple Then/All/Any continuations.  This only allows for dags of flow dependencies (and not output & anti dependencies).  I'm fairly certain this will be sufficient and there is a broad understanding of the capabilities from other languages that support this kind of construct (e.g. Javascript's Promise.then, C# Task.ContinueWith, Java's CompletableFuture).

 

I was not able to find any oox library or mention of licensing.  If there is a repository out there somewhere with a reference implementation I'd be happy to take a closer look.  I appreciate you bringing sharing this but at the moment I do not think the sophistication offered by oox is needed to solve this problem.

[asfimport]

Anton Malakhov:
Thanks for looking into this! As I mentioned in the article, OOX is not productized but it has PoC implementation, which was created for TBB. If there is enough interest from you and other people, I can try to convince Intel to publish the sources.

[asfimport]

Weston Pace / @westonpace:
@pitrou @lidavidm @wesm Given the state of the async operators, the exec plan work, and the fact that nested parallelism is supported on parquet (e.g. ARROW-12597) I am going to mark this resolved.  Feel free to reopen with details if you think more is needed.