Re: [boost] Futures - Reviews Needed (January 5, 2009)

Subject: Re: [boost] Futures - Reviews Needed (January 5, 2009)
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2009-01-18 17:15:06

Hi,

----- Original Message ----- 
From: "Johan Torp" <johan.torp_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, January 05, 2009 10:29 PM
Subject: Re: [boost] Futures - Reviews Needed (January 5, 2009)

> 
> Here is my review. Quite long so please bear with me :)
> 
> --- MOTIVATION---
> 
> My hope is that we can find a minimal acceptable library which support
> whatever use cases we deem important. I am worried that the C++ committee is
> too focused on using futures as a part of a thread pool interface. Gaskill
> has identified a number of use cases (guards, scheduling, lazy futures etc)
> which OTOH might be too elaborate. But if the interface isn't powerful
> enough we risk getting a wide variety of non-compatible future
> implementations out there. 
 
Yes, IMO the documentation should show at least that the accepted library can manage with these use cases. Why not as examples.
 
> I'll give a brief introduction for those who haven't followed my earlier
> future-related posts. I think that "choice" or waiting hasn't been thought
> through properly. In non-trivial use cases you probably have multiple
> futures and would like to schedule executions once they are completed.

 
> A third option is that the user starts an extra fire-and-forget thread (or
> run it in a thread pool or has an idle thread waiting around) which waits
> for the future. However, threads are rather heavy weight in contemporary
> desktop operating systems (default stack space 1mb in windows and 8mb in
> linux) so this would, IMHO, severely limit the usefulness of futures.

This is exactly what I have implemented with the fork_after function using wait_for_all. If the asynchronous executor is a thread_pool you will need a task and not a thread, so no heavy at all.
 
> William's version provides the free functions wait_for_any and wait_for_all.
> Using these, a scheduler could schedule an arbitrary amount of futures using
> just one additional future waiting thread. However, the current
> implementation of wait_for_any suffers some serious problems:
> - It takes O(N) time to wait for one of N futures. 

I have proposed an implementation that takes constant time without any sort of polling. But no comments for the moment.

>  If you want to schedule M callbacks after M futures are ready you get
> O(M^2) waiting time.
With my implementation only O(M)

> - wait_for_any does not allow arbitrary code to be executed upon readiness. 
>  This forces the user to implement a runtime mapping after wait_for_any has
> returned which determines which future was ready and takes the right action.
> This is both cumbersome and less efficient than if the callback had been
> bound before initiating waiting. 

My fork_after function allows to execute asynchronously any function after the completion of N functions.
 
> Perhaps more importantly than these shortcomings, William's version does not
> support "future composition" without using a third thread. This is not
> necessarily a flaw but rather a design decision.
> Consider implementing addition of two future integers:
> 
>  future<int> add(future<int> lhs, future<int> rhs);
> - Using Gaskill's version the actual addition would be performed by lhs's or
> rhs's promise-fulfilling thread.
> - Using the lazy approach I suggested above, the addition is carried out in
> the returned future's wait() or get() method.
> - William's version requires a third thread which waits for lhs and rhs and
> then carries out the addition. 

What about

    int direct_add(int lhs, int rhs) { return lhs+rhs};
    act_adapter<shared_future<int> > add(shared_future<int> lhs, shared_future<int> rhs) {
        return fork_after(bind(direct_add, lns, rhs), fusion::tuple(lhs, rhs));
    }

> This makes future composition way too heavyweight for ubiquitous simple
> logic. For instance, the proposed future operators would require a thread
> per operator (f1 || f2 && f3 || f4 would require three threads!) and

Three task with a thread_pool. Is this better for you?

> Gaskill's guarded schedulers would be quite unusable. OTOH, not supporting
> "threadless future composition" makes futures much simpler and more
> lightweight (which might be good for threadpool). IMO, this is the most
> important and difficult design decision. Unfortunately, I think it will take
> quite some time to find a good interface for "threadless future
> composition".  If we had fibers or some other lightweight execution
> mechanism (like Erlang’s processes) it would be a non-problem. 
> 
> 
> --- DISCUSSION ---
> 
> IMHO, we need to:
> #0 Decide if we want to support "threadless future composition" and if so
> sketch on some implementation

I haven't found a safe implementation.

> #1 Come up with a better wait_for_any mechanism (probably some kind of
> future container, another idea is exposing the internal condition variable)

Are you requiring some kind of public registration on completion as used by the future_waiters?
Anthony has sais that it could be something like that, but no concrete porposal for the the moment.

> #2 Discuss if we want Gaskill's promise::is_needed and
> promise::wait_until_needed functionality
> #3 Discuss if we want William's promise::set_wait_callback

I would want this but I prefer that if it is done non intrusively, i.e. only if possible in a hierarchycal design.

> #4 Verify that the proposed future is suitable for all identified use cases
> or discard them as irrelevant. 

I agree.

> The use cases I've seen discussed are boost.asio, libpoet, the proposed
> std.threadpool, future operators, lazy futures, guards and future streams
> 
> 
> #2 adds some state and complexity to a future/promise pair. How big of a
> problem is this for thread pools (which I presume want a really lightweight
> future to allow really fine grain tasks)? 
> 
> My 5 cents on #3 is that it's not really needed to implement efficient
> thread pools. The user might as well write std::wait_or_work(some_future);
> which either waits for the future or performs additional work if the
> executing thread happens to be a worker thread. The task calling
> std::wait_or_work gets a dependency to std.threadpool but I think it is well
> worth it considering the added clarity and simplification of a future
> object. Allowing execution of arbitrary code in future::wait from
> promise::set_wait_callback (a la William's implementation) is just as bad
> and hackish as allowing promise::set_value to execute code from
> future::add_callback (a la Gaskill's implementation). 
 
I have already proposed to Olivier a reschedule_until_ready that schedule other tasks until the asynchronous completion token (a future by example) is ready.

Best,
Vicente