Boost logo

Boost :

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

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

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.

Boost list run by bdawes at, gregod at, cpdaniel at, john at