How to implement std::when_any without polling?

Question

Consider http://en.cppreference.com/w/cpp/experimental/when_any. The following is just a naive and simplified implementation:

#include <future>

template<typename Iterator>
auto when_any(Iterator first, Iterator last)
{
    while (true)
    {
        for (auto pos = first; pos != last; ++pos)
        {
            if (pos->is_ready())
            {
                return std::move(*pos);
            }
        }
    }
}

I am not satisfied because it is a busy polling in an infinite loop.

Is there a way to avoid busy polling?

Answer 1

A polling free version would launch 1 thread per future and have them set a condition variable with which future is ready.

Then you "leak" the threads until the futures are ready while returning the fact one is ready.

This sucks. But no polling.

To do better, you need to have a future with a continuation you can set (and remove ideally). Then you just ask the futures to notify you when done, then wait . This requires modifying or writing your own future.

This is one of the reasons both continuations and when_any are both proposed for standarization. You need them in the future.

Now if you have your own system, you can base it off a thread safe queue delivering stuff rather than futures, implemented via condition variables. This requires cooperation at the point of "future" creation.

struct many_waiter_t {
  std::mutex m;
  std::condition_variable cv;
  std::vector<std::size_t> index;

  std::size_t wait() {
    auto l = lock();
    cv.wait(l, [this]{
      return !index.empty();
    });
    auto r = index.back();
    index.pop_back();
    return r;
  }
  void set( std::size_t N ) {
    {
      auto l = lock();
      index.push_back(N);
    }
    cv.notify_one();
  }
};
template<class T>
std::future<T> add_waiter( std::future<T> f, std::size_t i, std::shared_ptr<many_waiter_t> waiter )
{
  return std::async([f = std::move(f), waiter, i]{
    auto r = f.get();
    waiter.set(i);
    return r;
  });
}

Consuming an array of futures fs, we can generate a new array of futures f2s and a waiter, such that the waiter can be non-spinlock waited against until a future is ready, and the f2s correspond to the original fs.

You can repeatedly wait on the waiter until the f2s are all ready.