[future] Early draft of wait for multiple futures interface

[Johan Torp]

We've been discussing the need to implement a mechanism to wait for multiple futures in a separate thread: www.nabble.com/Review-Request%3A-future-library-%28Gaskill-version%29-to16600402.html

I've come up with some interfaces which I find intuitive and useful. I've never implemented thread waiting, so please let me know if you think something like this is viable.

------------------------------ Proposal  ------------------------------
A future can be constructed and thereafter wait on four different "future conditions"
 * a promise
 * a future_switch
 * a future_barrier
 * another future

Each condition has a specified return type and the futures you create from it must match this type. They all have the same possible states - isn't ready, has value or an expression. I have left these and alot of other details out of the interface below for conciseness.


------------------------------  Interface drafts  ------------------------------

/// Future condition which is ready when any of the added conditions is ready. Has an arbitrary return-type
template<class ReturnType>
class future_switch
{
public:

  /// Direct return
  template<class FutureConditionWithMatchingReturnType>
  void add_case(FutureConditionWithMatchingReturnType f);

  /// Possibility to perform custom functor, bind state, perform some logic etc before fulfilling it's condition
  template<class FutureCondition, class FutureTypeToReturnTypeFunctor>
  void add_case(FutureCondition f, FutureTypeToReturnTypeFunctor case);

  /// Only valid in is_ready state. Removes last fulfilled futurecondition and enables new futures to be  
  /// constructed. Existing futures will have copied the value or exception already and will still work.
  void remove_ready_case();

  bool empty() const;
};


/// Future condition which is ready when all added futures are.
/// This interface is less promising and has some flaws. Maybe you can get inspired by it though.
template<class ReturnType>
class future_barrier
{
public:
  future_barrier(const function<ReturnType()>& onReady);

  template<class FutureCondition>
  void add_condition(const future<FutureType>& f);
};

------------------------------  Example usage  ------------------------------

template<class T>
future_switch<T> operator||(const future<T>& lhs, const future<T>& rhs)
{
  future_switch<T> sw;
  sw.add_case(lhs);
  sw.add_case(rhs);
  return sw;
}

template<class T>
T and_impl(const future<T>& lhs, const future<T>& rhs)
{
  return lhs.get() && rhs.get();
}

template<class T>
future_barrier<T> operator&&(const future<T>& lhs, const future<T>& rhs)
{
  // Rather large runtime insecurity, we might forget to add lhs and rhs as conditions to the barrier
  future_barrier b(bind(&and_impl, lhs, rhs));
  b.add_condition(lhs);
  b.add_condition(rhs);
  return b;
}


// This is an experimental use case for using switch as a dynamic set of future conditions
// It handles three future responses and calls the three functions on the next lines

bool handle_response_a(ResponseA r);
bool handle_response_b(ResponseB r);
bool handle_response_c(ResponseC r);

void handle_pending_requests(const future<ResponseA>& a,
                                         const future<ResponseB >& b,
                                         const future<ResponseC >& c)
{
  future_switch<void> sw;

  sw.add_case(a, &handle_repsonse_a);
  sw.add_case(b, &handle_repsonse_b);
  sw.add_case(c, &handle_repsonse_c);
 
  bool all_ok = true;
  while (!sw.empty())
  {
     // Will automatically remove ok:ed futures from sw
     future<bool> next_response_was_ok(sw);
     bool all_ok = all_ok && next_response_was_ok.get();
     sw.remove_ready_case();
  }
 
  return all_ok;
}
------------------------------  Some comments  ------------------------------

There is a lot to improve here. I'd appreciate it if we could focus on determining whether this is a viable solution and the way we want to go before diving into details.

These abstractions has the following property:
A Users can compose conditions and poll them without the need of waiting.
B We do not need to spawn extra threads for waiting - we only wait on the "outmost" future
C Threads needn't awake and poll readiness - assuming the and/or logic is handled by waitingcode.
D No "user logic" from the future-blocking threads propagate to the promise-fulfilling thread.
E It's possible to implement efficient laziness by keeping readiness/waiting logic internal in the future library

"wait for all" can be implemented without adding future_barrier, by simply calling wait() on all futures. We lose property A and E for "wait for all" if we do it this way. The blocking thread will awake unnecessarily many times.

Property C means promise-fullfilling threads need to do some basic and/or logic. I think this can be implemented in a safe and efficient manner, O(log(N)) for barrier/all and O(1) for switch/any. I also think it is much preferable to waking and switching to future-blocking threads which re-check readiness conditions. Note property D.


Whatever mechanism we choose I think it's desirable to be able to easily "lift" existing functions to futures;
  R foo(A1 a1, A2 a2, A3 a3)
should be easily rewritable as;
  future<R> foo(future<A1> a1, A2 a2, future<A3> a3) // Some parameters need not be lifted


Johan

[Johan Torp]

After thinking more carefully on the problem I've realized it is implementable using condition variables. Here is a revised proposal, which - for now - excludes barriers.

----------------------------   Proposal  ----------------------------  

Add class future_expression that basically is a function which depend on futures values.
- A typed evaluation function (some work) is associated with each future dependency
--- This evaluation can result in that the future_expressions becomes ready
- A future dependency is a parent child relationship. This forms a graph where "promise-futures" are leafs.
--- You can wait() on any future in the graph
- When a future is completed it tells it's parents they need to re-evaluate via a future-complete callback
--- The future_expression that needs re-evaluation will:
--- 1. Schedule the associated evaluation to be run on the client thread on next wait or is_ready is called
--- 2. Notifies it's condition in case the client thread was waiting on this particular node
--- 3. Signals it's parents they too need to re-evaluate  
------ This way, the notifications propagate upwards to the root future
------ Some future_expression might be scheduled for re-evaluation even though
- When a future expression becomes ready it drops it's shared ownership to all depending childs
--- They are no longer needed and can die
--- This is done as a part of the pending evaluations on the client thread
- For now this is not a concurrent object, neither are the futures formed from it
--- All evaluation code can thus be single threaded
--- We can change this so that the work of evaluating a future is done by the first thread waiting on it.
     
Note:
- The callback is ONLY usable by future_exprs. - No user code can be executed by promise fulfilling code
- Other abstractions build on future_expressions rather than the dangerous complete-callback


----------------------------  Part of interface  ----------------------------

template<class T>
struct future_result
{
  T running_result_;
  bool value_is_final_;
  optional<exception> exception_;
  ...
};

///  A representation of a function which depends on futures.
///
template <class T>
class future_expression
{
  /// Default value if no dependencies are added
  future_expression(T starting_value);

  /// Add a future alongside with an evaluation function which will be called lazily by waiting threads
  template<class U>
  void add_dependency<U> (shared_future<U> f,
                                      function<void(U future_value, future_result<T>& result_setter)> on_ready);

  /// Perform pending evaluations. If none sets an exception or result wait on the internal condition
  void wait();

  /// If not ready, perform pending evaluations. If none sets an exception or result, return false
  bool is_ready();
};  

----------------------------  Example code  ----------------------------

void set_if_true(bool b, result& result_setter)
{
  if (b)
  {
    result_setter.running_value_ = true;
    result_setter.value_is_final_ = true;
  }
}

template<class T>
future<bool> operator||(future<bool> lhs, future<bool> rhs)
{
  future_expression<R> exp(false);
  exp.add_dependency(a1, &set_if_true);
  exp.add_dependency(a2, &set_if_true);
  return future<R>(exp);
}

template<class T>
void running_add(T value, result& result_setter)
{
  result_setter.running_value_ += value;
}

template<class T>
future<T> sum(vector<future<T>> futures)
{
  future_expression<T> exp(value_initialized<T>());

  for f in futures
     exp.add_dependency(f, &running_add);

  return future<T>(exp);
}

----------------------------  Conclusions  ----------------------------
 
This mechanism would solve all the issues we've found. Most importantly it allows making composite futures while prohibiting execution of user code while fulfilling promises.

Unfortunately, I feel it might be a little cumbersome to use. Also, since we need wait_for_many support it needs to get accepted alongside with the first version of the future library. I was hoping this version could be very lightweight.
 
What do you think? Any quick thoughts?

Johan

[Anthony Williams-4]

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

> After thinking more carefully on the problem I've realized it is
> implementable using condition variables. Here is a revised proposal, which -
> for now - excludes barriers.

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.

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-4 wrote:

> After thinking more carefully on the problem I've realized it is
> implementable using condition variables. Here is a revised proposal, which -
> for now - excludes barriers.

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.

