How to implement std::when_any without polling?

user_508343 0
Viewed 2009

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?

c++17 concurrency standards multithreading c++
3 Answers

I have posted an implementation of when_any over on CodeReview. As Yakk said in his answer,

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.

So my implementation relies on future::then(), and the gist of it is:

template<class... Futures>
struct when_any_shared_state {
    promise<tuple<Futures...>> m_promise;
    tuple<Futures...> m_tuple;
    std::atomic<bool> m_done;
    std::atomic<bool> m_count_to_two;

    when_any_shared_state(promise<tuple<Futures...>> p) :
        m_promise(std::move(p)), m_done(false), m_count_to_two(false) {}
};

template<class... Futures>
auto when_any(Futures... futures) -> future<tuple<Futures...>>
{
    using shared_state = detail::when_any_shared_state<Futures...>;
    using R = tuple<Futures...>;
    promise<R> p;
    future<R> result = p.get_future();

    auto sptr = make_shared<shared_state>(std::move(p));
    auto satisfy_combined_promise =
        [sptr](auto f) {
            if (sptr->m_done.exchange(true) == false) {
                if (sptr->m_count_to_two.exchange(true)) {
                    sptr->m_promise.set_value(std::move(sptr->m_tuple));
                }
            }
            return f.get();
        };
    sptr->m_tuple = tuple<Futures...>(futures.then(satisfy_combined_promise)...);
    if (sptr->m_count_to_two.exchange(true)) {
        sptr->m_promise.set_value(std::move(sptr->m_tuple));
    }
    return result;
}

You attach a continuation to each incoming future (using then). This continuation holds a shared_ptr to a shared state. The shared state holds a count-to-one (m_done) and a count-to-two (m_count_to_two). Each continuation that executes will increment the count-to-one; if it's the winner, it will also increment the count-to-two. The main thread will also increment the count-to-two after it finishes setting up all this stuff. As soon as the count-to-two has reached 2 (indicating that the main thread finished setting up and at least one continuation has executed), we'll call set_value on the promise corresponding to when_any's return future. Ta-da!

user_14248770
Related