Re: [boost] Re view Request: future library (N2561/Williams version)

From: Frank Mori Hess (frank.hess_at_[hidden])
Date: 2008-05-23 17:34:47

On Friday 23 May 2008 14:32 pm, Johan Torp wrote:
>
> I'm not sure I understand you. boost.bind itself has nothing to do with
> threads waiting on eachother. You will probably use boost.bind to create
> the evaluation functions (e1 and e2 in my previous post) though.
>

I must have read too much into what you said before.  I was thinking you were 
entirely in single-threaded mode, and all your futures were just coming from 
the same kind of lazy evaluations.

Anyways, I think the main deficiency with the prototype of future_select() 
I've coded is it will always be at least O(N) where N is the number of input 
futures.  So if you are waiting for N futures one at a time, it will take N 
calls to future_select giving O(N^2) complexity.  

If you have some kind of "future combination" class that contains the set of 
futures being waited on, and can remove completed futures from it in O(1) 
time, you might do better.  It would take O(N) time to create the "future 
combination" initially, but then each wait for the next completed future 
could be O(1).

Okay, to summarize where I think we are:

1) In order to wait on an arbitrary number of futures, determined at runtime, 
we need some kind of container.  

2) Since containers are homogeneous, that means some kind of type erasure 
(future<void>).

3) When a future becomes ready, we will often want to dispatch it somehow 
which might mean getting its value, or at least identifying the input future 
which became ready.  That could mean doing some kind of type unerasure, or 
doing an inefficient loop over all the original input futures until you find 
the completed one.  Your solution is to bind the dispatcher function to the 
future before it is type erased.  For thread-safety, you want to run the 
dispatcher function in one of the waiting threads, right after the future 
becomes ready.

There will be deadlock hazards running the user's dispatcher function while 
holding the future's associated mutex.  Also, it's possible multiple threads 
will be waiting on the future, in which case how much thread-safety benefit 
is there to running code in one of the waiting threads versus a callback run 
in the promise 
thread?

What if we allow a key value to be associated with each input future, then 
return the key of the completed future?  Then it would be left to the user to 
map the key back to whatever future they were originally interested in.