Boost logo

Boost :

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


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