[future] Early draft of wait for multiple futures interface

[Vicente Botet Escriba]

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

> 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.

Do you mean that  future_waiter will be public and not a implementation
detail?

Vicente


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

[Johan Torp]

Anthony Williams-4 wrote:

> 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.

I see. As others has pointed out, maybe we shouldn't supply the operators because of this possible confusion.

Johan

[Johan Torp]

Anthony Williams-4 wrote:

> 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?

I think that it's a common use case to serve or ignore one ready future and then go back to waiting on the remaining ones. This would requrie O(N^2) with your interface.

Johan

[Vicente Botet Escriba]

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

> 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?
>

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


_______________________________________________
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 11:45 am, Anthony Williams wrote:
> >
> > 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?

I mean there are N method requests in my scheduler, and I want to wait until
one of them is ready.

> You have N futures to wait for. You have to somehow register that
> you're waiting for each one => you need O(N) operations.

Yes.  But the scheduler is going to repeatedly wait on the same N futures
(plus or minus one).  So as Johan already pointed out, passing iterators to a
seperate container of futures to wait_for_any() will cause the sheduler to
call wait_for_any N times and take O(N^2) to dispatch N method requests.  On
the other hand, if the container of futures and wait_for_any are integrated
into one class (future_selector), then it doesn't have to do the full
setup/tear down with each wait.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFIQDgf5vihyNWuA4URAnr9AKDFSPDXNZub0bu4C3d/cbGdDJd+VwCgpmsv
t+JA1JnP0mQPP4iv61wVjZw=
=u825
-----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 30 May 2008 09:25 am, Johan Torp wrote:

> 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've been working on the "wait for any/all" issue with libpoet's futures, and
for me it has boiled down to the question of how this function should behave:

template<typename R, typename Combiner, typename T1, typename T2, ...,
typename TN>
future<R> future_combining_barrier(Combiner combiner, future<T1> f1,
future<T2> f2, ..., future<TN> fN);

The idea of future_combining_barrier is the returned future<R> gets its value
by calling

combiner(f1.get(), f2.get(), ..., fN.get())

once all the input futures are ready.  I see 3 options:

1) The combiner is run in a future-waiting thread.
2) The combiner is run in a promise-fulfilling thread.
3) The combiner is run in its own thread.

I initially tried to implement option (1) but could not make it work
satisfactorily with my implementation (which relies on completion callbacks).  
Basically, I couldn't get the returned future<R> to work well enough.  I
wanted it to run the combiner without holding any internal library locks, and
also to run its own completion callback without undue goading from external
code.  Also, it is easy to accidentally run the combiner in a
promise-fulfilling thread if the combiner gets run by the future::ready()
query as well as when waiting.  I haven't fully explored the uses of wait
callbacks though, maybe something can be made to work.

Currently, I have implemented solution (2).  It seems to work well enough.  
Exceptions thrown in the combiner are transported to the returned future<R>.  
However, it does mean that a combiner which blocks or takes a long time can
cause the promise-fulfilling thread to stall running it.

Solution (3) has the advantage that it insulates the promise-fulfilling thread
from the possibility of being stalled by a future-waiting thread which
inserts a slow-running combiner.  However, it is a relatively heavyweight
solution, since I'd expect the typical combiner to be a fairly trivial and
quick function to execute.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFIQEu25vihyNWuA4URAlB1AKCuwXXwJD9yRcooajshi2jyzPhgKgCfXBF7
SkoHgkcRO2JQiPXEB75t1oM=
=TDTm
-----END PGP SIGNATURE-----
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

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

> ----- Original Message -----
> From: "Anthony Williams" <anthony.ajw@...>

>> 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.
>
> Do you mean that  future_waiter will be public and not a implementation
> detail?

I mean that something based on future_waiter would be public, yes.

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" <vicente.botet@...> writes:

> ----- Original Message -----
> From: "Anthony Williams" <anthony.ajw@...>
>
>> 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?
>>
>
>
> The O(N) comes from wait function.

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

Yes, but these are additive, so the result is O(N). You have N futures
to wait for, so you cannot do better than O(N): the best you can do is
a constant factor.

As Frank and Johan have posted, it's the O(N) per wait, with O(N)
waits that's the killer.

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 <frank.hess@...> writes:

> On Friday 30 May 2008 11:45 am, Anthony Williams wrote:
>> >
>> > 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?
>
> I mean there are N method requests in my scheduler, and I want to wait until
> one of them is ready.
>
>> You have N futures to wait for. You have to somehow register that
>> you're waiting for each one => you need O(N) operations.
>
> Yes.  But the scheduler is going to repeatedly wait on the same N futures
> (plus or minus one).  

Aha: it's the repeated waits that matter. For one wait it's O(N) in
all cases. If you wait again on (almost) the same set, until the set
is empty, it's an issue if you have to redo the set up, as that is
then O(N^2) in total.

That's a different use case to the one I imagined. I would call it a
"future dispatcher" and have it invoke a callback on each future as it
became ready.

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 16:24 pm, Anthony Williams wrote:
> Aha: it's the repeated waits that matter. For one wait it's O(N) in
> all cases. If you wait again on (almost) the same set, until the set
> is empty, it's an issue if you have to redo the set up, as that is
> then O(N^2) in total.
>
> That's a different use case to the one I imagined. I would call it a
> "future dispatcher" and have it invoke a callback on each future as it
> became ready.

Interesting, being able to attach a callback to such a future dispatcher would
actually make it possible for me to implement my scheduler.  I also wouldn't
need to have a future_combining_barrier which can convert a heterogeneous
group of input futures into a result future of arbitrary type.

But I think I've finally figured out how to properly run the combiner in a
waiting thread as Johan has been suggesting, so I think I'm still going to
implement future_selector.  It seems more powerful to return a future,
although the need does seem far more abstract now that I realize I don't
absolutely need the feature myself.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFIQG+o5vihyNWuA4URAu0xAJ9/SzdFOl7BiMITpMbT9W4QVV+YMQCgqZZ5
mCMjYnfdlHS0cmcBWwrZOII=
=HhXC
-----END PGP SIGNATURE-----
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Gpderetta]

On Fri, May 30, 2008 at 10:24 PM, Anthony Williams
<anthony.ajw@...> wrote:

> Frank Mori Hess <frank.hess@...> writes:
>
>> On Friday 30 May 2008 11:45 am, Anthony Williams wrote:
>>> >
>>> > 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?
>>
>> I mean there are N method requests in my scheduler, and I want to wait until
>> one of them is ready.
>>
>>> You have N futures to wait for. You have to somehow register that
>>> you're waiting for each one => you need O(N) operations.
>>
>> Yes.  But the scheduler is going to repeatedly wait on the same N futures
>> (plus or minus one).
>
> Aha: it's the repeated waits that matter. For one wait it's O(N) in
> all cases. If you wait again on (almost) the same set, until the set
> is empty, it's an issue if you have to redo the set up, as that is
> then O(N^2) in total.
>
> That's a different use case to the one I imagined. I would call it a
> "future dispatcher" and have it invoke a callback on each future as it
> became ready.
>

Hum, I think that boost already has such a dispatcher: it is called
asio::io_service ;).

IMHO futures wait sets should be used to wait for very few events. If
the number of events grows significantly, it is probably a sign that
the application would be better redesigned as an event driven state
machine. I do not think it is worth optimizing futures for large N.

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

[Johan Torp]

Frank Mori Hess 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've been working on the "wait for any/all" issue with libpoet's futures, and
for me it has boiled down to the question of how this function should behave:

template<typename R, typename Combiner, typename T1, typename T2, ...,
typename TN>
future<R> future_combining_barrier(Combiner combiner, future<T1> f1,
future<T2> f2, ..., future<TN> fN);

The idea of future_combining_barrier is the returned future<R> gets its value
by calling

combiner(f1.get(), f2.get(), ..., fN.get())

once all the input futures are ready.  I see 3 options:

1) The combiner is run in a future-waiting thread.
2) The combiner is run in a promise-fulfilling thread.
3) The combiner is run in its own thread.

I think this is a very important and difficult design decision. As I explained above (with the points numbered 1-4), I don't think option 3 is viable. An additional argument against option 3 is that you can't use futures in single threaded programs.

My arguments against option 2 is:
A. If the combiner dead-locks, this would spread to the promise-fulfiller. This would make a bug harder to pin-point.
B. Argument 3 from the 1-4 arguments above
C. You can have exceptions (such as windows se_exceptions, divide by zero, null pointer use etc ) which you want don't want to catch and set in the future, but rather would like to catch at the "stack top" of each thread started (at least the threads you explicitly start yourself). If you catch and set these exceptions and later re-throw them, you lose the stack trace inside the combiner.
D. A log typically logs which thread does what. If the promise-fulfiller executes lots of different foreign threads' code it can become more difficult to follow program execution.
E. All of the above arguments above are due to executing code which is set by another foreign thread. I believe there are lots of other effects that can happen which I haven't thought of. OTOH, the future-listener which creates the composite future has full control. If the future is shared between more threads after creation, it can be accompanied by documentation (i.e. this future will acquire this lock). We do not want this sort of coupling between the promise-listener and promise-fulfillers.

