Re: [boost] Updated version of futures library

From: Frank Mori Hess (fmhess_at_[hidden])
Date: 2008-06-03 00:16:56

On Monday 02 June 2008 20:56, Frank Mori Hess wrote:
> 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. 

Ah, I knew there was some mistake.  At the beginning of the loop, all N+M 
method requests are "not ready" as far as the scheduler knows.  So that 
adds another O(M*P) dependencies, giving O((N+M)*P) to iterate through 
dependencies.

> 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. 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.

So we end up with O((N/M + 1)*P).