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