I agree we do not need this complex functionality in most cases. I too want to find a minimal interface which we can implement and get accepted into boost first, then we can add rich functionality - as Gaskill's proposal - on top of it. I hope we can find something much simpler than what I proposed without exposing the "completed callback". I fear that it might be difficult though.

I don't think your proposed interface is powerful enough to implement composed futures, but I might be wrong. For instance, how would you implement future operators with it?

future<bool> operator||(future<bool> lhs, future<bool> rhs);

Johan

[Anthony Williams-4]

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

> Anthony Williams-4 wrote:
>>
>>> After thinking more carefully on the problem I've realized it is
>>> implementable using condition variables. Here is a revised proposal,
>>> which -
>>> for now - excludes barriers.
>>
>> 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.
>>
>
> I agree we do not need this complex functionality in most cases. I too want
> to find a minimal interface which we can implement and get accepted into
> boost first, then we can add rich functionality - as Gaskill's proposal - on
> top of it. I hope we can find something much simpler than what I proposed
> without exposing the "completed callback". I fear that it might be difficult
> though.
>
> I don't think your proposed interface is powerful enough to implement
> composed futures, but I might be wrong. For instance, how would you
> implement future operators with it?
>
> future<bool> operator||(future<bool> lhs, future<bool> rhs);

Using wait callbacks:

    namespace detail
    {
        template<typename R>
        class future_or
        {
            boost::shared_ptr<packaged_task<R> > task;
            shared_future<R> lhs;
            shared_future<R> rhs;
           
        public:
            future_or(boost::shared_ptr<packaged_task<R> > const& task_,
                      shared_future<R> const& lhs_,
                      shared_future<R> const& rhs_):
                task(task_),lhs(lhs_),rhs(rhs_)
            {}
           
            R operator()()
            {
                unsigned const index=wait_for_any(lhs,rhs);
               
                return index?rhs.get():lhs.get();
            }

            static void run(jss::packaged_task<int>& pt)
            {
                try
                {
                    pt();
                }
                catch(task_already_started&)
                {
                }
            }
           
        };
       
    }
   

    template<typename R>
    unique_future<R> operator||(shared_future<R> const& lhs,shared_future<R> const& rhs)
    {
        boost::shared_ptr<packaged_task<R> > task(new packaged_task<R>);
       
        *task=packaged_task<R>(detail::future_or<R>(task,lhs,rhs));

        task->set_wait_callback(detail::future_or<R>::run);
       
        return task->get_future();
    }

Alternatively, you could have future_or spawn a thread to run the task
rather than do it lazily as a wait callback.

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-4 wrote:

Alternatively, you could have future_or spawn a thread to run the task
rather than do it lazily as a wait callback.

I don't think spawning a thread is acceptable.

1. Starting a new thread is expensive. Thread-pools might help here but they don't exist yet.
2. Context switching is expensive. Typically, the evaluation work is real small. This approach requires an additional context switch compared to if the future-listener performed the evaluation. It might also reduce the performance of a thread-pool if composite futures are frequently evaluated.
3. Composed futures might need to access data belonging to the future-listener in it's evaluation. If the evaluation is performed by a single future-listener, it can use const references. Now such the data needs to be copied or protected by mutexes.
4. Nested composed futures might get a context switch at every depth level.

I wouldn't be surprised if the context switching would rule out futures from libraries such as asio or poet. That would be a real shame. Frank or somebody with asio insight, what do you think?

I'm also not convinced that we want a wait callback. I'm not sure "thread stack re-use" is such a good idea. As I pointed out before, it can spread dead locks to client threads in very unexpected ways, for instance by violating lock acquistion orderings. Library support for fibers or even language support for co-routines are cleaner alternatives, I suppose they're quite difficult to add though.

Johan

[Johan Torp]

Anthony Williams-4 wrote:

> I don't think your proposed interface is powerful enough to implement
> composed futures, but I might be wrong. For instance, how would you
> implement future operators with it?
>
> future<bool> operator||(future<bool> lhs, future<bool> rhs);

Using wait callbacks:

is_ready doesn't trigger the callback, so this won't work.

OTOH, I think is_ready should trigger the callback, even for the "run extra work in wait()" thread pool use case.

Johan

Johan

[Peter Dimov-5]

Johan Torp:

> is_ready doesn't trigger the callback, so this won't work.
>
> OTOH, I think is_ready should trigger the callback, even for the "run
> extra
> work in wait()" thread pool use case.

ready() should trigger a separate "ready callback", since its semantics are
not the same.

(f1 || f2).ready :- f1.ready || f2.ready
(f1 || f2).wait :- wait_for_any(f1, f2)

(Ignoring the problem in which f1 completes with an exception and f2 is
still active.)

Java futures don't have this callback proliferation problem because they are
abstract.

class future
{
public:

    virtual void wait() = 0;
    virtual bool ready() = 0;
};

but we'd rather like to pass and return futures by value. :-)

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

[Anthony Williams-4]

"Peter Dimov" <pdimov@...> writes:

> Johan Torp:
>
>> is_ready doesn't trigger the callback, so this won't work.
>>
>> OTOH, I think is_ready should trigger the callback, even for the "run
>> extra
>> work in wait()" thread pool use case.
>
> ready() should trigger a separate "ready callback", since its semantics are
> not the same.
>
> (f1 || f2).ready :- f1.ready || f2.ready
> (f1 || f2).wait :- wait_for_any(f1, f2)

Interesting thought. An is_ready() query is certainly not a blocking
wait, so shouldn't call the wait callback. A "ready callback" would
allow a scheduler to priotize the task without taking over the waiting
thread.

This goes along with something mentioned earlier about flagging a
future as "needed" in order to trigger lazy evaluation, or prioritize
the task in a thread pool.

> (Ignoring the problem in which f1 completes with an exception and f2 is
> still active.)

I think that's a non-problem. If f1 completes with an exception, f1 is
ready, so (f1 || f2) is ready and should propagate the exception,
regardless of the state of f2. This is the same logic as if f1
completes with a value.

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

[Anthony Williams-4]

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

> Anthony Williams-4 wrote:
>>
>>> I don't think your proposed interface is powerful enough to implement
>>> composed futures, but I might be wrong. For instance, how would you
>>> implement future operators with it?
>>>
>>> future<bool> operator||(future<bool> lhs, future<bool> rhs);
>>
>> Using wait callbacks:
>>
>
> is_ready doesn't trigger the callback, so this won't work.

That depends on what you mean by "work".

It isn't ready, so is_ready() returns false. It just happens to always
return false until you do something to make it ready.

If you wait on it, it becomes ready. If you don't wait, it
doesn't. This is the essential problem with lazy futures.

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]

Peter Dimov-5 wrote:

> is_ready doesn't trigger the callback, so this won't work.
>
> OTOH, I think is_ready should trigger the callback, even for the "run
> extra
> work in wait()" thread pool use case.

ready() should trigger a separate "ready callback", since its semantics are
not the same.

(f1 || f2).ready :- f1.ready || f2.ready
(f1 || f2).wait :- wait_for_any(f1, f2)

No, (f1 || f2).ready != f1.ready || f2.ready.
f1 can be ready and false, in which case we need to wait for f2 to become ready until the composite future is ready.

Java futures don't have this callback proliferation problem because they are
abstract.

class future
{
public:
    virtual void wait() = 0;
    virtual bool ready() = 0;
};

There are other ways of solving this too, without exposing callbacks.

but we'd rather like to pass and return futures by value. :-)

What do you mean?

Johan

[Anthony Williams-4]

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

> Peter Dimov-5 wrote:
>>
>>> is_ready doesn't trigger the callback, so this won't work.
>>>
>>> OTOH, I think is_ready should trigger the callback, even for the "run
>>> extra
>>> work in wait()" thread pool use case.
>>
>> ready() should trigger a separate "ready callback", since its semantics
>> are
>> not the same.
>>
>> (f1 || f2).ready :- f1.ready || f2.ready
>> (f1 || f2).wait :- wait_for_any(f1, f2)
>>
>
> No, (f1 || f2).ready != f1.ready || f2.ready.
> f1 can be ready and false, in which case we need to wait for f2 to become
> ready until the composite future is ready.

What does it mean for a shared_future<string> to be "ready and false"?

I view "f1 || f2" as a short-hand for a call to wait_for_any(f1,f2)
followed by either f1.get() or f2.get() depending on which was ready
first.

>> Java futures don't have this callback proliferation problem because they
>> are
>> abstract.
>>
>> class future
>> {
>> public:
>>     virtual void wait() = 0;
>>     virtual bool ready() = 0;
>> };
>>
>
> There are other ways of solving this too, without exposing callbacks.

