Review Request: future library (Gaskill version)

[Anthony Williams-3]

"vicente.botet" <vicente.botet@...> writes:

> Well let me come back to my initial example. Supose that I had
>     Result f(InOut& ref);
>     // ...
>         {
>             InOut v=0;
>             // ...
>             v = 13;
>             Result r = f(v);
>             // ...     use r or v;
>             g(r, v);
>             v = 15;
>         }
>
> Do you mean that the following works with your proposal?
>
>     unique_future<Result> f(shared_future<InOut>& ref);
>     // ...
>         {
>             shared_future<InOut> v; v->get()=0;
>             // ...
>             v->get() = 13;
>             unique_future<Result> r = f(v);
>             // ... use r or v;
>             g(r->get(), v->get());
>             v->get() = 15;
>         }

Not quite. You can't set a value on a future by writing to the result of a
call to get() - you need a promise or a packaged task for that. However, you
can write:

void foo()
{
    promise<InOut> p;
    shared_future<InOut> v=p.get_future();
    p.set_value(13);

    unique_future<Result> r=f(v);

    // v.get() may have changed if f took v by reference
    g(r.get(),v.get());
}

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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Johan Torp]

vicente.botet wrote:

>> If we want consistency what we
>> would need is something like
>>
>>     future<Result> f(future<InOut&>& ref);
>>
>
> Firstly, this is a dangerous design. The calling thread must keep the
> reference alive until the future is ready - no matter what. For instance,
> what if it's owner thread tells it to terminate?

What do you propose instead? What do you think of
     future<Result> f(cosnt InOut& in, future<InOut>& out);

    future<InOut> fv;
    r= f(v,  fv)
    v = fv.get();

If result was binary - succeed or "not possible" I would use
  unique_future<boost::optional<InOut> > f();
otherwise
  unique_future<tuple<Result, InOut> > f();
or
  unique_future<variant<ErrorCode, InOut> >

I'm assuming InOut is movable and we have r-value references. Otherwise, use unique_ptr/auto_ptr instead of InOut. If we need shared_futures I would use shared_ptr instead of InOut.

vicente.botet wrote:

>> Yet another example
>>     future<Out&> f();
>
> This is also very dangerous, the promise-fulfilling thread must guarantee
> that the reference is valid until program termination as it can't detect
> when the future dies. Even if it could detect future destruction, it would
> be a strange design. Shared_ptrs or some kind of moving should be applied
> here.

This is not more dangerous that
     Out& f();

Sharing references between threads is always very dangerous and should be avoided. The owning thread can typically not know when the other thread will access it and must hence keep it alive until the program terminates and can never alter the data again (unless it's a concurrent object).

vicente.botet wrote:

We know how dangerous it is and we use every time. This reference point
usualy to a member object, and the object can be deleted.

The single threaded case is a lot less dangerous.

As a side note, I think return-by-reference is an almost deprecated programming style. Code which depend on boost can use auto_ptr, shared_ptr, variant, optional and tuples to easily return data, unless performance is _really_ critical. R-value references will remove the expensive copying for movable types too.

Those are my thoughts on the matter.

Johan

[Vicente Botet Escriba]

----- Original Message -----
From: "Anthony Williams" <anthony_w.geo@...>
To: <boost@...>
Sent: Tuesday, May 13, 2008 10:03 PM
Subject: Re: [boost] Review Request: future library : what does
futureofreferences exactly means?

> "vicente.botet" <vicente.botet@...> writes:
>
>> Well let me come back to my initial example. Supose that I had
>>     Result f(InOut& ref);
>>     // ...
>>         {
>>             InOut v=0;
>>             // ...
>>             v = 13;
>>             Result r = f(v);
>>             // ...     use r or v;
>>             g(r, v);
>>             v = 15;
>>         }
>>
>> Do you mean that the following works with your proposal?
>>
>>     unique_future<Result> f(shared_future<InOut>& ref);
>>     // ...
>>         {
>>             shared_future<InOut> v; v->get()=0;
>>             // ...
>>             v->get() = 13;
>>             unique_future<Result> r = f(v);
>>             // ... use r or v;
>>             g(r->get(), v->get());
>>             v->get() = 15;
>>         }
>
> Not quite. You can't set a value on a future by writing to the result of a
> call to get() - you need a promise or a packaged task for that. However,
> you
> can write:
>
> void foo()
> {
>    promise<InOut> p;
>    shared_future<InOut> v=p.get_future();
>    p.set_value(13);
>
>    unique_future<Result> r=f(v);
>
>    // v.get() may have changed if f took v by reference
>    g(r.get(),v.get());
> }
>

Sorry, this is exactly the behaviour I wanted to refactor.

Thanks
Vicente


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Anthony Williams-3]

Johan Torp <johan.torp@...> writes:

> Anthony Williams-3 wrote:
>>
>> If the thread "crashes", you've got a serious bug: all bets are off. It
>> doesn't matter whether that's the same thread that's performing another
>> task
>> or not.
>>
>
> I agree that something is seriously wrong and that we perhaps don't need to
> handle things gracefully. But if the threading API allows us to detect
> "crashing" threads somehow, we could avoid spreading a thread-local problem
> to the whole process. The client thread could even be notified with a
> thread_crash exception set in the future. I'm haven't had time to read up on
> what possibilities the C++0x threading API will supply here, but I suppose
> you know. Maybe there isn't even a notion of a thread crashing without
> crashing the process.

No, there isn't. A thread "crashes" as a result of undefined behaviour, in
which case the behaviour of the entire application is undefined.

> At the very least, I see a value in not behaving worst than if the
> associated client thread would have spawned it's own worker thread. That is:
>   std::launch_in_pool(&crashing_function);
> should not behave worse than
>   std::thread t(&crashing_function);

It doesn't: it crashes the application in both cases ;-)

> Anthony Williams-3 wrote:
>>
>>> B might be useful. It can't detect waiting by periodic is_ready-polling -
>>> which with todays interface is needed to wait for more than one future.
>>
>> I would use timed_wait() calls when waiting for more than one future:
>> doing a
>> busy-wait with is_ready just consumes CPU time which would be better spent
>> actually doing the work that will set the futures to ready, and timed_wait
>> is
>> more expressive than sleep:
>>
>> void wait_for_either(jss::unique_future<int>& a,jss::unique_future<int>&
>> b)
>> {
>>     if(a.is_ready() || b.is_ready())
>>     {
>>         return true;
>>     }
>>     while(!a.timed_wait(boost::posix_time::milliseconds(1)) &&
>>           !b.timed_wait(boost::posix_time::milliseconds(1)));
>> }
>>
>
> It could as well have been implemented by:
>
>     while (!a.is_ready() || !b.is_ready())
>     {
>         a.timed_wait(boost::posix_time::milliseconds(1));
>     }

This has a redundant check on a.is_ready(), and as you mention below, it
doesn't cause a wait callback on "b" to be called. Also, this is biased
towards waiting on a. By alternating the timed wait you're sharing the load.

> You can't detect that b is needed here. I would not implement dynamic wait
> by timed_waiting on every single future, one at a time. Rather i would have
> done something like:
>
> void wait_for_any(const vector<future<void>>& futures)
> {
>   while (1)
>   {
>     for (...f in futures...) if (f.is_ready()) return;
>     sleep(10ms);
>   }
> }

If it was a large list, I wouldn't /just/ do a timed_wait on each future in
turn. The sleep here lacks expression of intent, though. I would write a
dynamic wait_for_any like so:

void wait_for_any(const vector<future<void>>& futures)
{
  while (1)
  {
    for (...f in futures...)
    {
        for (...g in futures...) if (g.is_ready()) return;
        if(f.timed_wait(1ms)) return;
    }
  }
}

That way, you're never just sleeping: you're always waiting on a future. Also,
you share the wait around, but you still check each one every time you wake.

>
> Anthony Williams-3 wrote:
>>
>>> - Let the thread-pool be a predictable FIFO queue. Trust client code to
>>> do
>>> the scheduling and not submit too many tasks at the same time.
>>
>> That's not appropriate for situations where a task on the pool can submit
>> more
>> tasks to the same pool, as in my quicksort example.
>>
>
> Ah - I knew I missed something. Agreed, child tasks should be prioritized.
> But that mechanism could be kept internal in the thread pool.

The pool can only do that if the pool knows you're waiting on a child task.

> Anthony Williams-3 wrote:
>>
>> My wait_for_either above could easily be extended to a dynamic set, and to
>> do
>> wait_for_both instead.
>>
>
> Still you don't really wait for more than one future at a time. Both yours
> and mine suggestion above are depressingly inefficient if you were to wait
> on 1000s of futures simultaneously. I don't know if this will be a real use
> case or not. If the many core prediction comes true and we get 1000s of
> cores, it might very well be.  

You're right: if there's lots of futures, then you can consume considerable
CPU time polling them, even if you then wait/sleep. What is needed is a
mechanism to say "this future belongs to this set" and "wait for one of the
set". Currently, I can imagine doing this by spawning a separate thread for
each future in the set, which then does a blocking wait on its future and
notifies a "combined" value when done. The other threads in the set can then
be interrupted when one is done. Of course, you need /really/ lightweight
threads to make that worthwhile, but I expect threads to become cheaper as the
number of cores increases. Alternatively, you could do it with a
completion-callback, but I'm not entirely comfortable with that.

>
> Anthony Williams-3 wrote:
>>
>>> My 5 cents is still that 2 x time_limited_wait is clear and readable
>>> enough
>>> but it's no strong opinion. For good or bad you are forcing users to
>>> supply
>>> their intent twice - by both argument type and method name. Is this a
>>> general strategy for the standard library?
>>
>> This is an important strategy with condition variables, and it is probably
>> sensible to do the same elsewhere in the standard library for consistency.
>>
>
> I understand your point, even though I'm not sure it's the best strategy.
> Rather than arguing with more experienced people, I'll adopt whatever public
> code I write to this.

Currently the WP uses overloads of timed_wait for condition variables. I
expect we'll see whether the committee prefers that or wait_for/wait_until
after the meeting in June.

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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Vicente Botet Escriba]

----- Original Message -----
From: "Anthony Williams" <anthony_w.geo@...>
To: <boost@...>
Sent: Sunday, May 11, 2008 11:53 AM
Subject: Re: [boost] Review Request: future library (N2561/Williams version)

> * Finally, I've added a set_wait_callback() function to both promise and
>  packaged_task. This allows for lazy-futures which don't actually run the
>  operation to generate the value until the value is needed: no threading
>  required. It also allows for a thread pool to do task stealing if a pool
>  thread waits for a task that's not started yet. The callbacks must be
>  thread-safe as they are potentially called from many waiting threads
>  simultaneously. At the moment, I've specified the callbacks as taking a
>  non-const reference to the promise or packaged_task for which they are
> set,
>  but I'm open to just making them be any callable function, and leaving it
> up
>  to the user to call bind() to do that.

Hi,

Why you don't allow multiple callbacks? I suposse that this is related to
the implementation of do_callback

void do_callback(boost::unique_lock<boost::mutex>& lock)
{
    if(callback && !done)
    {
        boost::function<void()> local_callback=callback;
        relocker relock(lock);
        local_callback();
    }
}

You need to call all the callbacks with the mutex unlock, and you need to
protect from other concurrent set_wait_callback. So you will need to copy
the list of callbacks before unlock.

Is this correct?

Anyway, IMO, having a single call back could motivate a user wrapper which
offer "bugy" multiple callbacks.

Vicente


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Anthony Williams-3]

"vicente.botet" <vicente.botet@...> writes:

> Why you don't allow multiple callbacks? I suposse that this is related to
> the implementation of do_callback
>
> void do_callback(boost::unique_lock<boost::mutex>& lock)
> {
>     if(callback && !done)
>     {
>         boost::function<void()> local_callback=callback;
>         relocker relock(lock);
>         local_callback();
>     }
> }
>
> You need to call all the callbacks with the mutex unlock, and you need to
> protect from other concurrent set_wait_callback. So you will need to copy
> the list of callbacks before unlock.
>
> Is this correct?

That is correct with respect to the implementation, but I don't actually see
the need for multiple callbacks. The callbacks are set as part of the promise
or packaged_task. I can't imagine why that would require multiple
callbacks. In any case, the user can provide that facility on their own if
required.

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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Vicente Botet Escriba]

----- Original Message -----
From: "Anthony Williams" <anthony_w.geo@...>
To: <boost@...>
Sent: Wednesday, May 14, 2008 10:55 AM
Subject: Re: [boost] Review Request: future library (N2561/Williams version)

> "vicente.botet" <vicente.botet@...> writes:
>
>> Why you don't allow multiple callbacks? I suposse that this is related to
>> the implementation of do_callback
>>
>> void do_callback(boost::unique_lock<boost::mutex>& lock)
>> {
>>     if(callback && !done)
>>     {
>>         boost::function<void()> local_callback=callback;
>>         relocker relock(lock);
>>         local_callback();
>>     }
>> }
>>
>> You need to call all the callbacks with the mutex unlock, and you need to
>> protect from other concurrent set_wait_callback. So you will need to copy
>> the list of callbacks before unlock.
>>
>> Is this correct?
>
> That is correct with respect to the implementation,

BTW, Braddock implementation do a move of the list of callbacks before doing
the callbacks. What do you thing about this approach?

> but I don't actually see
> the need for multiple callbacks. The callbacks are set as part of the
> promise
> or packaged_task. I can't imagine why that would require multiple
> callbacks. In any case, the user can provide that facility on their own if
> required.
>

What about the guarded schedule of Braddock?
    template future<T>
    schedule(boost::function<T (void)> const& fn, future<void> guard =
future<void>()) {
         promise<T> prom; // create promise
         future_wrapper<T> wrap(fn,prom);
         guard.add_callback(boost::bind(&JobQueue3::queueWrapped<T>, this,
wrap, prom));
         return future<T>(prom); // return a future created from the promise
    }

Several task can be scheduled guarded by the same future.

Vicente


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Anthony Williams-3]

"vicente.botet" <vicente.botet@...> writes:

> ----- Original Message -----
> From: "Anthony Williams" <anthony_w.geo@...>
> To: <boost@...>
> Sent: Wednesday, May 14, 2008 10:55 AM
> Subject: Re: [boost] Review Request: future library (N2561/Williams version)
>
>
>> "vicente.botet" <vicente.botet@...> writes:
>>
>>> Why you don't allow multiple callbacks? I suposse that this is related to
>>> the implementation of do_callback
>>>
>>> void do_callback(boost::unique_lock<boost::mutex>& lock)
>>> {
>>>     if(callback && !done)
>>>     {
>>>         boost::function<void()> local_callback=callback;
>>>         relocker relock(lock);
>>>         local_callback();
>>>     }
>>> }
>>>
>>> You need to call all the callbacks with the mutex unlock, and you need to
>>> protect from other concurrent set_wait_callback. So you will need to copy
>>> the list of callbacks before unlock.
>>>
>>> Is this correct?
>>
>> That is correct with respect to the implementation,
>
> BTW, Braddock implementation do a move of the list of callbacks before doing
> the callbacks. What do you thing about this approach?

That's an interesting idea: rather than calling the callback every time some
thread waits on a future, it's only called on the first call. You could make
the callback clear itself when it was invoked if you want that behaviour, as
the promise or packaged_task is passed in to the callback.

>> but I don't actually see
>> the need for multiple callbacks. The callbacks are set as part of the
>> promise
>> or packaged_task. I can't imagine why that would require multiple
>> callbacks. In any case, the user can provide that facility on their own if
>> required.
>>
>
> What about the guarded schedule of Braddock?
>     template future<T>
>     schedule(boost::function<T (void)> const& fn, future<void> guard =
> future<void>()) {
>          promise<T> prom; // create promise
>          future_wrapper<T> wrap(fn,prom);
>          guard.add_callback(boost::bind(&JobQueue3::queueWrapped<T>, this,
> wrap, prom));
>          return future<T>(prom); // return a future created from the promise
>     }
>
> Several task can be scheduled guarded by the same future.

That's a completion callback, not a wait callback. My proposal doesn't offer
completion callbacks.

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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Vicente Botet Escriba]

----- Original Message -----
From: "Anthony Williams" <anthony_w.geo@...>
To: <boost@...>
Sent: Wednesday, May 14, 2008 12:15 PM
Subject: Re: [boost] Review Request: future library (N2561/Williams version)

> "vicente.botet" <vicente.botet@...> writes:
>
>> ----- Original Message -----
>> From: "Anthony Williams" <anthony_w.geo@...>
>> To: <boost@...>
>> Sent: Wednesday, May 14, 2008 10:55 AM
>> Subject: Re: [boost] Review Request: future library (N2561/Williams
>> version)
>>
>>
>>> "vicente.botet" <vicente.botet@...> writes:
>>>
>>>> Why you don't allow multiple callbacks? I suposse that this is related
>>>> to
>>>> the implementation of do_callback
>>>>
>>>> void do_callback(boost::unique_lock<boost::mutex>& lock)
>>>> {
>>>>     if(callback && !done)
>>>>     {
>>>>         boost::function<void()> local_callback=callback;
>>>>         relocker relock(lock);
>>>>         local_callback();
>>>>     }
>>>> }
>>>>
>>>> You need to call all the callbacks with the mutex unlock, and you need
>>>> to
>>>> protect from other concurrent set_wait_callback. So you will need to
>>>> copy
>>>> the list of callbacks before unlock.
>>>>
>>>> Is this correct?
>>>
>>> That is correct with respect to the implementation,
>>
>> BTW, Braddock implementation do a move of the list of callbacks before
>> doing
>> the callbacks. What do you thing about this approach?
>
> That's an interesting idea: rather than calling the callback every time
> some
> thread waits on a future, it's only called on the first call. You could
> make
> the callback clear itself when it was invoked if you want that behaviour,
> as
> the promise or packaged_task is passed in to the callback.
>
>>> but I don't actually see
>>> the need for multiple callbacks. The callbacks are set as part of the
>>> promise
>>> or packaged_task. I can't imagine why that would require multiple
>>> callbacks. In any case, the user can provide that facility on their own
>>> if
>>> required.
>>>
>>
>> What about the guarded schedule of Braddock?
>>     template future<T>
>>     schedule(boost::function<T (void)> const& fn, future<void> guard =
>> future<void>()) {
>>          promise<T> prom; // create promise
>>          future_wrapper<T> wrap(fn,prom);
>>          guard.add_callback(boost::bind(&JobQueue3::queueWrapped<T>,
>> this,
>> wrap, prom));
>>          return future<T>(prom); // return a future created from the
>> promise
>>     }
>>
>> Several task can be scheduled guarded by the same future.
>
> That's a completion callback, not a wait callback. My proposal doesn't
> offer
> completion callbacks.
>

Why you don't want to provide completion callbacks? Have you another
proposal for completion callbacks?

Maybe you could open the interface and return the last callback setting.
This will result in a chain of responsabilities and the client must be aware
of that with thow potential problems: growing stack and clients forgetting
its responsabilities.

template<typename F,typename U>boost::function0<void>
boost::function0<void> set_wait_callback(F f,U* u)
{
    boost::function0<void> cb = callback
    callback=boost::bind(f,boost::ref(*u));
    return cb;
}

In this case it is also  needed to reset the callback, other wise the
void do_callback(boost::unique_lock<boost::mutex>& lock)
{
    if(callback && !done)
    {
        boost::function<void()> local_callback=callback;
        callback.clear();
        relocker relock(lock);
        local_callback();
    }
}

Vicente


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Anthony Williams-3]

"vicente.botet" <vicente.botet@...> writes:

> Why you don't want to provide completion callbacks? Have you another
> proposal for completion callbacks?

I don't like them because you're chaining work onto the thread that sets the
future value, and that strikes me as dangerous.

> Maybe you could open the interface and return the last callback setting.
> This will result in a chain of responsabilities and the client must be aware
> of that with thow potential problems: growing stack and clients forgetting
> its responsabilities.

I really don't see the need for multiple wait callbacks.

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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Johan Torp]

Anthony Williams-3 wrote:

> Maybe there isn't even a notion of a thread crashing without
> crashing the process.

No, there isn't. A thread "crashes" as a result of undefined behaviour, in
which case the behaviour of the entire application is undefined.

I thought Windows' SetUnhandledExceptionFilter could handle this but I was wrong.

Anthony Williams-3 wrote:

> At the very least, I see a value in not behaving worst than if the
> associated client thread would have spawned it's own worker thread. That is:
>   std::launch_in_pool(&crashing_function);
> should not behave worse than
>   std::thread t(&crashing_function);

It doesn't: it crashes the application in both cases ;-)

You're right. Deadlocks will however be able to "spread" in this non-obvious way.
Lets say thread C1 adds task T1 to the pool which is processed by worker thread W1. C1 then blocks until T1 is finished. When T1 waits on a future, it starts working on job T2 which deadlocks. This deadlock now spreads to the uninvolved thread C1 too.

Don't now how much of a problem this is though - effective thread re-use might be worth more than this unexpected behaviour.

Anthony Williams-3 wrote:

If it was a large list, I wouldn't /just/ do a timed_wait on each future in
turn. The sleep here lacks expression of intent, though. I would write a
dynamic wait_for_any like so:

void wait_for_any(const vector<future<void>>& futures)
{
  while (1)
  {
    for (...f in futures...)
    {
        for (...g in futures...) if (g.is_ready()) return;
        if(f.timed_wait(1ms)) return;
    }
  }
}

That way, you're never just sleeping: you're always waiting on a future. Also,
you share the wait around, but you still check each one every time you wake.

Maybe you would, but I doubt most users would. I wouldn't expect that waiting on a future expresses interest in the value.

Anthony Williams-3 wrote:

You're right: if there's lots of futures, then you can consume considerable
CPU time polling them, even if you then wait/sleep. What is needed is a
mechanism to say "this future belongs to this set" and "wait for one of the
set".

Exactly my thoughts. Wait for all would probably be needed too. And to build composites, you need to be able to add both futures and these future-sets to a future-set. Might be one class for wait_for_any and another one for wait_for_all.

Anthony Williams-3 wrote:

Currently, I can imagine doing this by spawning a separate thread for
each future in the set, which then does a blocking wait on its future and
notifies a "combined" value when done. The other threads in the set can then
be interrupted when one is done. Of course, you need /really/ lightweight
threads to make that worthwhile, but I expect threads to become cheaper as the
number of cores increases.

Starting a thread to wait for a future doesn't seem very suitable to me. Imagine 10% of the core threads each waiting on (combinatorial) results from the  remaining 90%. Also, waiting on many futures is probably applicable even on single core processors. For instance if you have 100s of pending requests to different types of distributed services, you could model each request with a future and be interested in the first response which arrives. Windows threads today aren't particularily light-weight.

This might mean that condition_variable isn't a suitable abstraction to build futures on :( At least not the way it works today. But I don't think it's a good idea to change condition_variables this late. It is a pretty widespread, well working and well understood concurrent model. OTOH changing future's waiting model this late is not good either.

Anthony Williams-3 wrote:

Alternatively, you could do it with a
completion-callback, but I'm not entirely comfortable with that.

I'm not comfortable with this either, for the reasons I expressed in my response to Gaskill's propsal.

This issue is my biggest concern with the future proposal. The alternatives I've seen so far:

1. Change/alter condition variables
2. Add future-complete callback (Gaskill's proposal)
3. Implement wait_for_many with a thread per future
4. Implement wait_for_many with periodic polling with timed_waits
5. Introduce new wait_for_many mechanism (public class or implementation details)
6. Don't ever support waiting on multiple futures
7. Don't support it until next version, but make sure we don't need to alter future semantics/interface when adding it.

Alternative 7 blocks the possibility to write some exciting libraries on top of futures until a new future version is available.

Do you have further alternatives?

Johan

[Frank Mori Hess]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wednesday 14 May 2008 08:28 am, Anthony Williams wrote:

> "vicente.botet" <vicente.botet@...> writes:
> > Why you don't want to provide completion callbacks? Have you another
> > proposal for completion callbacks?
>
> I don't like them because you're chaining work onto the thread that sets
> the future value, and that strikes me as dangerous.
>
> > Maybe you could open the interface and return the last callback setting.
> > This will result in a chain of responsabilities and the client must be
> > aware of that with thow potential problems: growing stack and clients
> > forgetting its responsabilities.
>
> I really don't see the need for multiple wait callbacks.
>

To add my 2 cents: in libpoet, I allow multiple completion callbacks by
providing poet::future::connect_update() which takes a slot (from
thread_safe_signals).  A completion callback allowed me to solve the "wait
for multiple futures" problem which arose in my scheduler classes (which
contain a queue of method requests, each of which must wait for a set of
input futures before in can be executed).  The completion callback notifies a
condition variable which the scheduler thread is waiting on so it can wake up
and see if any method requests have become ready.

I chose signals/slots over a simple callback because I find simple callbacks
unbearably primitive (no multiple callbacks, no automatic connection
management).  I may be more enthusiastic about using signal/slots than most
however.  As was mentioned earlier, It is possible to tack on a signal to a
simple callback.  You could bundle each future with a signal and make the
callback just invoke the signal.  However, that requires every future to have
its own signal.  By integrating the signals/slots into the future library,
the future and all its copies can accept slots and forward them to a single
signal which is invoked when their promise is fulfilled or reneged.

If there are no completion callbacks, I regard at least the ability to wait on
an arbitrary number of futures simultaneously as essential.  Something that
provides functionality analagous to POSIX select() on a set of file
descriptors.

- --
Frank
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFIKu915vihyNWuA4URAiCjAKDUNsClBfsktvFC+cShsEWe3rA62wCdEICb
qkv7JM8XovbY+bn/cvpaUEw=
=2KGe
-----END PGP SIGNATURE-----
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Frank Mori Hess]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wednesday 14 May 2008 08:57 am, Johan Torp wrote:

> Anthony Williams-3 wrote:
> > Alternatively, you could do it with a
> > completion-callback, but I'm not entirely comfortable with that.
>
> I'm not comfortable with this either, for the reasons I expressed in my
> response to Gaskill's propsal.
>
> This issue is my biggest concern with the future proposal. The alternatives
> I've seen so far:
>
> 1. Change/alter condition variables
> 2. Add future-complete callback (Gaskill's proposal)
> 3. Implement wait_for_many with a thread per future
> 4. Implement wait_for_many with periodic polling with timed_waits
> 5. Introduce new wait_for_many mechanism (public class or implementation
> details)
> 6. Don't ever support waiting on multiple futures
> 7. Don't support it until next version, but make sure we don't need to
> alter future semantics/interface when adding it.
>
> Alternative 7 blocks the possibility to write some exciting libraries on
> top of futures until a new future version is available.

In my libpoet scheduler code I described in an earlier post today, I currently
use the a future-complete callback (signals/slots more specifically).  
Although I could make my scheduler work with wait_for_many support instead,
it would be more cumbersome and less efficient.  

First, with signals/slots I can avoid having to make the scheduler thread wake
up every time any input future of any method request in the scheduler queue
becomes ready.  Instead the individual method requests can observe their
inputs, and only generate invoke a signal in turn when all of their futures
are ready.  Then the scheduler only has to observe the method requests and
doesn't have to wake up (possibly spuriously) and check every method request
in its queue every time a single input future becomes ready.

Second, if all I can do is wait for multiple futures, then the scheduler has
to additionally maintain and keep updated a separate container with all the
input futures of the method requests currently queued.

- --
Frank
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFIK0AR5vihyNWuA4URAk/8AJ9P/AMkQhvs6bcOTxlNy3ZdQ3ddygCgyt4o
qeFQZocP8r4yd7G+sBIt310=
=lkFA
-----END PGP SIGNATURE-----
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Johan Torp]

Frank Mori Hess wrote:

