-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Monday 02 June 2008 19:17 pm, Peter Dimov wrote:
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.
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. 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. 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. In my case, where the scheduler thread is executing the tasks itself (as opposed to sending them to a thread pool for instance), if I were in optimization mode I would start looking at breaking things up more finely once M hit 1, to maximize use of available processors. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) iD8DBQFIRJbc5vihyNWuA4URAjs4AKCnkXU1L1I16IptutBfU30IIhL19wCePg5p OQE5Qc7GW3032ITk8Ht36e0= =Njyz -----END PGP SIGNATURE-----