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
> 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).
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk