Re: [boost] [future] Early draft of wait for multiple futures interface

From: Frank Mori Hess (frank.hess_at_[hidden])
Date: 2008-05-30 13:23:43

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

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).  So as Johan already pointed out, passing iterators to a 
seperate container of futures to wait_for_any() will cause the sheduler to 
call wait_for_any N times and take O(N^2) to dispatch N method requests.  On 
the other hand, if the container of futures and wait_for_any are integrated 
into one class (future_selector), then it doesn't have to do the full 
setup/tear down with each wait.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFIQDgf5vihyNWuA4URAnr9AKDFSPDXNZub0bu4C3d/cbGdDJd+VwCgpmsv
t+JA1JnP0mQPP4iv61wVjZw=
=u825
-----END PGP SIGNATURE-----