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

Subject: Re: [boost] Futures - Reviews Needed (January 5, 2009)
From: Johan Torp (johan.torp_at_[hidden])
Date: 2009-01-05 16:29:27

Here is my review. Quite long so please bear with me :)

* What is your evaluation of the design?

The split promise/future design, exception propagation mechanism and broken
promise detection are well thought through. I have full confidence that both
authors are quite capable to nail down any details remaining regarding
these.

I think we should have support for movable types which motivates the
distinction between shared_future and unique_future (as in William's
version). 

I am however, very concerned about the waiting mechanisms and callback hooks
of both libraries. See motivation below.

* What is your evaluation of the implementation?

Both implementations seem to be of good quality.

* What is your evaluation of the documentation?

I haven't spent much time reviewing them, at a first glance they both seem
fine but William's might add some flesh. I personally wouldn't mind allowing
a lot of documentation to be added after a formal review acceptance.

* What is your evaluation of the potential usefulness of the library?

It depends. It has the potential to become an extremely useful library if we
can find a powerful enough interface, otherwise I'm afraid it might cause
more problems than it solves. See motivation below.

* Did you try to use the library?  With what compiler?
  Did you have any problems?

I've used a slimmed down version of Gaskill's implementation in production
code. I have not written any toy programs using either of the two libraries

* How much effort did you put into your evaluation?
  A glance? A quick reading? In-depth study?

I've spent a lot of hours thinking about the waiting and callback problems,
50h++ during the last year. I’ve focused the review solely on these matters.

* Are you knowledgeable about the problem domain?

Quite. I've have many years of experience in writing commercial C++
multithreaded applications and have recently written a five months master's
thesis on the shift to parallel processors, thread based programming and
memory consistency.

* Do you think the library should be accepted as a Boost library?

Unfortunately, no. Some fundamental and very difficult design decision
remains. If, however, we can find consensus on these matters, I'd gladly
change my vote to yes.

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

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.

Gaskill's implementation allows schedulers and multiple waiting to be
implemented by allowing arbitrary callbacks to be executed in the promise
fulfilling thread (set in future::add_callback, executed in promise::set).
This is powerful but quite dangerous, for instance if that callback throws
an exception, it will propagate to the promise-fulfilling thread. Another
problem is that you cannot implement future::remove_callback in a dead-lock
free way so that the callback is guaranteed to not take place as soon as
future::remove_callback returns. 

Alternatively, the callback can be executed lazily in future::wait and
future::get once the future-listening thread calls them. This removes some
problems but introduces some others. For instance a scheduler cannot know
when a promise is fulfilled until a client somehow waits for them. And there
might be several future-listening threads which want to execute different
callbacks, etc.

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.

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. 
  If you want to schedule M callbacks after M futures are ready you get
O(M^2) waiting time.
- 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. 

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. 
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
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
#1 Come up with a better wait_for_any mechanism (probably some kind of
future container, another idea is exposing the internal condition variable)
#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
#4 Verify that the proposed future is suitable for all identified use cases
or discard them as irrelevant. 
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 hope I haven't kept a too negative tone in my review. I think both
implementations are very good and I really appreciate the effort you both
have spent :)

Best Regards, Johan Torp
www.johantorp.com
-- 
View this message in context: http://www.nabble.com/Futures---Reviews-Needed-%28January-5%2C-2009%29-tp21221849p21299340.html
Sent from the Boost - Dev mailing list archive at Nabble.com.