From: Peter Dimov (pdimov_at_[hidden])
Date: 2008-06-02 19:17:36
Frank Mori Hess:
>> wait_for_any( waiting_ );
> A scheduler which takes O(N) to dispatch a method request is considered
> inefficient. N being the number of pending method requests in the
> The call to wait_for_any alone is O(N), thus my motivation for using
> future_selector for a scheduler.
Using algorithmic complexity to evaluate the performance of a call that
blocks because you have nothing to do is not quite correct. Let's tidy up
the pseudocode a bit:
list< future<void> > deps_;
wait_for_any( deps_ );
for each in deps_:
if ready() erase;
for each pending task:
if all dependencies are ready()
I believe that the "if all dependencies are ready" part corresponds to your
One can reasonably assume that wait_for_any will return early if it finds a
ready() future, bit even if it doesn't, we can optimize the loop to only
call wait_for_any when there was no activity on the last iteration.
So we only enter wait_for_any when none of deps_ are ready() and it blocks.
It doesn't really matter what the overhead of wait_for_any is (as long as it
isn't pathological) since it's usually going to block anyway. The worse the
overhead of wait_for_any, the less often we'll enter it. What matters, in
the end, is whether the rest of the scheduler can keep up with the outside
world submitting requests; if wait_for_any turns into a bottleneck, it
simply won't be called at all.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk