Boost logo

Boost :

From: Oliver Kullmann (O.Kullmann_at_[hidden])
Date: 2005-08-17 11:28:17

On Wed, Aug 17, 2005 at 10:15:11AM -0500, Hartmut Kaiser wrote:
> Oliver Kullmann wrote:
> > thanks for your reply.
> [snip]
> > Different to your solution above, we are happy with the
> > evaluation of only
> > f1 or f2 only in the case the function returned true; and I
> > guess, due to the missing cancellation of threads, in your
> > solution one thread will still continue to run (and using
> > resources) even if result has been computed and the main
> > thread is continuing, right?
> That's very much related to the idea Martin was talking about in his post
> wrt failing futures. We'll have to think about, how to allow such behaviour.
> The current implementation relies on the futures returning some 'real'
> result value, not a flag signing success.

You are right, my case could be modelled using "failing futures".
But the approach seems somewhat too special for me.

Consider for example

int f1();
int f2();

int result = run_parallel_and_evaluate_shortcircuit( f1() * f2() );

(syntax is not real, but I hope it's clear what I mean).

Here if one of f1 or f2 returns 0 then result = 0 (and the other thread
can be cancelled), while otherwise both f1 and f2 have to be computed.

The underlying theme is, that an expression is to be evaluated which uses
certain function calls f_i, and that under certain circumstances not all
of the f_i have to be evaluated (but we can short-circuit the evaluation).

With such a functionality one could also handle Martin's
'futures returns a result with quality == "best"'.

The general mechanism could be as follows (using mathematical notation):

create_thread_and_evaluate( (f_1, c_1), (f_2, c_2), ..., (f_n, c_n), e(y_1, ..., y_n) );

This expression starts n threads running f_1, ..., f_n.
If f_i finishes with result y_i, then c_i(y_i) is called; c_i(y_i) has
the possibility to cancel all the other threads and compute the result
directly. Otherwise all results are collected and the value e(y_1, ..., y_n)
is returned.

The c_i are conditions which tell us under what circumstances the result
of f_i alone is sufficient (and furthermore they compute the result in this
case), while e(y_1, ..., y_n) is the default evaluation.

Of course, there could be more complicated situation, where perhaps you have to
compute 2 out of 3 values (but not all 3). This situation could be handled by
passing to c_i the complete information which f_i have terminated yet with
which values y_i --- c_i then either decides "that's enough" and handles
the whole computation, or it says "so well, continue".


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