Intel Threading Building Blocks

Continuation Passing

The spawn_and_wait_for_all method is a convenient way to wait for child tasks, but it incurs some inefficiency if a thread becomes idle. The idle thread attempts to keep busy by stealing tasks from other threads. The scheduler limits possible victim tasks to those deeper than the waiting task. This limit modifies the policy that the shallowest task should be chosen. The limit restrains memory demands in worst-case scenarios.

A way around the constraint is for the parent not to wait, but simply to spawn both children and return. The children are allocated not as children of the parent, but as children of the parent’s continuation task, which is a task that runs when both children complete. Example 9-7 shows the continuation-passing variant of FibTask, with the addition of FibContinuation c.

Example 9-7. Continuation-passing Fibonacci

struct FibContinuation: publictask { long* const sum; long x, y; FibContinuation( long* sum_ ) : sum(sum_) {} task* execute() { *sum = x+y; return NULL; } }; struct FibTask: public task { const long n; long* const sum; FibTask( long n_, long* sum_ ) : n(n_), sum(sum_) {} task* execute() { if( n<CutOff ) { *sum = SerialFib(n); return NULL; } else { FibContinuation& c = *new( allocate_continuation() ) FibContinuation(sum); FibTask& a = *new( c.allocate_child() ) FibTask(n-2,&c.x); FibTask& b = *new( c.allocate_child() ) FibTask(n-1,&c.y); // Set ref_count to "two children". c.set_ref_count(2); c.spawn( b ); c.spawn( a ); return NULL; ...