Boost logo

Boost :

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

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk