Re: [boost] Updated version of futures library

From: Peter Dimov (pdimov_at_[hidden])
Date: 2008-06-02 21:26:51

Frank Mori Hess:
...

>> for each in deps_:
>>     if ready() erase;
>>
>> for each pending task:
>>     if all dependencies are ready()
>>         execute task
...

> Okay, lets try ignoring the wait_for_any call.  Say you have on average N
> method requests just sitting in your scheduler that are not ready, and 
> have
> on average M method requests that are ready to execute, and each method
> request has on average P dependencies (I'd imagine P would probably be
> small).  That means each pass through your pseudocode will take O(N*P) to
> iterate through all the unready dependencies of the unready method 
> requests.

The number of unready dependencies can be lower than N*P, but let's ignore 
that for now.

> Then it will take O(M+N) to go through all the method requests and execute
> the M ready tasks.  That results in O(N*P/M+1) per method request 
> executed.

I think that going through the method requests takes (N+M)*P, because of the 
"all dependencies are ready" part. (I think that this is also true for your 
scheduler.) So we have (2*N+M)*P total, or (2*N/M+1)*P per executed request.

> Having M in the denominator is nice, as you would expect it to scale with 
> N,
> and it means the scheduler probably won't break down under heavy load.
>
> On the downside, in a common case I'd expect M to be small (between 0 and 
> 1),
> with performance concerns about the scheduler starting to come into play 
> as M
> approaches 1.

If the scheduler performance is insufficient, it will not be able to 
maintain a low M. If it does manage to maintain a low M, then its 
performance is sufficient.

Stated differently, in the additional N*P time taken by the first loop, some 
of the futures will become ready that wouldn't otherwise, and the second 
loop will execute more tasks, automatically diluting the overhead.