Can you suggest some?

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-4 wrote:

> is_ready doesn't trigger the callback, so this won't work.

That depends on what you mean by "work".

It isn't ready, so is_ready() returns false. It just happens to always
return false until you do something to make it ready.

If you wait on it, it becomes ready. If you don't wait, it
doesn't. This is the essential problem with lazy futures.

That is way too strange semantics. A user would not expect having to call wait() or get() to make a future become ready. I have been thinking about not type erasing the laziness and instead providing a lazy_future class or composite future class. But I think inherent, type-erased laziness is a better idea.

Johan

[Peter Dimov-5]

Anthony Williams:
> "Peter Dimov" <pdimov@...> writes:
>
>> (Ignoring the problem in which f1 completes with an exception and f2 is
>> still active.)
>
> I think that's a non-problem. If f1 completes with an exception, f1 is
> ready, so (f1 || f2) is ready and should propagate the exception,
> regardless of the state of f2.

The "problem" (bad choice of a word on my part) is with choosing between the
behavior you outlined and the alternative, in which f1 || f2 only propagates
an exception when both f1 and f2 end with an exception. Both approaches make
sense (at least at first sight). I've chosen to implement the first in the
pseudocode because it's easier, but the implementability of the second
should probably be a concern as well.

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

[Frank Mori Hess]

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

On Friday 30 May 2008 10:44 am, Anthony Williams wrote:

> Johan Torp <johan.torp@...> writes:
> > Peter Dimov-5 wrote:
> >>> is_ready doesn't trigger the callback, so this won't work.
> >>>
> >>> OTOH, I think is_ready should trigger the callback, even for the "run
> >>> extra
> >>> work in wait()" thread pool use case.
> >>
> >> ready() should trigger a separate "ready callback", since its semantics
> >> are
> >> not the same.
> >>
> >> (f1 || f2).ready :- f1.ready || f2.ready
> >> (f1 || f2).wait :- wait_for_any(f1, f2)
> >
> > No, (f1 || f2).ready != f1.ready || f2.ready.
> > f1 can be ready and false, in which case we need to wait for f2 to become
> > ready until the composite future is ready.
>
> What does it mean for a shared_future<string> to be "ready and false"?
>
> I view "f1 || f2" as a short-hand for a call to wait_for_any(f1,f2)
> followed by either f1.get() or f2.get() depending on which was ready
> first.

I in believe Johan's operator||, the value of the returned future logically
corresponds to

f1.get() || f2.get()

That is, the operator|| is acting more consistently with the usual meaning of
operator|| for boolean values, as opposed to just being a short hand way to
express a "wait for either future" operation.  This kind of confusion is why
I don't like operator overloading :)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFIQBYv5vihyNWuA4URAkhbAKCoZK5pP48ieB+9gSN14GAIhr0UnQCferoj
6tHjtxYhwJYp8GPaimF66KE=
=KCnZ
-----END PGP SIGNATURE-----
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Johan Torp]

Anthony Williams-4 wrote:

> No, (f1 || f2).ready != f1.ready || f2.ready.
> f1 can be ready and false, in which case we need to wait for f2 to become
> ready until the composite future is ready.

What does it mean for a shared_future<string> to be "ready and false"?

I view "f1 || f2" as a short-hand for a call to wait_for_any(f1,f2)
followed by either f1.get() or f2.get() depending on which was ready
first.

I was talking about future operators. That is the composite future we got from f1 || f2, not selecting the first one which is ready. This should become ready when it has an evaluated value of true or false.

Anthony Williams-4 wrote:

>> Java futures don't have this callback proliferation problem because they
>> are
>> abstract.
>>
>> class future
>> {
>> public:
>>     virtual void wait() = 0;
>>     virtual bool ready() = 0;
>> };
>>
>
> There are other ways of solving this too, without exposing callbacks.

Can you suggest some?

I already have, all of my proposals has solved this without exposing any external callbacks. I propose adding a parent-child relationship to futures which is only exposed the wait for any/all mechanism. The promise-fullfillers does not only notify their own condition, they traverse their future's parents and notify them too.

The future-expressions can be built up with expressive templates or using some sort of future collection. Read my other posts in the review request thread and you should get an idea.

Johan

[Anthony Williams-4]

"Peter Dimov" <pdimov@...> writes:

> Anthony Williams:
>> "Peter Dimov" <pdimov@...> writes:
>>
>>> (Ignoring the problem in which f1 completes with an exception and f2 is
>>> still active.)
>>
>> I think that's a non-problem. If f1 completes with an exception, f1 is
>> ready, so (f1 || f2) is ready and should propagate the exception,
>> regardless of the state of f2.
>
> The "problem" (bad choice of a word on my part) is with choosing between the
> behavior you outlined and the alternative, in which f1 || f2 only propagates
> an exception when both f1 and f2 end with an exception. Both approaches make
> sense (at least at first sight). I've chosen to implement the first in the
> pseudocode because it's easier, but the implementability of the second
> should probably be a concern as well.

OK. Let's call it "first_value()" as it returns the first value rather
than the first ready future, and we don't have to worry about operator
semantics.

Here's an implementation, based on my operator||. Note that if the
first future ready threw an exception, it takes the value or exception
from the second. If the second had a value, that's what you want. If
it didn't, you've got two exceptions, and you can either pick one at
random or throw a new exception.

As before, if you're worried about is_ready(), you can have it spawn a
thread rather than do lazy evaluation.

namespace detail
{
    template<typename R>
    class future_first_value
    {
        boost::shared_ptr<packaged_task<R> > task;
        shared_future<R> lhs;
        shared_future<R> rhs;

    public:
        future_first_value(boost::shared_ptr<packaged_task<R> > const& task_,
                  shared_future<R> const& lhs_,
                  shared_future<R> const& rhs_):
            task(task_),lhs(lhs_),rhs(rhs_)
        {}

        R operator()()
        {
            unsigned const index=wait_for_any(lhs,rhs);

            bool const is_exceptional=
                index?rhs.has_exception():lhs.has_exception();

            if(!is_exceptional)
            {
                return index?rhs.get():lhs.get();
            }
            else
            {
                return index?lhs.get():rhs.get();
            }
        }

        static void run(jss::packaged_task<int>& pt)
        {
            try
            {
                pt();
            }
            catch(task_already_started&)
            {
            }
        }

    };

}


template<typename R>
unique_future<R> first_value(shared_future<R> const& lhs,shared_future<R> const& rhs)
{
    boost::shared_ptr<packaged_task<R> > task(new packaged_task<R>);

    *task=packaged_task<R>(detail::future_first_value<R>(task,lhs,rhs));

    task->set_wait_callback(detail::future_first_value<R>::run);

    return task->get_future();
}

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

[Frank Mori Hess]

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

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.

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

iD8DBQFIQBz75vihyNWuA4URAolQAKCmet2KPNWK0oXkz5Gd8OAR6xoc3QCg0vHf
Oh3VSBo5/gnAIk6cJRFR3is=
=oQ5s
-----END PGP SIGNATURE-----
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Anthony Williams-4]

Frank Mori Hess <frank.hess@...> 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?

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

[Anthony Williams-4]

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

> Anthony Williams-4 wrote:
>>
>>> No, (f1 || f2).ready != f1.ready || f2.ready.
>>> f1 can be ready and false, in which case we need to wait for f2 to become
>>> ready until the composite future is ready.
>>
>> What does it mean for a shared_future<string> to be "ready and false"?
>>
>> I view "f1 || f2" as a short-hand for a call to wait_for_any(f1,f2)
>> followed by either f1.get() or f2.get() depending on which was ready
>> first.
>>
>
> I was talking about future operators. That is the composite future we got
> from f1 || f2, not selecting the first one which is ready. This should
> become ready when it has an evaluated value of true or false.

Are you envisaging "f1 || f2" as a short-hand for "f1.get() ||
f2.get()" that may not need to wait for both? I see that as very
limited utility, since it only works for future<R> where R can be used
with ||.

My "f1 || f2" is a future operator that returns a composite future. It
is the future that is subject to ||, not the returned value.

>>> There are other ways of solving this too, without exposing callbacks.
>>
>> Can you suggest some?
>>
>
> I already have, all of my proposals has solved this without exposing any
> external callbacks. I propose adding a parent-child relationship to futures
> which is only exposed the wait for any/all mechanism. The
> promise-fullfillers does not only notify their own condition, they traverse
> their future's parents and notify them too.

OK. This is similar to what I've done with detail::future_waiter. I
could probably extend it to provide a full future that had the
semantics of the future_or I posted earlier. I'll have a look next week.

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