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

From: Anthony Williams (anthony.ajw_at_[hidden])
Date: 2008-05-30 16:19:27

"vicente.botet" <vicente.botet_at_[hidden]> writes:

> ----- Original Message ----- 
> From: "Anthony Williams" <anthony.ajw_at_[hidden]>
>
>> Frank Mori Hess <frank.hess_at_[hidden]> writes:
>>
>>> On Friday 30 May 2008 06:23 am, Anthony Williams wrote:
>>>>
>>>> Given wait_for_any and wait_for_all (see my latest revision), I don't
>>>> think we need these more complex composite classes in many cases, and
>>>> where we do they might be better implemented specifically for the case
>>>> at hand.
>>>
>>> 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?
>>
>> You have N futures to wait for. You have to somehow register that
>> you're waiting for each one => you need O(N) operations.
>>
>> I suppose that if one of the futures was already ready, you could skip
>> the rest, but that doesn't really strike me as much of an improvement.
>>
>> Once it's done registering, wait_for_any then blocks until one of them
>> is ready. No polling, just a single wait.
>>
>> Could you elaborate on what you were getting at?
>>
>
>
> The O(N) comes from wait function.

> and on the all_futures_lock which will be inialized (O(N)), unlocked on wait 
> (O(N)) and locked after wait (O(N))

Yes, but these are additive, so the result is O(N). You have N futures
to wait for, so you cannot do better than O(N): the best you can do is
a constant factor.

As Frank and Johan have posted, it's the O(N) per wait, with O(N)
waits that's the killer.

Anthony
-- 
Anthony Williams            | Just Software Solutions Ltd
Custom Software Development | http://www.justsoftwaresolutions.co.uk
Registered in England, Company Number 5478976.
Registered Office: 15 Carrallack Mews, St Just, Cornwall, TR19 7UL