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

From: vicente.botet (vicente.botet_at_[hidden])
Date: 2008-05-30 13:23:52

----- Original Message ----- 
From: "Anthony Williams" <anthony.ajw_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Friday, May 30, 2008 5:45 PM
Subject: Re: [boost] [future] Early draft of wait for multiple 
futuresinterface

> 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.
            unsigned wait()
            {
                all_futures_lock lk(futures);
                for(;;)
                {
                    for(unsigned i=0;i<futures.size();++i)        // O(N)
                    {
                        if(futures[i].future->done)
                        {
                            return futures[i].index;
                        }
                    }
                    cv.wait(lk);
                }
            }

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

            struct all_futures_lock
            {
                unsigned count;
                boost::scoped_array<boost::unique_lock<boost::mutex> > 
locks;

                all_futures_lock(std::vector<registered_waiter>& futures):
                    count(futures.size()),locks(new 
boost::unique_lock<boost::mutex>[count])
                {
                    for(unsigned i=0;i<count;++i)         // O(N)
                    {
                        locks[i]=boost::unique_lock<boost::mutex>(futures[i].future->mutex);
                    }
                }

                void lock()
                {
                    boost::lock(locks.get(),locks.get()+count); // O(N)
                }

                void unlock()
                {
                    for(unsigned i=0;i<count;++i) // O(N)
                    {
                        locks[i].unlock();
                    }
                }
            };

Best

Vicente