On Fri, May 30, 2008 at 10:24 PM, Anthony Williams <anthony.ajw@gmail.com> wrote:
Frank Mori Hess <frank.hess@nist.gov> writes:
On Friday 30 May 2008 11:45 am, Anthony Williams wrote:
One problem is wait_for_any is not sufficient to implement an efficient scheduler. You have to copy all the futures into wait_for_any so each wait_for_any call is O(N). So something like the future_selecter (should be spelled future_selector?) class I mentioned earlier would still be needed.
What do you mean by O(N) in this context?
I mean there are N method requests in my scheduler, and I want to wait until one of them is ready.
You have N futures to wait for. You have to somehow register that you're waiting for each one => you need O(N) operations.
Yes. But the scheduler is going to repeatedly wait on the same N futures (plus or minus one).
Aha: it's the repeated waits that matter. For one wait it's O(N) in all cases. If you wait again on (almost) the same set, until the set is empty, it's an issue if you have to redo the set up, as that is then O(N^2) in total.
That's a different use case to the one I imagined. I would call it a "future dispatcher" and have it invoke a callback on each future as it became ready.
Hum, I think that boost already has such a dispatcher: it is called asio::io_service ;). IMHO futures wait sets should be used to wait for very few events. If the number of events grows significantly, it is probably a sign that the application would be better redesigned as an event driven state machine. I do not think it is worth optimizing futures for large N. -- gpd