Frank Mori Hess wrote:

I initially tried to implement option (1) but could not make it work
satisfactorily with my implementation (which relies on completion callbacks).  
Basically, I couldn't get the returned future<R> to work well enough.  I
wanted it to run the combiner without holding any internal library locks, and
also to run its own completion callback without undue goading from external
code.

I really hope option 1 is implementable without holding any locks. Could explain in more detail what problems you ran into?

Frank Mori Hess wrote:

 Also, it is easy to accidentally run the combiner in a
promise-fulfilling thread if the combiner gets run by the future::ready()
query as well as when waiting.  

I'm not following you, could you elaborate?

Johan

[Frank Mori Hess-2]

On Friday 30 May 2008 17:41, Giovanni Piero Deretta wrote:
> Hum, I think that boost already has such a dispatcher: it is called
> asio::io_service ;).
>
> IMHO futures wait sets should be used to wait for very few events. If
> the number of events grows significantly, it is probably a sign that
> the application would be better redesigned as an event driven state
> machine. I do not think it is worth optimizing futures for large N.

That's essentially where I started.  To do an event driven design requires
the ability to generate an event when a future completes.  That means a
completion callback as part of the future's public interface.  A
completion callback has been resisted as too dangerous, and waits on
groups of futures offered as a safer alternative.  Therefore, I'm trying
to insist the wait functionality be sufficient to build a decent scheduler
on.


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

[Frank Mori Hess-2]

On Friday 30 May 2008 20:21, Frank Mori Hess wrote:

> On Friday 30 May 2008 17:41, Giovanni Piero Deretta wrote:
> > Hum, I think that boost already has such a dispatcher: it is called
> > asio::io_service ;).
> >
> > IMHO futures wait sets should be used to wait for very few events. If
> > the number of events grows significantly, it is probably a sign that
> > the application would be better redesigned as an event driven state
> > machine. I do not think it is worth optimizing futures for large N.
>
> That's essentially where I started.  To do an event driven design
> requires the ability to generate an event when a future completes.  That
> means a completion callback as part of the future's public interface.  A
> completion callback has been resisted as too dangerous, and waits on
> groups of futures offered as a safer alternative.  Therefore, I'm trying
> to insist the wait functionality be sufficient to build a decent
> scheduler on.

What if we specifically support asio for handling future completion events?  
That is, the future lets you register an asio::io_service along with a
completion handler, and the promise just posts the completion handler to
the io_service when it is fulfilled.  Then the completion handler won't
actually get run in the promise-fulfilling thread.  Would that be safe
enough and is it sensible (I don't know asio very well)?


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

[Frank Mori Hess-2]

On Friday 30 May 2008 18:10, Johan Torp wrote:
> Frank Mori Hess wrote:
> > once all the input futures are ready.  I see 3 options:
> >
> > 1) The combiner is run in a future-waiting thread.
> > 2) The combiner is run in a promise-fulfilling thread.
> > 3) The combiner is run in its own thread.

> I really hope option 1 is implementable without holding any locks. Could
> explain in more detail what problems you ran into?

I've got it working locally now.  The combiner and any implicit
type-conversions now only happen in future-waiting threads, and they are
run without holding locks.  I haven't committed it yet though, since it
breaks my scheduler (due to some futures not completing until a wait or a
future::ready/has_exception query is performed).  This makes my scheduler
stall, so I'll need to implement a reasonably efficient re-useable "wait
for any" like future_selector to fix it.  The changes also add some
overhead.  I haven't done any measurements, but the amount of
locking/unlocking of mutexes has definitely increased.


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

[Johan Torp]

Frank Mori Hess-2 wrote:

On Friday 30 May 2008 18:10, Johan Torp wrote:
> Frank Mori Hess wrote:
> > once all the input futures are ready.  I see 3 options:
> >
> > 1) The combiner is run in a future-waiting thread.
> > 2) The combiner is run in a promise-fulfilling thread.
> > 3) The combiner is run in its own thread.

> I really hope option 1 is implementable without holding any locks. Could
> explain in more detail what problems you ran into?

