Boost logo

Boost :

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
> scheduler.
> 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()
        execute task

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, gregod at, cpdaniel at, john at