First, with signals/slots I can avoid having to make the scheduler thread wake
up every time any input future of any method request in the scheduler queue
becomes ready.  Instead the individual method requests can observe their
inputs, and only generate invoke a signal in turn when all of their futures
are ready.  Then the scheduler only has to observe the method requests and
doesn't have to wake up (possibly spuriously) and check every method request
in its queue every time a single input future becomes ready.

Second, if all I can do is wait for multiple futures, then the scheduler has
to additionally maintain and keep updated a separate container with all the
input futures of the method requests currently queued.

If you have the time, please look at my proposed solution at http://www.nabble.com/-future--Early-draft-of-wait-for-multiple-futures-interface-to17242880.html. I think it solves both your problems without moving "user code execution" from future-blocking threads to promise-fulfilling ones. I'm very interested in seeing if it works well with scheduling and I think your input would be very valuable.

Johan

[Frank Mori Hess]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wednesday 14 May 2008 19:21 pm, Johan Torp wrote:

> Frank Mori Hess wrote:
> > First, with signals/slots I can avoid having to make the scheduler thread
> > wake
> > up every time any input future of any method request in the scheduler
> > queue
> > becomes ready.  Instead the individual method requests can observe their
> > inputs, and only generate invoke a signal in turn when all of their
> > futures
> > are ready.  Then the scheduler only has to observe the method requests
> > and doesn't have to wake up (possibly spuriously) and check every method
> > request
> > in its queue every time a single input future becomes ready.
> >
> > Second, if all I can do is wait for multiple futures, then the scheduler
> > has
> > to additionally maintain and keep updated a separate container with all
> > the
> > input futures of the method requests currently queued.
>
> If you have the time, please look at my proposed solution at
> http://www.nabble.com/-future--Early-draft-of-wait-for-multiple-futures-int
>erface-to17242880.html. I think it solves both your problems without moving
> "user code execution" from future-blocking threads to promise-fulfilling
> ones. I'm very interested in seeing if it works well with scheduling and I
> think your input would be very valuable.

Ah, yes it seems like some kind of composable future_switch and future_barrier
could work quite well for my use case.  Do they actually need to be classes
though?  What if they were just free functions for example

future<void> future_barrier(const future<void> &a1, const future<void>
7a2, ... , const future<void> &aN);

- --
Frank
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFILDTO5vihyNWuA4URAsOZAJ9YWXWRMuxZ5mPE34mkEGyUByHnKgCgpvCl
rIObEXk3c7/Izc3gje0s9ig=
=t+B+
-----END PGP SIGNATURE-----
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Johan Torp]

Frank Mori Hess wrote:

Ah, yes it seems like some kind of composable future_switch and future_barrier
could work quite well for my use case.  Do they actually need to be classes
though?  What if they were just free functions for example

future<void> future_barrier(const future<void> &a1, const future<void>& a2, ... , const future<void> &aN);

If we want to support dynamically adding futures to future_switch and maybe future_barrier a free function won't suffice. However I believe these functions are really useful and should be implemented on top of the proposed mechanisms.

template<class ReturnType, class Arg1, class Arg2>
future<ReturnType> barrier_compose(const future<Arg1> &a1, const future<Arg2>& a2,
                                                   const function<ReturnType(Arg1, Arg2)>& compose);

Johan

[Frank Mori Hess]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Friday 16 May 2008 05:23 am, Johan Torp wrote:

> Frank Mori Hess wrote:
> > Ah, yes it seems like some kind of composable future_switch and
> > future_barrier
> > could work quite well for my use case.  Do they actually need to be
> > classes
> > though?  What if they were just free functions for example
> >
> > future<void> future_barrier(const future<void> &a1, const future<void>&
> > a2, ... , const future<void> &aN);
>
> If we want to support dynamically adding futures to future_switch and maybe
> future_barrier a free function won't suffice.

Yes, you're right.  Especially with future_switch there should be a way to
wait on a group of futures whose number is only known at runtime.

- --
Frank
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFILZby5vihyNWuA4URAhChAJ9MTK+2ZoKBm8PVaoZZB5UqLHbeqACg5Xtm
aPId2WGfrUTXhKdZbJjTYGo=
=//EW
-----END PGP SIGNATURE-----
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Frank Mori Hess]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Friday 16 May 2008 10:15 am, Frank Mori Hess wrote:

> On Friday 16 May 2008 05:23 am, Johan Torp wrote:
> > Frank Mori Hess wrote:
> > > Ah, yes it seems like some kind of composable future_switch and
> > > future_barrier
> > > could work quite well for my use case.  Do they actually need to be
> > > classes
> > > though?  What if they were just free functions for example
> > >
> > > future<void> future_barrier(const future<void> &a1, const future<void>&
> > > a2, ... , const future<void> &aN);
> >
> > If we want to support dynamically adding futures to future_switch and
> > maybe future_barrier a free function won't suffice.
>
> Yes, you're right.  Especially with future_switch there should be a way to
> wait on a group of futures whose number is only known at runtime.

Hmm, actually what I said is wrong.  As I believe has been pointed out before
by others on this list, you could build up a arbitrary size group of futures
to wait on at runtime by taking the return value from the free future_barrier
or future_switch function and passing it to another call.  So I'm still
partial to the free function approach.  It is similar to operator|| and
operator&& in Gaskill's library except not operators, no comb<T> class or
op() function, and overloaded to accept more than 2 arguments:

future<void> future_barrier(const future<void> &a1, const future<void>&
a2, ... , const future<void> &aN);

future<void> future_switch(const future<void> &a1, const future<void>&
a2, ... , const future<void> &aN);

A naive implementation would probably be pretty inefficient when evaluating a
future that has been produced after passing through many
future_barrier/future_switch calls.  But I imagine some optimizations could
be found under the hood in the implementation to avoid unnecessarily long
chains of futures depending on each other.

These prototypes assume the future lib supports conversion of any future<T>
type to future<void>.

- --
Frank
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFILaLU5vihyNWuA4URAuuSAJ9/dlFhPWn/USbuVQCcgoKZBJVDJACfRfEH
cOeNVQBDhQy/Ifd8Bkj/Slk=
=vG5O
-----END PGP SIGNATURE-----
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Johan Torp]

Frank Mori Hess wrote:

> > If we want to support dynamically adding futures to future_switch and
> > maybe future_barrier a free function won't suffice.
>
> Yes, you're right.  Especially with future_switch there should be a way to
> wait on a group of futures whose number is only known at runtime.

Hmm, actually what I said is wrong.  As I believe has been pointed out before
by others on this list, you could build up a arbitrary size group of futures
to wait on at runtime by taking the return value from the free future_barrier
or future_switch function and passing it to another call.  So I'm still
partial to the free function approach.  It is similar to operator|| and
operator&& in Gaskill's library except not operators, no comb<T> class or
op() function, and overloaded to accept more than 2 arguments:

It is possible, what I meant by "won't suffice" is that it will be very innefficient. Imagine implementing or for 1000 futures. If you have "collection" you can just add children and get a tree with depth 2 and where the root node has 1000 childs. If you rely on free functions, say of arity 2, you get a tree depth of a 1000 and need 999 extra parent nodes which all has one leaf node and one of the parent nodes as child.

Frank Mori Hess wrote:

future<void> future_barrier(const future<void> &a1, const future<void>&
a2, ... , const future<void> &aN);

future<void> future_switch(const future<void> &a1, const future<void>&
a2, ... , const future<void> &aN);

A naive implementation would probably be pretty inefficient when evaluating a
future that has been produced after passing through many
future_barrier/future_switch calls.  But I imagine some optimizations could
be found under the hood in the implementation to avoid unnecessarily long
chains of futures depending on each other.

This would be nice and could potentially solve the inefficiency problem. You are allowed to wait for any node in a tree. The main difficulty is figuring out which nodes only exists in the tree and which who are visible to the outside world. The nodes who only exist in the tree can be re-arranged into a compact tree. Maybe we can use unique_future to guarantee this. I.e. the combination functions always return unique_futures and if we get these as in-parameters, we can safely re-arrenge the tree.


Johan

[Frank Mori Hess-2]

On Saturday 17 May 2008 07:32, Johan Torp wrote:

> Frank Mori Hess wrote:
> > future<void> future_barrier(const future<void> &a1, const
> > future<void>& a2, ... , const future<void> &aN);
> >
> > future<void> future_switch(const future<void> &a1, const future<void>&
> > a2, ... , const future<void> &aN);
> >
> > A naive implementation would probably be pretty inefficient when
> > evaluating a
> > future that has been produced after passing through many
> > future_barrier/future_switch calls.  But I imagine some optimizations
> > could
> > be found under the hood in the implementation to avoid unnecessarily
> > long chains of futures depending on each other.
>
> This would be nice and could potentially solve the inefficiency problem.
> You are allowed to wait for any node in a tree. The main difficulty is
> figuring out which nodes only exists in the tree and which who are
> visible to the outside world. The nodes who only exist in the tree can
> be re-arranged into a compact tree. Maybe we can use unique_future to
> guarantee this. I.e. the combination functions always return
> unique_futures and if we get these as in-parameters, we can safely
> re-arrenge the tree.

Returning a unique_future seems okay.  To get around an exponential blowup
in number of overloads when overloading each parameter for
shared_future/unique_future you'd need some kind of implicitly convertible
wrapper class.  You could have future_barrier/future_switch accept and
return a wrapper like the comb<T> from Braddock's library.  The comb<T>
could keep carry any state information which is needed to optimize the
tree.

Another solution would be to just provide another overload that accepts
iterators to a user-supplied container of future<void>s.

--
Frank



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost