document

HTML5 & JavaScript side
twitter: @y_imaya

2015年02月

6to5 に末尾呼び出し最適化が入ったと思ったら一瞬でなくなった

一昨日の記事を書いた後、末尾呼び出し最適化の実装にバグがあって速攻で消されたようです。

  • v3.5.0: 末尾呼び出し最適化の実装が入る
  • v3.5.1: 他のTailオブジェクトと混同して判定されてしまうため、Tail.prototype._isTailDescriptor というのを付けて対処
  • v3.5.2: _tailCall をつかった末尾呼び出し最適化がコメントアウト
  • v3.5.3: v3.5.0 以前の末尾再帰最適化の実装に戻す

少し見たところ、以下のようなケースでうまく動かないようです。

function foo() {
  return "foo";
}

function fooWrapper() {
  return foo();
}

function test() {
  var str = fooWrapper();
  if (str !== "foo") {
    throw new Error();
  }
}

function testWrapper() {
  return test();
}

testWrapper();

なぜこのケースでうまく動かないのか見ていきます。
このコードを 6to5(v3.5.1) で変換したものがこちらです。

"use strict";

var _tailCall = (function() {
    function Tail(func, args, context) {
        this.func = func;
        this.args = args;
        this.context = context;
    }
    Tail.prototype._isTailDescriptor = true;
    var isRunning = false;
    return function(func, args, context) {
        var result = new Tail(func, args, context);
        if (!isRunning) {
            isRunning = true;
            do {
                result = result.func.apply(result.context, result.args);
            } while (result instanceof Tail || result && result._isTailDescriptor);
            isRunning = false;
        }
        return result;
    };
})();

function foo() {
    return "foo";
}

function fooWrapper() {
    return _tailCall(foo);
}

function test() {
    var str = fooWrapper();
    if (str !== "foo") {
        throw new Error();
    }
}

function testWrapper() {
    return _tailCall(test);
}

testWrapper();

呼び出し順序は以下の順序です。

testWrapper
  _tailCall(test)
    test
      fooWrapper
        _tailCall(foo)

ここで問題となるのが _tailCall(foo) です。
これはもともと return foo(); なので "foo" が返るはずです。
しかし、この呼び出し順序では最初の _tailCall(test) が呼ばれた時に isRunnningtrue になるため、 _tailCall(foo) は Tail オブジェクトを返します。
var str = fooWrapper();str の値が Tail オブジェクトになってしまうため、変換前の結果と異なってしまいます。

今回のように他の末尾呼び出ししている function の戻り値を変数に代入するようなケースでもうまく動くような修正が入らなければ、再び末尾呼び出し最適化を有効にするのは難しそうな気配を感じます。
(現在はもともと入ってた末尾再帰最適化での高速化を行っているようです)
そのほかにもパフォーマンスの問題もあるので大変そうですが、はやく再び有効になると良いなあと思います。

6to5 に末尾呼び出し最適化が実装されたので調べてみた

@azu_re さんのツイートで知ったのですが、6to5 に末尾呼び出し最適化が追加されました。

ECMAScript 6 compatibility table によると ES6 transpiler では初めてテストを通った実装のようです。

6to5 ではどのような ECMA−262 5th のコードに変換して実現しているのか気になったので調査してみました。

末尾呼び出し最適化って何?

その前に「末尾呼び出し最適化って何?」って人のために簡単に説明しておきます。
通常、再帰するようなコードを書くとこんな感じになります。

function f(num) {
  var acc = arguments[1] || 0:
  return num <= 0 ? acc : f(num - 1, acc + num);
}

var result = f(5);
console.log(result);

この場合だと 5+4+3+2+1 を計算するコードですね。
f の呼び出しに注目すると、f(5) の中で f(4, 5) が呼ばれ、その中でさらに f(3, 9) が呼ばれ…という感じになっています。
この呼び出しをインデントで表すと以下のようになります。

result = f(5);
    return f(4, 5);
        return f(3, 9);
            return f(2, 12);
                return f(1, 14);
                    return f(0, 15);
                        return 15;

このように、再帰するたびにコールスタックが増えていきます。
コールスタックが増えるたびに f のスコープの変数なども保持していなくてはならないため、メモリをどんどん消費していきます。
(なお、ブラウザによりますがコールスタックがあまりに増えすぎると例外を投げて止まります)

