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

From: Johan Torp (johan.torp_at_[hidden])
Date: 2008-05-12 11:26:10

Anthony Williams-3 wrote:
> 
> Suppose you're using a thread pool to provide a parallel version of
> quick-sort. The easiest way to do that is to partition the values into
> those
> less than and those not-less-than the chosen pivot (as you would for a
> single-threaded version), and submit tasks to the thread pool to sort each
> half and then waits for them to finish. This doubles the number of tasks
> with
> each level of recursion. At some point the number of tasks will exceed the
> number of threads in the pool, in which case you have some tasks waiting
> on
> others that have been submitted to the pool but not yet scheduled.
> 
> If you can arrange for the implementation to identify this scenario as it
> happens, and thus schedule the task being waited for to run on the waiting
> thread, you can achieve greater thread reuse within the pool, and reduce
> the
> number of blocked threads.
> 
> One way to do this is have the pool use packaged_tasks internally, and set
> a
> wait callback which is invoked when a thread waits on a future from a pool
> task. When the callback is invoked by the waiting thread (as part of the
> call
> to wait()), if that waiting thread is a pool thread, it can proceed as
> above. If not, then it might arrange to schedule the waited-for task next,
> or
> just do nothing: the task will get its turn in the end.
> 

I misunderstood - I thought set_wait_callback was Gaskill's proposed
callback when a future was ready.

If I understand you correctly this use case is as follows;
Each future correlates to an unfinished task. 
A. When a worker thread calls wait(), instead of/prior to blocking it might
perform another task
B. By detecting when client/non-worker threads are waiting we can use that
information to serve them faster.

A seems very dangerous. The worker thread has a stack associated with the
task it is carrying out. If the thread crashes or an exception is thrown,
only the current task is affected. If it should carry out another task
[task2] on top of the first task [task1], task2 crashing would destroy task1
too. Also, we could get a problem with too deep stack nesting if the same
thread starts working on more and more tasks.

B might be useful. It can't detect waiting by periodic is_ready-polling -
which with todays interface is needed to wait for more than one future.
Rather than implicitly trying to guess client threads' needs wouldn't it be
better to either:
- Let the thread-pool be a predictable FIFO queue. Trust client code to do
the scheduling and not submit too many tasks at the same time.
- Open up the pool interface and let users control some kind of
prioritization or scheduling

I'm probably misunderstanding something here.

Anthony Williams-3 wrote:
> 
> Waiting for one of a number of tasks is an important use case. I'm not
> sure
> how best to handle it. I've seen people talk about "future_or" and "f1 ||
> f2",
> but I'm not sure if that's definitely the way to go.
> 

I think we should allow waiting on a dynamically changing number of futures.
Operators are poorly suited for this because they require function
recursion. Maybe some kind of future container with wait_all() and
wait_any() functions. My biggest question is how this will map to
condition_variables. Also, could this facility be some layer below futures
which can be reused?

Dependency deduction and lazy return value composition functionality - like
operators - should probably be built on top of the dynamic waiting facility. 

Anthony Williams-3 wrote:
> 
> However, even though distinct overloads will be called, this is not
> necessarily desirable, as the semantics are distinct.
> 

In what way are the semantics different?

Anthony Williams-3 wrote:
> 
> The members of the LWG are discussing renaming
> condition_variable::timed_wait to have distinct names
> for the duration and absolute time overloads in order to ensure that the
> user
> has absolute clarity of intent: wait_for(absolute_time) or
> wait_until(duration) won't compile.
> 

To be extra clear, I'll repeat myself: This will complicate writing parallel
algorithms which works generically with any time type. For both library
vendors and users.

My 5 cents is still that 2 x time_limited_wait is clear and readable enough
but it's no strong opinion. For good or bad you are forcing users to supply
their intent twice - by both argument type and method name. Is this a
general strategy for the standard library?

Best Regards, Johan
-- 
View this message in context: http://www.nabble.com/Review-Request%3A-future-library-%28Gaskill-version%29-tp16600402p17189801.html
Sent from the Boost - Dev mailing list archive at Nabble.com.