I've got it working locally now.  The combiner and any implicit
type-conversions now only happen in future-waiting threads, and they are
run without holding locks.  I haven't committed it yet though, since it
breaks my scheduler (due to some futures not completing until a wait or a
future::ready/has_exception query is performed).  This makes my scheduler
stall, so I'll need to implement a reasonably efficient re-useable "wait
for any" like future_selector to fix it.  The changes also add some
overhead.  I haven't done any measurements, but the amount of
locking/unlocking of mutexes has definitely increased.

Great, thanks for the effort. Could you post the code somewhere or mail it to me at johan [.] torp [at] gmail [.] com? I've been worried that an "ideal" future will need to hold a lot of state and becomes somewhat complicated.

I've been thinking about another problem which seems related to your scheduling problem. I'm not sure if this is due to the way I program or if I'm trying to use futures in ways they're not supposed to be, so please bear with me.

I often have some kind of top flow control mechanism for some threads which waits - without any time limit/poll - when there is nothing to do. It might be;
- A message pump
- An asio::io_service (calling run)
- A job queue
- A logical clock in reactive programming

Within this thread code is executed while processing a message, servicing some thing, executing a job or inside a logical clock tick/instant. Let's call this X's client code. Inside the client code I imagine you often will create a new pending request to some service and get a future back to wait on. Instead of waiting directly on the future and stall the entire thread, you'd typically want to get a notification from X at a later point. Let's call this future F and let's for simplicity assume there is only one of it.

This gives us the need to wait for either something to do in X or F. We need to provide some interface/mechanism for the X's client code to reschedule some execution when a future becomes ready. This can be implemented in a number of ways;
A. F supplies a callback from the promise-fulfilling thread which is used to signal X.
B. X supplies a work-to-do callback hook. We somehow use this hook to create a combined future with F and wait for it.
C. X supplies a future<void> which becomes ready when there is work to be done. We wait for the combined future of F and this future
D. Futures and X both depend on the same condition-expression waiting mechanism and both expose this fact. We wait on this mechanism.
E. X is re-written to work with futures internally. This fact is either exposed directly or a mechanism to schedule a future-dependent execution is given.
F. *slap*! Futures should not be exposed directly to X's client code. Rather the future-dependent execution should be done in some external thread which then notifies X. This could be a fire and forget thread per future. Or it could be a reusable service thread which can wait on multiple futures and dispatch arbitrary functions accordingly.

I've been arguing against A which otherwise seems like a simple solution. B seems a bit analogous, but I suppose it depends on what X is.

Thoughts on this? Is this a real problem and typical use case or am I just programming in strange ways?

Johan

[Peter Dimov-5]

Johan Torp:

> I often have some kind of top flow control mechanism for some threads
> which
> waits - without any time limit/poll - when there is nothing to do. It
> might
> be;
> - A message pump
> - An asio::io_service (calling run)
> - A job queue
> - A logical clock in reactive programming
>
> Within this thread code is executed while processing a message, servicing
> some thing, executing a job or inside a logical clock tick/instant. Let's
> call this X's client code. Inside the client code I imagine you often will
> create a new pending request to some service and get a future back to wait
> on. Instead of waiting directly on the future and stall the entire thread,
> you'd typically want to get a notification from X at a later point. Let's
> call this future F and let's for simplicity assume there is only one of
> it.
>
> This gives us the need to wait for either something to do in X or F.

The fundamental question is whether the layer you're calling should expose

    future<X> async_do_something( Y y );

or

    void async_do_something( Y y, function<void(X)> done );

Obviously, in a message-passing-based architecture, the second interface
would be more convenient as it allows you to just post an appropriate
message in 'done'.

The "completion callback" approach tries to express the second interface in
terms of the first, but I'm not quite sure that this is correct. Expressing
the first in terms of the second seems more natural to me.

future<X> async_do_something( Y y )
{
    promise<X> px;
    future<X> fx = px.get_future();
    async_do_something( y, bind( &promise<X>::set_value, move(px), _1 ) );
    return fx;
}

There's the small problem with the exceptions though.

void async_do_something( Y y,
    function<void(X)> done, function<void(exception_ptr)> failed );

future<X> async_do_something( Y y )
{
    shared_ptr< promise<X> > px( new promise<X> );
    future<X> fx = px->get_future();

    async_do_something( y,
        bind( &promise<X>::set_value, px, _1 )
        bind( &promise<X>::set_exception, px, _1 )
    );

    return fx;
}

which only reaffirms my experience that each time you see something
move-only, you are going to need shared_ptr to get around its limitations.
But that's another story. :-)

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

[Johan Torp]

Peter Dimov-5 wrote:

The fundamental question is whether the layer you're calling should expose

    future<X> async_do_something( Y y );

or

    void async_do_something( Y y, function<void(X)> done );

Obviously, in a message-passing-based architecture, the second interface
would be more convenient as it allows you to just post an appropriate
message in 'done'.

The "completion callback" approach tries to express the second interface in
terms of the first, but I'm not quite sure that this is correct. Expressing
the first in terms of the second seems more natural to me.

Interesting way of putting it. I was hoping we could do better than the second interface, that futures could solve a lot of the problems which are associated with that approach;
- Exception propagation, as you pointed out
- It does not allow detection that there are not futures associated with a particular promise, which has been proposed.
- You need to handle safe and threadsafe shutdown from within the "done" callback, if the future-listening thread wants to terminate before the active object
- It also suffers from all of the problem with moving functors/code from one thread to another. See my arguments regarding executing foreign thread's code at: http://www.nabble.com/-future--Early-draft-of-wait-for-multiple-futures-interface-to17242880.html
I guess most done-callbacks will be thin wrappers which does minimal things like posting a message containing the value but the problems are still there.

The alternatives A-F which I listed in my previous post assumes interface 1. It's about trying to "marry" different architectures with futures. I was hoping futures could be used as in interface 1 given any architecture you might have - but it seems difficult.

Does this seem like a reasonable goal? Do you have any comments on the alternatives A-F in my previous post? Or any thoughts regarding the problems I listed with executing foreign threads' code?


Johan

[Peter Dimov-5]

Johan Torp:

> Interesting way of putting it. I was hoping we could do better than the
> second interface, that futures could solve a lot of the problems which are
> associated with that approach;
> - Exception propagation, as you pointed out
> - It does not allow detection that there are not futures associated with a
> particular promise, which has been proposed.
> - You need to handle safe and threadsafe shutdown from within the "done"
> callback, if the future-listening thread wants to terminate before the
> active object
> - It also suffers from all of the problem with moving functors/code from
> one
> thread to another. See my arguments regarding executing foreign thread's
> code at:
> http://www.nabble.com/-future--Early-draft-of-wait-for-multiple-futures-interface-to17242880.html
> I guess most done-callbacks will be thin wrappers which does minimal
> things
> like posting a message containing the value but the problems are still
> there.

There's no question that the future-based interface can be safer and more
convenient. But this doesn't necessarily make it "the" low-level interface
on top of which one can (or must) express all other interfaces.

The callback-based interface, on the other hand, can be difficult to use,
but both future-based and message-based interfaces can be built upon it.

A future-based interface built on top of a callback interface doesn't seem
to suffer from the deficiencies you list, and neither does a message-based
interface (given an appropriately powerful and robust message-passing
framework in which to express it.)

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

[Johan Torp]

Peter Dimov-5 wrote:

There's no question that the future-based interface can be safer and more
convenient. But this doesn't necessarily make it "the" low-level interface
on top of which one can (or must) express all other interfaces.

I wasn't suggesting this, for instance I doubt Microsoft will be unwilling to rewrite their message pumps to use futures internally :)

I wonder if all existing architectures can somehow be adapted to work smoothly with futures - without the future-complete callback. Either by intrusively adding explicit support for futures or by writing some simple helper functions which maps futures into the main flow control. For instance, a message passing architecture might provide something like this:

active_object a;
future<X> x  = a.do_foo_async();
// Can this be implemented?
repost_as_message_when_ready(message_channel, x, bind(&make_foo_complete_message, _1));

If futures can be integrated into any architecture, I imagine they can become "the glue" between user architecture and various asynchronous libraries.

Does this seem lika a reasonable goal for futures?

Peter Dimov-5 wrote:

The callback-based interface, on the other hand, can be difficult to use,
but both future-based and message-based interfaces can be built upon it.

A future-based interface built on top of a callback interface doesn't seem
to suffer from the deficiencies you list, and neither does a message-based
interface (given an appropriately powerful and robust message-passing
framework in which to express it.)

You're right. Maybe the more powerful but more dangerous callback-style interfaces is better in many situations rather than forcing futures on the users. Future return value-interfaces has a certain elegancy/clarity to them which I guess I'm drawn to :)

Johan