継続渡し

spawn_and_wait_for_all メソッドは、子タスクの完了を待つ親タスクを実行する便利な方法ですが、場合によっては非効率です。スレッドが spawn_and_wait_for_all を呼び出すと、子タスクがすべて完了するまで、スレッドはほかのタスクを実行してビジー状態を保ちます。親タスクで継続する準備ができても、スレッドはほかのタスクを実行しているため、直ちに継続できません。解決方法は、親が子を待たないようにして、代わりに子と return の両方を生成することです。子は、その親の子としてではなく、親の継続タスク として割り当てられます。子が完了すると、任意のアイドルスレッドが継続タスクをスチールして実行します。

簡単な例で説明した FibTask の "継続渡し" バージョンを次に示します。

struct FibContinuation: public task {
    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 {
            // 変更前:	long x, y;
            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);
            // ref_count を "子タスクの数 2" に設定
            c.set_ref_count(2);
            spawn( b );
            spawn( a );
	    // 変更前:	*sum = x+y;
            return NULL;
        }
    }
};

オリジナルバージョンと継続渡しバージョンの違いは次のとおりです。

大きな違いは、オリジナルバージョンでは x と y が execute メソッドでローカル変数であることです。継続渡しバージョンでは、子が完了する前に親がリターンするため、これらはローカル変数になりません。その代わり、継続タスク FibContinuation のフィールドになります。

さらに、割り当て方法が変更されています。継続バージョンは allocate_continuation で割り当てられます。this のサクセサー (successor) を c に転送して、this のサクセサー を NULL に設定することを除いて、allocate_child と似ています。次の図は、この動作を要約したものです。

allocate_continuation の動作

変換のプロパティーは、サクセサーの参照カウントを変更しないため、参照カウント方法による干渉を回避できます。

参照カウントは、子の数の 2 に設定されます。オリジナルバージョンでは、spawn_and_wait_for_all で増分カウントが必要なため、3 に設定されています。さらに、コードは、子で待機するのは継続の実行のため、親ではなく、継続の参照カウントを設定します。

FibContinuation に格納するのは、現在は *sum であるため、sum ポインターは、コンストラクターによって継続に渡されます。子は、まだ allocate_child によって割り当てられますが、親ではなく、継続 c の子として割り当てられることに注意してください。これは、this ではなく、c が両方の子が完了したときに自動的に生成された子のサクセサーになるためです。誤って this.allocate_child() を使用した場合、両方の子が完了した後に親タスクが再び実行されます。

オリジナルのトップレベル・コード、ParallelFib がどのように記述されていたかを考えてみると、ルートの FibTask が子の終了前に完了し、トップレベル・コードはルートの FibTask を待つために spawn_root_and_wait を使用しているため、継続渡しスタイルがコードを分割するのではないかと懸念するかもしれません。しかし、spawn_root_and_wait は継続渡しスタイルで正常に動作するように設計されているため、問題ありません。spawn_root_and_wait(x) の呼び出しは、実際には x の終了を待ちません。その代わり、x の仮のサクセサーを作成して、そのサクセサーの参照カウントがデクリメントするのを待ちます。allocate_continuation は、この仮のサクセサーを継続に転送するため、継続が完了するまで仮のサクセサーの参照カウントはデクリメントされません。

親トピック: 役立つタスク手法