Re: [boost] Updated version of futures library

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 
method_request::ready.

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.