JavaScriptによるマルチスレッドの実現‐Concurrent.Threadの裏側

昨年12月3日の記事で，JavaScriptでマルチスレッドを利用可能にするライブラリ、Concurrent.Threadを紹介しました。しかし、そもそもスレッドが 1 つしかないJavaScript環境の上に、どのようにしてマルチスレッドを、しかもWebブラウザを改変することをせずに、実現しているのでしょうか？

今回はConcurrent.Threadの内部で何が起こっているのかについて、ご紹介しましょう。

JavaScriptにおけるスレッド

Concurrent.Threadの内部についてお話しする前に、JavaScript のスレッドについておさらいしておきます。

まず、JavaScriptにはスレッドは1本しかありません。JavaScriptのコードは呼び出されるたびに、この1本だけのスレッドを独占的に使用して実行されます。「独占的」が意味するところは、スレッドがあるコードによって使われている間は他のコードは割り込んだりすることはできないということです。そのため、JavaScriptコードを実行しようとした時に他のコードがスレッドを使っていたら、前の実行が終了するまでじっと待っていなくてはなりません。

一方、実行中のJavaScriptコードは、自分の仕事をすべて終えるまでスレッドを解放することはできません。通常、JavaScriptはHTMLの中からイベントハンドラとして呼び出されますから、イベントハンドラから完全にreturnするまではスレッドを他の仕事のために使うことはできないわけです。従ってJavaScriptにおいては、プログラムの途中で現在の仕事を中断して、他の仕事にスレッドの実行権を譲るといったことは簡単にはできません。

並行処理を実現する素朴な方法

こうしたJavaScript環境の上で並行処理を実現するには、古くからsetTimeoutが用いられてきました。次の例で考えてみましょう。

function f ( ) {
    do_something();
    do_another();
    do_one_more();
}

このプログラムでは順番に3つの関数を呼び出していますが、各関数呼び出しの間でいったんスレッドの実行権を他のJavaScriptコードに渡したいとします。これは次のように、各関数呼び出しをそれぞれ別の関数に分けて、間にsetTimeoutを挿むようにプログラムを書き換えることで実現できます。

function f ( ) {
    do_something();
    setTimeout(f1, 1);  // 1ミリ秒後にf1を呼び出す
}

function f1 ( ) {
    do_another();
    setTimeout(f2, 1);
}

function f2 ( ) {
    do_one_more();
}

こうして書き換えた関数fを、

f();
f();

のようにして2回連続して呼び出した場合の実行の様子を考えてみましょう。

まず1回目のfが呼ばれて、その中でdo_somethingが呼び出されます。do_somethingの実行が終わると、fはsetTimeoutを使って関数f1をあとで実行するように予約してから、呼び出しから返ります。すると今度は2つめのfが呼び出されて、同じようにdo_somethingを実行してからsetTimeoutして、呼び出しから返ります。

2つのfの呼び出しが終わると、このJavaScriptコードは仕事を完了してスレッドを解放します。これでスレッドに新しい仕事を割り当てることができるようになりました。するとどうでしょう、先ほどsetTimeoutで予約しておいた関数f1の時間がすぐにやって来て、スレッドの上で実行されます。f1はdo_anotherを実行して、今度はsetTimeoutでf2をあとで呼び出すように予約してスレッドを解放します。最初に関数fを2回呼び出してf1の実行予約も2回されたため、もうひとつのf1の時間もすぐにやってきて、もう一度同じように実行されます。2回のf1の実行が終わるとすぐに、今度はf2の時間がやってきます。f2も2回実行が予約されているので、do_one_moreを2回実行することになります。

この実行の様子を図に表すと下のようになります。

こうして見るとどうでしょう？もともとの書き換え前の関数fが、2つ並行に実行されているように見えませんか？

上のプログラムの書き換えのポイントは、次の仕事をsetTimeoutで予約してすぐにプログラムを終了するような形にすることです。setTimeoutしたらすぐにスレッドを解放することで、他の仕事に使えるようにしているわけです。

このような書き換えをしてやればJavaScriptでも並行処理を実現できるわけですが、いちいちこんな書き換えをしなければならないというのは面倒ですね。自分の代わりに誰かがやってくれたら、と思うのが人情というものです。

