document

HTML5 & JavaScript side
twitter: @y_imaya

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 以降でこの実装は除外されました。
詳しくは別途記事を書いたのでそちらを見てください。

zlib.js の Inflate 実装を JSX-lang に移植しました

はじめに

JSX 速いという話を聞いたので、zlib.js を移植したらどうなるのか興味があったので試しました。

お詫び

JSXがリリースされた直後に少し触ってみたのですが、最初期のバージョンでは素のJSとの連携が取りにくかったので、自分の用途には少しマッチしないなと敬遠気味でした。
その認識は最近まで続いていたのですが、現在は export なども出来るようになっているのでライブラリなんかも簡単に作れるようになってます。
(おそらく実装されたのは 2013-04-30 にリリースされた v0.9.27 ?)

何度か飲み会などで「素のJSとの連携が取りにくいからなー」とか言ってしまって誤解を与えてしまったのをここでお詫びします。
(export できるのは @tkihira さんに出来ますよと言われてやっと気がついたので、身近にJSXの熟練者がいなかったのが勘違いを持続した一因だとおもってます。JSX詳しい人ってどのへんに生息してるんでしょうか…)

悩んだところ

Array.<number> と Uint8Array の適切な扱い

zlib.js は Array.<number> と Uint8Array どちらも扱えるようになっているので、JSXにおいてもその仕様は維持したいと思っていました。
しかし、Array と Typed Array はどちらも Arraylike だけど継承関係にないので扱いにくい感じです。
結局は以下のように ByteArray というラッパーモジュールを作って、それを通すことで解決しました。
この ByteArray は constructor を持たずすべてのメソッドが static function なので、このモジュールに対する副作用は存在しないため、おそらくコンパイラが適切に最適化してくれるだろうなと推測して書きました。
(出力されたJSを確認したところ、期待通りこのモジュールの function call はきちんと展開されていました。便利)

final class ByteArray {
  static function subarray(array: Array.<number>, start: number, end: number): Array.<number> {
    return array.slice(start, end);
  }

  static function subarray(array: Uint8Array, start: number, end: number): Uint8Array {
    return array.subarray(start, end);
  }
  ...
}

JS のライブラリとして使えるように export

以下のように __export__ 修飾子を付ければ良いようです。
また、ここでも Array.<number>Uint8Array の扱いに困りましたが、とりあえず別のプロパティとしてあつかって振り分ける事にしました。

import '../src/inflate.jsx';

__export__ class ZlibInflate {
  var array: Inflate.<Array.<number>>;
  var uint8: Inflate.<Uint8Array>;
  var typed: boolean;

  function constructor(input : variant, options : Map.<variant>) {
    if (input instanceof Array.<number>) {
      this.array = new Inflate.<Array.<number>>(input as __noconvert__  Array.<number>);
      this.typed = false;
    } else if (input instanceof Uint8Array) {
      this.uint8 = new Inflate.<Uint8Array>(input as __noconvert__ Uint8Array);
      this.typed = true;
    } else {
      throw new Error('invalid input');
    }
  }

  function decompress() : variant {
    return this.typed ? this.uint8.decompress() : this.array.decompress();
  }
}

そして、これを以下のように jsxjsx-linker を使ってビルドする。

$ jsx --release --minify export/inflate.jsx | ./node_modules/.bin/jsx-linker -t export-global --stdin -o inflate.js

これだけでライブラリとして使えるようになります。便利。

性能

どきどきしながら計測したんですが、zlib.js とあまり違いは見られませんでした。
以下のページで確認できます。

また、ファイルサイズにおいても Array.<number>Uint8Array を受け付ける設計になっていたので JSX 版はそれぞれの型でメソッドを生成する必要があるため、zlib.js と比べて単純に倍程度のファイルサイズになってしまいました。
余計なコードが入っている訳ではないのでこの出力結果はかなり良いと思います。

終わりに

そこそこ使い慣れている JavaScript と、初心者状態である JSX の実装を比較するのはあまりフェアではないような気がしますが、今回は JavaScript とあまり変わらない結果になってしまいました。
JSX 熟練者の方々からのツッコミなどお待ちしております。

