C++ async vs OpenMP tasks

Question

In OpenMP, I can create a bunch of tasks as follows and run them asynchronously using some fixed number of threads:

#pragma omp parallel
{
   #pragma omp single 
   {
      for (int i = 0; i < 1000; i++) {
         #pragma omp task
         f(i);
}  }  }

In C++11, I can do something not-quite-same std::async:

std::vector<std::future> futures;
for (int i = 0; i < 1000; i++) {
   auto fut = std::async(f, i);
   futures.push_back(std::move(fut));
}
...
for (auto & fut : futures) {
  auto res = fut.get();
  // do something with res
}

What I worry about is efficiency. If I am correct, in OpenMP, tasks are stored in some task pool and then distributed to threads (automatically by the OpenMP runtime).

In C++, at the moment of invoking std::async, the runtime decides whether to run f(i) asynchronously in a new thread or defer its run to the point of invoking std::future::get.

Consequently, either a runtime

1. creates 1000 threads and run them all concurrently,
2. or create less threads, but then some invocation of f(i) will be performed sequentially in the main thread (within the final loop).

Both these options seem to be generally less efficient than what OpenMP does (create many tasks and run them concurrently in a fixed number of threads).

Is there any way to get the same behavior as what OpenMP tasks provide with C++ threading?

UPDATE

I did some measurements with the following code: https://wandbox.org/permlink/gLCFPr1IjTofxwQh on 12C Xeon E5 CPU compiled with GCC 7.2 and -O2:

1. OpenMP runtime with 12 threads: 12.2 [s]
2. C++ threading runtime: 12.4 [s]

(averages from serveral runs). They seem to be practically the same.

However, I also tried the same with 500,000 tasks (n) and 1,000 iterations within them (m) and the times then differed significantly:

1. OpenMP runtime with 12 threads: 15.1 [s]
2. C++ threding runtime: 175.6 [s]

UPDATE 2

I measured how many times a new thread was created (following this answer to interpose pthread_create calls: https://stackoverflow.com/a/3709027/580083):

First experiment (20,000 tasks, 20,000 iterations within):

1. OpenMP runtime with 12 threads: 11
2. C++ threding runtime: 20,000

Second experiment (500,000 tasks, 1,000 iterations within):

1. OpenMP runtime with 12 threads: 11
2. C++ threding runtime: 32,744

Answer 1

Your analysis is quite good, but I think there is a loophole for threadpools in std::async.

OpenMP does use a fixed, user-controlled amount of threads that execute tasks quite flexibly. untied tasks can even move between threads, although that doesn't seem to be well-supported in practice.

Yes, as per the C++11 standard, the implementation must chose either std::launch::async or std::launch::deferred. The former one must create a std::thread object, while the latter one will execute the task's code in the thread calling wait. However, the standard leaves a Note (emphasis mine):

If this policy is specified together with other policies, such as when using a policy value of launch::async | launch::deferred, implementations should defer invocation or the selection of the policy when no more concurrency can be effectively exploited.

To be honest fail to see how the standard wording besides that note would allow an implementation to defer the decision - but the standard seems to actually encourage thread pools! If decision to chose launch:async is deferred, it means that the required new std::thread could reuse an existing thread of execution - at least I don't see why not.

Originally I thought that std::thread could also be implemented as green threads which sort-of also means a thread pool. However, the standard remarks that threads [managed by <thread>] are intended to map one-to-one with operating system threads.

At the end of the day measure to verify your performance. There may be a very bad OpenMP implementation or a very clever standard library implementation.

This answer to a similar question, presents some measurement results that indicate high overhead of std::async and also shares the measurement code.

Answer 2

Both these options seem to be generally less efficient than what OpenMP does (create many tasks and run them concurrently in a fixed number of threads).

The thing is, you actually don't know that that is what OpenMP is doing. OpenMP is an API that lets you specify "this task can be parallelized" and provide guides on how the implementation should try to parallelize it. It doesn't expose the low-level details of that implementation unless you specify them yourself. It might try to allocate a fixed number of threads to execute batches of tasks in each thread, OR it might create threads for each individual task. It might even forgo allocating any threads at all if the implementation thinks your target machine is incapable of benefiting from the parallelism.

This is both a strength and weakness of OpenMP: It will try to do what it thinks is best for your particular task, which may mean optimizing the runtime of your program, but it might also occasionally be wrong about what actually is best. std::async is, in most respects, in the same boat: the implementation (and compiler) will make efforts to try to guess what the most efficient bytecode of your code will be, but there's always a chance it's wrong. So std::async, too, is often implemented to use a dedicated (fixed-size) thread-pool. It might split each task into its own thread, or execute everything on a single thread.

If you have expectations about the precise implementation of your multithreaded code, you need to specify those expectations using lower-level concepts and objects like std::thread. If you want to let your compiler assume what's best (and the compiler is often right), std::async and OpenMP are probably comparable.

And of course, it's important to measure: your situation might be one where OpenMP has the best idea about what's fastest. Or maybe not. The only way you'll know for sure is if you implement both versions and measure which is fastest.