Concurrent.Threadがやってくれること

実のところ、Concurrent.Threadがしてくれるのはまさしくこのようなプログラムの書き換えなのです。Concurrent.Threadがやっていることはこれがすべてだと言っても過言ではありません（実際にはもう少しだけ仕事をしているのですが）。Concurrent.Threadはあなたの代わりに、プログラムを分割してsetTimeoutを挿み込むという書き換えを、自動的におこなってくれているのです。

しかし、上の例はとても簡単なプログラムを書き換えただけでした。もっと複雑なプログラムでも自動的に書き換えるなんてことができるのでしょうか？これから少しずつ考えていきましょう。

入れ子になったプログラムを書き換える

まずは次のような単純なループ文を書き換えてみましょう。

function g ( ) {
    while ( i < n ) {
        do_something(i);
        do_another(i);
        i++;
    }
}

目標はさっきと同じです。do_somethingとdo_anotherのそれぞれの呼び出しの間で、スレッドを他の仕事が使えるように解放するようにします。

今度は上の例ほど単純にはいきません。なぜなら最初に説明したように、JavaScriptではループの中のようなプログラムの途中で、実行を中断することはできないためです。しかし少し考えれば、ループ文を2つの関数に分割して、お互いに呼び出し合えば良いということがわかると思います。結果は次のようになります。

function g ( ) {
    if ( i < n ) {
        do_something(i);
        setTimeout(g1, 1);
    }
}

function g1 ( ) {
    do_another(i);
    i++;
    setTimeout(g, 1);
}

では、次のようなもう少し複雑なプログラムはどうでしょうか。

function h ( ) {
    p = 2;
    OUTER:
    for ( i=3; i < n; i++ ) {
        for ( j=2; j < i; j++ ) {
            if ( i % j == 0 ) continue OUTER;
        }
        p = i;
    }
}

ループ文が入れ子になっているため、この関数の実行にはとても長い時間がかかる可能性があります。そのため、繰り返しの適当なところでスレッドを解放するようにしたいとしましょう。

今回はループ文が入れ子になっていますし、また、内側のループ文の中ではラベルつきbreakを使って一気に外側のループに戻るという構造になっています。10行に満たない簡単なプログラムですが、どのように分割してやればよいかわかるでしょうか？

じっと見ているだけでは、ちょっとわからないかもしれませんね。こういう場合には、プログラムを平らにしてみるとわかりやすくなります。「平ら」というのはつまり、入れ子構造をラベルとgotoを使った形にしてみることです。するとこれは次のようになります。

function h ( ) {
    p = 2;
    i = 3;
  LABEL1:
    if ( !(i < n) ) goto LABEL6;
    j = 2;
  LABEL2:
    if ( !(j < i) ) goto LABEL4;
    if ( !(i % j == 0) ) goto LABEL3;
    goto LABEL5;
  LABEL3:
    j++;
    goto LABEL2;
  LABEL4:
    p = i;
  LABEL5:
    i++;
    goto LABEL1;
  LABEL6:
}

JavaScriptにはgoto文はありませんので、実際にはこれは正しいJavaScriptプログラムではありません。しかしこうして見ると、プログラムの切れ目がはっきりしたのではないでしょうか？そうです。ラベルからラベルまでのブロックをそのまま関数へと分割してやればいいのです。またこうすると、gotoをsetTimeoutに置き換えてやることで、ブロックの切れ目でスレッドを解放できることになります。

