Re: [boost] Futures Review - wait_for_any complexity

Subject: Re: [boost] Futures Review - wait_for_any complexity
From: Anthony Williams (anthony.ajw_at_[hidden])
Date: 2009-01-20 09:01:14

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

> there was a long discusion about the complexity of wait_for_any some
> mounts ago. If I understood well the probleme was in the
> future_waiter::wait
>
>     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);
>         }
>     }

Yes.

> What we need is a synchonization structure that returns a user
> specific data (in this case the index). So we can replace by
>
>     unsigned wait()
>     {
>         all_futures_lock lk(futures);
>         return cv_with_value.wait(lk);
>     }

I'm not sure. I think we're better off with a simple
mutex/value/cond-var triplet in the waiter. We then don't need the
"all_futures_lock".

    unsigned wait()
    {
        boost::unique_lock<boost::mutex> lk(mut);
        while(ready_future_index<0)
        {
            cv.wait(lk);
        }
        return ready_future_index;
    }

> We need to pass to the register_external_waiter the specific data,
> in this case the index

and the mutex => better off as a struct of some kind.

struct ready_future_value
{
    boost::mutex mut;
    int ready_future_index;
    boost::condition_variable cv;

    void notify_ready(unsigned index)
    {
        boost::lock_guard<boost::mutex> lk(mut);
        if(ready_future_index<0)
        {
            ready_future_index=index;
            cv.notify_all();
        }
    }
} ready_value;

>     template<typename F>
>     void add(F& f)
>     {
>         if(f.future)
>         {
>             futures.push_back(registered_waiter(f.future,
>//             f.future->register_external_waiter(cv,future_count,mut),future_count));

            f.future->register_external_waiter(&ready_value,future_count),future_count));

>         }
>         ++future_count;
>     }
>
>
> So the list of waiters is now 
>     
>//     typedef std::list<std::pair<condition_variable_any_with_value<unsigned>*, 
 
    typedef std::list<std::pair<ready_future_value*,

>                                 unsigned> 
>                             > waiter_list;
>     waiter_list::iterator register_external_waiter(
>//                 condition_variable_any_with_value<unsigned>& cv_with_value, 

                ready_future_value& ready_value, 

>                 unsigned indx)
>     {
>         boost::unique_lock<boost::mutex> lock(mutex);
>         do_callback(lock);
>         return external_waiters.insert(external_waiters.end(),std::make_pair(&cv, indx));
>     }
>
> The notification to the waiters will no use the new notify_all
> interface passing as parameter the index of the future relative to
> the condition_variable.
>
>     void mark_finished_internal()
>     {
>         done=true;
>         waiters.notify_all();
>         for(waiter_list::const_iterator it=external_waiters.begin(),
>                 end=external_waiters.end();it!=end;++it)
>         {

             (it->first)->notify_ready(it->second);

>         }
>     }

It turns out that my ready_future_value struct isn't too far from your
cv_with_value, so I like the idea, but not the name. (I don't like
ready_future_value either for that matter).

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