#寿司js で Docker について雑に話してきました

#寿司js で Docker について雑に話してきました

寿司だ寿司だとつられていったらなぜかLTする雰囲気だったので慌てて資料をつくって、最近やっていたDockerでの環境構築について簡単に話してきました。

以下のような話題が話されていた気がします。すでにうろ覚えです。

  • promises
    • http://swipe.to/0990
    • 状態は一方向で基本的に使い捨て
    • 例外処理がきちんと出来る
    • 別に実装は含まれなくてもいいけど標準仕様は決めてほしい
      • 各実装でAPIばらばらでつらい
  • なごやLTとは
    • 突っ込みが無限に入るけど時間はゆるい
    • 東京も大きいところ以外は大体ゆるい
  • E2Eテストどうする
  • フレームワーク
    • Vue.js 流行ってる(ごく一部で)
  • hue (電球の方)
    • 微調整とか出来て良い
  • Firefox OS 国内でどれくらいシェアとるつもりなのか
    • キャリアの本気度が分からないと本腰をいれていいのか迷う
    • Tizen...
    • キャリア向けの説明資料とか見たい
    • 今度出る端末のスペックはゲーム動くレベルなの?
    • asm.js 効いてる…?
  • package.json などが更新されたら自動で npm install 等したいけどどう?
  • Docker めっちゃはまる
  • 寿司で学ぶ Web Components
    • x-sushi 要素とは...
    • 属性の有無で皿が消えたりする
    • Web Components が良いのは他のCSSの影響を受けない
    • 今後コンポーネントベースのUIフレームワーク増えそう
    • Polymer 使っておけばバックエンドがいつの間にか Web Components に切り替わってるとかありそう

#JSオジサンで Source Map について話してきました

JSオジサンという名前からしてダメそうな感じのイベントでLTしてきました。 内容については azu さんのまとめ(→ JSオジサンで現在のJavaScript ASTについて発表してきた )を見ると良いと思います。

LT5分なのに時間オーバーしたあげく枠のおかわりまでしてすみませんでした…。

おっさんたちが集まってわいわいLTするゆるふわイベントだと思って、
最近ちょっと触った Source Map の話でもするかーと思って申し込んだら予想外にガチ勢が多くいたため、こりゃもうちょっと資料ちゃんとしないと駄目かなと思ってページ増やしたら時間足りなくなってしまいました。

楽しいイベントだったので次回以降もあるならば、予定があえば参加していきたいです。

発表資料

zlib.js 0.2.0 をリリースしました

更新が必要な人

今回は Inflate のアルゴリズム部分のバグ修正となるので、過去のバージョンで Inflate を利用している方は更新する必要があります。

バグ詳細

このコミットの解説となります。

Deflate では、リテラルと長さ・距離符号(LZSS)をハフマン符号化して圧縮します。
ハフマン符号も辞書をそのまま格納するのではなく、符号の長さだけを格納することで更なるサイズ節約を行っています。
さらに、符号の長さもランレングス符号化を行って格納されます。

リテラルと長さ符号、距離符号は別々にハフマン符号化し、それぞれ RFC1951 では HLIT, HDIST と呼ばれています。
このように、別々の辞書を使ってハフマン符号化されるため、ランレングス符号化もそれぞれ別のコンテキストで行われるものだとおもっていたのですが、
どうやら、HLIT と HDIST を連続したものと扱いランレングス符号化するのが正しかったようです。

issue#29 の例でいうと、HLIT の符号長が

[..., 5, 3, 5, 6, 6, 4, 5, 7, 8, 8, 7]

となっていて、HDIST は以下のようになっていました。

[16, 16, 4, 7, 3, 7, 6, 7, 7, 6, 6, 6, 5, 6, 5, 4, 4, 4, 3, 4, 3, 4]

HDIST の 16 という値は「前の値を複数回コピーする」というもので、修正前の実装では初期値である 0 をコピーしてしまっていました。
これを今回の修正で、HLIT の最後の値である 7 をコピーすることで正常に展開することができるようになりました。
今までのテストで見つかっていなかったのが不思議ですが、あまり頻繁にあるケースではないのかもしれません。

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