function h ( ) {
    p = 3;
    i = 3;
    setTimeout(LABEL1, 1);
  function LABEL1 ( ) {
    if ( !(i < n) ) setTimeout(LABEL6, 1);
    j = 2;
    setTimeout(LABEL2, 1);
  }
  function LABEL2 ( ) {
    if ( !(j < i) ) setTimeout(LABEL4, 1);
    if ( !(i % j == 0) ) setTimeout(LABEL3, 1);
    setTimeout(LABEL5, 1);
  }
  function LABEL3 ( ) {
    j++;
    setTimeout(LABEL2, 1);
  }
  function LABEL4 ( ) {
    p = i;
    setTimeout(LABEL5, 1);
  }
  function LABEL5 ( ) {
    i++;
    setTimeout(LABEL1, 1);
  function LABEL6 ( ) {
  }
}

このように、一度ラベルとgotoを使った形に置き換えて考えてやれば、どんなに複雑に入れ子にされたプログラムであっても、自動的に書き換えてやることができそうです。

でもちょっと待ってください。こうやってループ文をバラバラにしたとしても、そこで呼び出されている関数（たとえば先ほどの例にあったdo_somethingやdo_another）の中で長大なループなどを実行されてしまったら、結局そこでスレッドが独占されてしまいます。そのため、呼び出されている関数もスレッドを解放できるように、同様に書き換えてやることを考えます。しかし、関数呼び出しが絡むと、問題はもっと複雑になります。

関数は自身の処理を終えると呼出し元に実行を返しますが、どこに返すべきかは呼び出された際に関数スタックに積んでおきます。一方、JavaScriptではスレッドを解放できるのはイベントハンドラからreturnしたときだけですから、スレッドを解放するということは関数スタックを空にするということです。関数スタックが空になってしまっては、あとで呼出し元に戻る際に戻るべき先がわからなくなってしまっています。これはどうしたらいいでしょうか？

Concurrent.Threadでは、これを継続渡し形式を利用することで解決しています。

継続渡し形式 (CPS)

継続渡し形式（Continuation Passing Style ― CPS）とは、関数を呼び出す際に続きの処理（これを「継続」と呼びます）を表す関数を引数として渡すようなプログラム形式のことをいいます。またCPSでは、関数の結果をreturnする代わりに、渡された継続を呼び出すようにします。関数がreturnすることはないため、基本的にCPSのプログラムは実行が進むに従って、関数呼び出しはどんどん深くなる一方になります。

具体的にどんなものか、例で見てみましょう。まずは階乗を求める関数facを、CPSではない通常のプログラム形式で記述してみます。

function fac ( n, a ) {
    if ( n == 0 ) {
        return a;
    } else {
        return fac(n-1, a*n);
    }
}

var x = fac(10, 1);  // 10の階乗を求める
...省略

同じことをするプログラムをCPSで記述すると次のようになります。

function fac ( n, a, k ) {
    if ( n == 0 ) {
        k(a);
    } else {
        fac(n-1, a*n, k);
    }
}

fac(10, 1, rest);
function rest ( r ) {
    var x = r;
    ...省略
}

まず、関数facが続きの処理（継続）を受け取るように引数kを増やしています(1行目)。そして3行目のreturn文は、先に言ったとおり、受け取った継続に結果を渡して呼び出すようになっています。

次に、このfacを呼び出す側について見てみましょう。9行目の呼び出しでは第3引数として関数restを渡しています。このrestが続きの処理を表しています。facのあとの続きの処理というのは、facの結果を変数xに代入することです。CPSではfacの結果は関数に渡されるのでしたから、restの内容は上のように受け取った値をxに代入して、さらに続きの処理を続けるということになります。5行目のfacの再帰呼び出しは少々わかりづらいかもしれませんが、ここでのfacの呼び出しのあとの続きの処理とは、facの結果を返すことです。結果を返すのは継続（k）を呼び出すことになったわけですから、結局ここでの続きの処理というのはk自身です。従って、facにはkを渡せばよいということになります。（詳しい人へ: 演算子いえども関数の一種ですから、本来であればCPSでは演算子による計算にも継続を渡します。また、普通CPSと言ったときには関数呼び出しの引数にはアトム（変数や即値）のみを置くようにしますので、今回のプログラム例は厳密にはCPSとは言えません。しかしそこは、説明の簡潔さを優先しました。）

こうしてCPSで表現したプログラムを見てみると、関数を呼び出したあとには、いつも何もしていないことがわかると思います。関数呼び出しのあとに何もすることがないということは、呼び出しから"戻ってくる必要がない"ということでもあります。つまり、関数を呼んだら行きっぱなしで良いのです。

この"行ったら戻ってこない"という性質は、実はgotoと同じものです。そのため、乱暴な言い方をすれば、通常のプログラムをCPSに書き換えるということは、関数呼び出しをgotoに書き換えることだと考えることができます。実際、CPSで定義したfacは、再帰呼び出しを先頭へのgotoに置き換えてしまって、次のように書き換えられます。

function fac ( n, a, k ) {
  FAC:
    if ( n == 0 ) {
        k(a);
    } else {
        n = n - 1;
        a = n * a;
        goto FAC;
    }
}

ここで変数n、aの値を上書きしてしまっても大丈夫なのは、CPSでは関数呼び出しから戻ってくることがないため、もとの値が必要になることがないことが判っているからです。そのため、新しくスタックフレームを積み上げることなく、現在のスタックフレームを再利用できるという判断ができるのです。（詳しい人へ: 正確さのために捕捉しておくと、スタックフレームの再利用のためには、現在の関数に入れ子になっている関数、つまりクロージャが外に漏れ出していないということが必要になります。たとえ現在の関数に実行が戻ってくることはなくても、あとでクロージャが呼び出された際に現在のスタックフレームが参照される可能性があるからです。今回の場合は入れ子になった関数がないので、再利用できるのは明らかですね。）

このように再帰呼び出しをループにするなど、プログラムの最適化がしやすいことがCPSの便利な点です。実際、そのためCPSは関数型言語をコンパイルする際の中間表現として一般的に用いられています。もっと詳しく知りたいという人は、『Compiling with Continuations』(Andrew W. Appele著／Cambridge University Press刊)などを参照してください。

関数呼び出しが入ったプログラムを書き換える

さて、話を再び並行処理のための書き換えに戻しましょう。他の関数から呼び出された関数の中でもうまくスレッドを解放するにはどうすれば良いのかを検討していたのでした。

CPSが関数呼び出しをgotoにするようなものだという話をしましたが、gotoになってしまえば、もうこの問題は解決したも同然です。なぜなら、gotoはほぼそのままsetTimeoutに置き換えられることは、すでに説明したとおりだからです。つまり上でCPSに書き換えた関数facは、次のように単純に書き換えることができます。

function fac ( n, a, k ) {
    if ( n == 0 ) {
        setTimeout(k, 1, a);
    } else {
        setTimeout(fac, 1, n-1, a*n, k);
    }
}

見てわかるように、これは関数呼び出しの部分を単純にsetTimeoutを使って書き換えただけです（※指定した関数を呼び出す際の引数をsetTimeoutに追加で指定できるのは、MozillaやOperaでの拡張仕様ですが、ここではコードを単純化するために使用しています。例えば、上の「setTimeout(k, 1, a)」は、「setTimeout(function(){ k(a); }, 1)」と同義です）。

こうすることで、関数呼び出しのたびにスレッドをいったん解放することができるようになり、また、関数から呼び出し元へ戻ることも、継続の呼び出しによって適切に行われることがわかるかと思います。

それでは、ループ文を含む入れ子構造と、関数呼び出しの両方が使われているプログラムを書き換えてみましょう。例として、指定されたDOMノード以下の全ノードを辿る次の関数を用います。

function traverse ( node ) {
    var i;
    do_something(node);
    for ( i=0;  i < node.childNodes.length;  i++ ) {
        traverse(node.childNodes[i]);
    }
    return;
}

まずはgotoとラベルを用いてプログラムを平らにします。

function traverse ( node ) {
    var  i;
    do_something(node);
  LABEL1:
    i = 0;
  LABEL2:
    if ( !(i < node.childNodes.length) ) goto LABEL4;
    traverse(node.childNodes[i]);
  LABEL3:
    i++;
    goto LABEL2;
  LABEL4:
    return;
}

次にプログラムをCPSに書き換えます。

function traverse ( node, k ) {
    var  i;
    do_something(node, LABEL1);
  LABEL1:
    i = 0;
  LABEL2:
    if ( !(i < node.childNodes.length) ) goto LABEL4;
    traverse(node.childNodes[i], LABEL3);
  LABEL3:
    i++;
    goto LABEL2;
  LABEL4:
    k();
}

ここで、各関数呼び出しの引数には、継続の代わりとして関数呼び出しの直下にあるラベルを渡しておきます。上で説明したように、ラベルはあとで関数名になりますから、最終的にはこれでつじつまが合うわけです。最後に、ブロックを関数に、gotoと関数呼び出しをsetTimeoutに書き換えれば完成です。

function traverse ( node, k ) {
    var  i;
    setTimeout(do_something, 1, node, LABEL1);
  function LABEL1 ( ) {
    i = 0;
    setTimeout(LABEL2, 1);
  }
  function LABEL2 ( ) {
    if ( !(i < node.childNodes.length) ) setTimeout(LABEL4, 1);
    setTimeout(traverse, 1, node.childNodes[i], LABEL3);
  }
  function LABEL3 ( ) {
    i++;
    setTimeout(LABEL2, 1);
  }
  function LABEL4 ( ) {
    setTimeout(k, 1);
  }
}

トランポリン

プログラムを書き換えてsetTimeoutを挿み込むことで、並行処理を実現できるようになりましたが、上のプログラムにはとても無駄が多いということにお気づきでしょうか？このプログラムはsetTimeoutでタイマーを設定して、スレッドを解放するということを頻繁に行います。setTimeoutによる実行再開はそんなに軽い処理ではありませんから、このままではオーバヘッドが非常に大きくなってしまいます。

上のプログラムでは、ブロックからブロックへ実行が移る度にスレッドを解放するようにしていましたが、実用上はそんなに頻繁に解放する必要はありません。人間から見て気にならない程度の短い時間であれば、スレッドを使い続けても良いのです。1つの処理がスレッドを使い続けるこの短い時間のことを、タイムスライスと呼びます。タイムスライスの間スレッドを解放しないで動作するようにするために、Concurrent.Threadではトランポリンを用いています。

トランポリンというのはプログラミング言語処理系の実装でよく用いられる仕組みのことで、関数を繰り返し呼び出す機構のことを指します。トランポリンから呼び出される関数は、呼び出されるとその結果として次に実行すべき関数を返すようにしておきます。トランポリンは返された関数を同じようにして呼び出し、返された関数に対しても同様に繰り返し呼び出しを続けます。トランポリンの便利なところは、繰り返し関数を呼び出すその合間に、色々な処理を挿入することができるということです。今回の場合は、一定時間が経過したらsetTimeoutを挿入してスレッドを解放するようにするわけです。（詳しい人へ: もうお気づきでしょうが、トランポリンとCPSの間には深いつながりがあります。気になる人は『Trampolined style』(Ganz et al)を参照してみてください。）

上で例に用いた関数traverseを、トランポリンで使えるようにしてみましょう。トランポリンから呼び出される関数は次に実行すべき関数を返せばよかったわけですから、上ではsetTimeoutになっていた部分を関数を返すように変更すれば良さそうです。しかしまた、関数を呼び出す際の引数も覚えておかなくてはなりませんので、関数と引数を組にしてまとめて返すようにします。従って次のように書き換えます

function traverse ( node, k ) {
    var  i;
    return {func:do_something, args:[node, LABEL1]};
  function LABEL1 ( ) {
    if ( !node.childNodes ) return {func:LABEL4, args:[]};
    i = 0;
    return {func:LABEL2, args:[]};
  }
  function LABEL2 ( ) {
    if ( !(i < node.childNodes.length) ) return {func:LABEL4, args:[]};
    return {func:traverse, args:[node.childNodes[i], LABEL3]};
  }
  function LABEL3 ( ) {
    i++;
    return {func:LABEL2, arg:[]};
  }
  function LABEL4 ( ) {
    return {func:k, args:[]};
  }
}

このように書き換えられたプログラムは、トランポリンを表す次のような関数での上で実行することができます。

function trampoline ( ctxt ) {
    var limit = (new Date).valueOf() + TIME_SLICE;
    do {
        ctxt = ctxt.func.apply(null, ctxt.args);
    } while ( new Date < limit );  // タイムスライスの間繰り返す
    setTimeout(trampoline, 1, ctxt);
}

この関数は、TIME_SLICEで指定された時間はスレッドを解放せずに実行を続け、タイムスライスを使い切るとsetTimeoutで自分自身を再度呼び出すように予約して、いったん実行を終了するというように動きます。この実行の様子を図に表すと下のようになります。

こうして適当なタイミングでスレッドを解放することで、より効率的に並行処理を実現することができます。

コード変換

ここまででConcurrnt.ThreadがJavaScriptプログラムをどのような形に書き換えるのかを説明してきました。実際にはConcurrent.Threadはこのような変換作業をJavaScriptプログラムの実行時に行っています。Concurent.Threadがこのような実行時のプログラム書き換えをどのように行っているのかを簡単に説明しておきます。

1. ソースコードを得る
   JavaScriptでは関数を文字列化することで、その関数を定義しているソースコードを得ることができます。そのためこれを利用して、並行処理用に変換したい関数を文字列化して、そのソースコードを実行時に得ます。
2. 構文解析する
   1.で得たソースコードを解析して、プログラムから扱いやすいデータ構造（構文木）を作ります。Concurrent.Threadはこの作業を行う構文解析器として、JavaによるJavaScript実装であるRhinoのコードの一部を、JavaScriptに移植して利用しています。
3. プログラムを書き換える
   次に、これまで述べてきたような形へとプログラムを変形させます。これは2.で得られた構文木を適宜組み換えることで行われます。
4. 文字列にしてevalで評価する
   組み換えたら、結果のプログラム（構文木）を再び文字列表現に直して、組み込み関数evalに渡します。evalは文字列をJavaScriptプログラムとして評価し、その結果を返すので、これで並行処理用のJavaScript関数を実行時に得ることができるというわけです。

以上のように、Concurrent.ThreadはJavaScriptのプログラムコードを異なる表現のプログラムコードへと変換しているという点で、コンパイラと同じような仕事をしています。また、Concurrent.Thread自身もJavaScript自身で記述されているわけですから、これはある意味でJavaScript to JavaScriptのセルフコンパイラとも呼べるような構成になっています。

残された問題

以上で、Concurrent.Threadが行うプログラム書き換えの核心についての、ほとんどを説明しました。しかしまだ次のような細かいことを考える必要があります。

変数のスコープ

JavaScriptは関数内で宣言された変数は、その関数内に局所化されます。従って単純に関数を分割すると、本来見えていたはずの変数が見えなくなってしまうことになります。また、JavaScriptには変数のスコープを動的に変更することができるwith文があるため、このことも考慮しなくてはなりません。

this値とarguments配列

JavaScriptでは現在のオブジェクトへの参照を表すthisの値と、現在の関数に渡された実引数の情報を表すarguments配列の値が、関数を呼び出すたびに決まります。従って、本来ひとつであった関数を複数の関数に分割してしまうと、そのそれぞれの中でthisとargumentsの値が変わってしまうことになります。

例外処理

JavaScriptはtry-catchとthrow構文を用いた例外処理機構を備えていますが、これまでの説明ではこの点を考慮していません。

書き換えができない関数

Concurrent.Threadは関数を文字列化することで、変換もとのソースコードを得ていましたが、JavaScript処理系に組み込みで備わっている関数は、この方法で実装コードを得ることはできません。従って、並行処理用に書き換えた関数プログラムからは、組み込み関数を呼び出すことができなくなってしまいます。しかし、組み込み関数をまったく使わずに現実的なJavaScriptアプリケーションを記述することは不可能ですから、なんとかして使えるようにする必要があります。

これらの問題は説明が煩雑になるため、今回は説明しませんでした。興味のある人は、こちらの論文に書かれていますので、是非参照してみてください。

著者について

牧 大介(まき だいすけ): 国際基督教大学教養学部理学科を卒業(教養学士)したのち、電気通信大学大学院にて情報工学を専攻。Web開発、特にJavaScriptを用いた Ajaxを専門とする。Concurrent.Threadの開発者であり、このプロジェクトは情報処理推進機構(IPA) 未踏ソフトウェア創造事業(2006年度)に採択された。
現在、電気通信大学大学院博士後期過程に在籍中。工学修士。
Web サイト: http://daisukemaki.dtdns.net