Boost logo

Boost :

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 Williams            | Just Software Solutions Ltd
Custom Software Development |
Registered in England, Company Number 5478976.
Registered Office: 15 Carrallack Mews, St Just, Cornwall, TR19 7UL

Boost list run by bdawes at, gregod at, cpdaniel at, john at