それはよくないということで、return するときに function 呼び出している場合は現在のスコープを破棄して、呼び出している function の戻り値をそのまま呼び出し元に返すようにします。
これを末尾呼び出し最適化といいます。

あまり正確ではありませんが、前述の呼び出しに末尾呼び出し最適化を適用すると以下のようになります。
呼び出し自体は変わっていないのですが、呼び出し元がずっと同じイメージです。

result = f(5);
    return f(4, 5);
    return f(3, 9);
    return f(2, 12);
    return f(1, 14);
    return f(0, 15);
    return 15;

実際に変換してみる

元となるコードは下記の通り。

function f(num, acc=0) {
  return num <= 0 ? acc : f(num - 1, acc + num);
}

var result = f(5);
console.log(result);

これを 6to5 で変換したのがこちら。
_tailCall が一行になっていて読みにくいので Google Chrome の開発者ツールで整形しています。

"use strict";

var _tailCall = (function() {
    function Tail(func, args, context) {
        this.func = func;
        this.args = args;
        this.context = context;
    }
    var isRunning = false;
    return function(func, args, context) {
        var result = new Tail(func, args, context);
        if (!isRunning) {
            isRunning = true;
            do {
                result = result.func.apply(result.context, result.args);
            } while (result instanceof Tail);
            isRunning = false;
        }
        return result;
    };
})();

function f(num) {
    var acc = arguments[1] === undefined ? 0 : arguments[1];
    if (num <= 0) {
        return acc;
    } else {
        return _tailCall(f, [num - 1, acc + num]);
    }
}

var result = f(5);
console.log(result);

まず、return num <= 0 ? acc : f(num - 1, acc + num); の条件演算子が最適化され、retrun accreturn _tailCall(f, [num - 1, acc + num]); に分解されています。

ここからが末尾呼び出し最適化のキモで、_tailCall というメソッドが何を行っているのか見ていきます。

_tailCallfunc, args, context の3つの引数をとります。
func は元の function, args はその引数, context はおそらくレシーバを指しています。
これらは元となる function を function.prototype.apply で実行するのに不可欠だからです。
これらのコンテキストを Tail というオブジェクトにしています。

最初の呼び出しだけ do-while のループに入るようにして、次回以降はそのまま Tail オブジェクトを返すようにしています。
これは何をしているのでしょうか?
このコード例を元に条件文や変数を都度展開して追っていくと以下のようになります。

1. result = f(5);
    // f(5, 0)
    2. return _tailCall(f, [4, 5]);
        3. result = new Tail(f, [4, 5], undefined)
        4. result = result.func.apply(undefined, [4, 5])
            // f(4, 5);
            5. return _tailCall(f, [3, 9]);
                6. result = new Tail(f, [3, 9], undefined);
                7. return result; // Tail Object
        8. result = result.func.apply(undefined, [3, 9]);
            // f(3, 9);
            9. return _tailCall(f, [2, 12]);
                10. result = new Tail(f, [2, 12], undefined);
                11. return result; // Tail Object
        12. result = result.func.apply(undefined, [2, 12]);
            // f(2, 12);
            13. retrun _tailCall(f, [1, 14]);
                14. result = new Tail(f, [1, 14], undefined);
                15. return result; // Tail Object
        16. result = result.func.apply(undefined, [1, 14]);
            // f(1, 14);
            17. retrun _tailCall(f, [0, 15]);
                18. result = new Tail(f, [0, 15], undefined);
                19. return result; // Tail Object
        20. result = result.func.apply(undefined, [0, 15]);
            // f(0, 15);
            21. return 15; // not Tail Object
        22. return 15;

これを見るとわかるように、2回目以降の _tailCall 呼び出しはその場で function を呼び出すのではなく、Tail オブジェクトを返すようにすることでコールスタックが深くなっていくのを避けています。

追記(2015/02/10 13:00)

末尾呼び出し最適化の実装が不完全だったため v3.5.2 以降でこの実装は除外されました。
詳しくは別途記事を書いたのでそちらを見てください。

記事検索
最新コメント
最新トラックバック
カテゴリ別アーカイブ
タグクラウド
QRコード
QRコード
  • ライブドアブログ