document

HTML5 & JavaScript side
twitter: @y_imaya

2017年06月

asm.js を手書きする

はじめに

人間は誰しもパフォーマンスを求め、最終的には asm.js か WebAssembly を手書きするようになるので、人権を手に入れるためにいつでも asm.js を書ける環境をつくります。 WebAssembly はさすがに手書き厳しそうでした。

というのは冗談で、zlib.js の一部の処理を asm.js で高速化できないかと考え、ひとまず Adler-32 と CRC-32 を asm.js で書き直してみた際にいろいろ苦労したので忘れないようにこの記事を書いています。

なお、今回 asm.js で書いたコードは以下の通り gist で公開しています。 zlib.js での採用はまだ検証が必要なので未定ですが、採用するにしてももう少しきちんとした書き方になるでしょう。

asm.js 手書き環境の整備

JavaScript shell

asm.js は Mozilla が言い始めただけあって Firefox で実行するのが一番良いのですが、毎回 Firefox で実行するのは正直手間です。 そこで、ここでは Web ブラウザを使わずにコマンドラインだけで asm.js として正しいかチェックを行う環境を JavaScript shell を使って構築していきます。 JavaScript shell とは Mozilla の JavaScript エンジン SpiderMonkey のコマンドラインツールです。

概要:https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Introduction_to_the_JavaScript_shell

ダウンロードと準備

下記のURLから、最新版の jsshell をダウンロードしましょう。

https://archive.mozilla.org/pub/firefox/nightly/latest-mozilla-central/

あとは展開してパスを通し、

$ js -w -c hoge.js

のように js ファイルを指定して実行すると、asm.js のチェック(というか、実際にコンパイルを試みる)を行います。 なお、 -w オプションは warning を表示するオプションで、asm.js まわりのメッセージは warning として出力されるため必要となり、 -c オプションはコンパイルのみ行い、実行はしないというオプションです。asm.jsとしてただしいコードかどうかはコンパイルできるかどうかで判別できるので、実行する必要はありません。

watch

各々の好きなタスクランナーで asm.js のコードが変更されたら JavaScript shell でチェックを行うようにすると便利です。

一例として npm scripts で chokidar-cli を使って行う場合の手順を書いておきます。

ディレクトリ構成

src 以下に *.asm.js というファイル名で asm.js のコードを置き、vendor/jsshell に JavaScript shell を配置しています。

.
├── package.json
├── src
│   ├── adler32.asm.js
│   └── crc32.asm.js
└── vendor
    └── jsshell
        ├── js
        ├── libmozglue.dylib
        └── libnss3.dylib

chokidar-cli のインストール
$ npm i -D chokidar-cli
npm scripts の登録

package.json 内の scripts に以下のように watch を追加します。

  "scripts": {
    "watch": "chokidar src/**/*.asm.js -c \"vendor/jsshell/js -w -c {path}\""
  },
監視の開始
$ npm run watch

これで src/ 以下に *.asm.js となるファイルを作ったり更新したりすると、JavaScript shell によるチェックが行われるようになりました。

ひとまず、 asm.js を手書きで開発していく環境が整ったと言っても良いでしょう。

asm.js で詰まったポイント

仕様を軽く読んだだけでは覚えきれず、詰まったポイントが幾つかあったので詰まった現象と対処法を書いておきます。 型関係のエラーは大体言われてすぐ気がつくので省略します。

32bit整数同士の掛け算が * 演算子で行えない

具体的には

TypeError: asm.js type error: one arg to int multiply must be a small (-2 ^ 20, 2 ^ 20) int literal

というエラーの場合、asm.js の仕様 に書いてあるように Math.imul を使いましょう。

Uint8Array, Int8Array 以外のヒープのビューにアクセスするときにエラーが出る

具体的には

TypeError: asm.js type error: index expression isn't shifted; must be an Int8/Uint8 access

というエラーです。

asm.js の仕様 によると index が数値ではなく expression の時は右シフトしなくてはならないので、 array[index << 2 >> 2] のようにしましょう。 (この仕様は正直通常のJSで遅くなるのでツライ)

大きなヒープで何度も計算すると素のJSよりも遅くなる

asm.js では function の引数などに配列を使うことはできません。 では、どうするかというと最初に Heap (ArrayBuffer) を asm.js コードに渡してやり、その中で Uint8Array などでビューを作ってやり、自分でメモリの構造を決め、asm.js 内の各 function では index と length を使ってここからここまでは何々の配列として扱う、みたいなことをします。

CRC-32 の計算では事前計算テーブルとデータという2つの配列を扱わなくてはならないため、この2つの配列を結合するあたらしい ArrayBuffer を作り、それを heap として asm.js のコードを呼んでいました。 このときのヒープの構造は 0-1023 バイトまでは事前計算テーブル(32bit*256個)、1024 バイト以降は CRC-32 に渡すデータとして扱う、という形にしました。

なお、この際

var table = new stdlib.Uint32Array(heap, 0, 256);
var data = new stdlib.Uint8Array(heap, 1024);

のようにビューでわかりやすくすればいいのでは、と思ってやってみたところ asm.js では許されていませんでした。(コンストラクタの引数は heap のみの一つだけ、と言われます) TypedArray#subarray などのメソッドも使えないので素直に先頭からの index でアクセスしましょう。

こうして、配列の CRC-32 ハッシュ値を求めようとする際に、毎回テーブル+データのヒープを作ってasm.jsに渡す素直な実装が出来たわけですが、当然 ArrayBuffer の作成と(計算が行われた後は使わなくなるため)破棄が行われ、何度も実行していると GC が大量に発生することになり、asm.js 化する前より性能が落ちたりします。

function crc32_asm(data) {
  var table = new Uint32Array([
    // CRC-32 の事前計算テーブル
    ...
  ]);

  function asm(stdlib, foreign, heap) {
    "use asm";

    var heapUint32 = new stdlib.Uint32Array(heap);
    var heapUint8  = new stdlib.Uint8Array(heap);

    function calc(pos, length) {
      // CRC-32 の計算をして返す
    }


    return {
      calc: calc
    }
  }

  // 事前計算テーブルとCRC-32を求めたい配列の結合
  var tableUint8Array = new Uint8Array(table.buffer);
  var dataLength = tableUint8Array.length + data.length;
  var heapSize = 1 << 8;
  while (dataLength  > heapSize) {
    heapSize <<= 1;
  }
  var heap = new ArrayBuffer(heapSize);
  var heapUint8Array = new Uint8Array(heap);

  heapUint8Array.set(tableUint8Array);
  heapUint8Array.set(data, tableUint8Array.length);

  // asm.js にヒープを渡し、返ってきた calc 関数に引数を渡しそのまま実行 
  return asm(self, {}, heap).calc(0, data.length) >>> 0;
}

Web ブラウザの開発ツールでプロファイルを取ったところ、GC が支配的になっていることに気づいたので、ArrayBuffer の作成を最低限に抑えるようにしました。

具体的には、asm.js コード全体を呼び出すのは現在のヒープサイズでは足りない際に、ArrayBuffer を倍の長さで作り直した時だけで、それ以外は以前のヒープに TypedArray#set でデータを上書きし、 asm.js コードの実行によって得られた function によってハッシュ値を計算するようにしました。

function crc32_asm() {
  var table = new Uint32Array([
    // CRC-32 の事前計算テーブル
    ...
 ]);

  function asm(stdlib, foreign, heap) {
    "use asm";

    var heapUint32 = new stdlib.Uint32Array(heap);
    var heapUint8  = new stdlib.Uint8Array(heap);

    function calc(pos, length) {
      // CRC-32 の計算をして返す
      ...
    }

    return {
      calc: calc
    }
  }

  function calcBufferSize(data) {
    return 1024 + data.length;
  }

  var tableUint8Array = new Uint8Array(table.buffer);
  var heapSize = 1 << 16;
  var heap;
  var heapUint8Array;
  var asmFunctions;

  function init() {
    update(new Uint8Array(0));
  }

  // バッファの拡張と事前計算テーブルをセットして asm.js を実行し直す
  function update(data) {
    var requireBufferSize = calcBufferSize(data);

    while (requireBufferSize > heapSize) {
      heapSize <<= 1;
    }

    heap = new ArrayBuffer(heapSize);
    heapUint8Array = new Uint8Array(heap);

    heapUint8Array.set(tableUint8Array);
    asmFunctions = asm(self, {}, heap);
  }

  function calc(data) {
    // 現在のヒープサイズで足りないときだけ、asm.js を実行し直す
    if (calcBufferSize(data) > heapSize) {
      update(data);
    }

    // データを heap にセットする
    heapUint8Array.set(data, 1024);

    return asmFunctions.calc(0, data.length) >>> 0;
  }

  init();

  return {
    calc: calc
  };
}

複数の配列を扱いたいという場合はわりとよくあると思うので、このバッファの使い回しは asm.js では基本となると思います。

また、私見ですがこのバッファの使い回しをすすめていくと、Webアプリケーション全体をプロセスとみなし、このバッファがプロセス内のデータセグメントとスタックセグメントのようになるのではないかと思います。 どういうことかというと、Webアプリケーション内全体で一度に大きな ArrayBuffer を確保し、asm.js で使用する変数や配列などをこの ArrayBuffer の中で割り当てていくメモリ管理コードを持つようになるということです。 このとき、長く使いそうなものは上から、一時的なものは下から積み上げていく、つまりプロセスにおけるデータセグメント内のヒープ領域とスタックセグメントのような形が考えられます。 そして、ヒープ領域の拡張時に断片化の解消などを含むメモリ管理の仕組みを再実装していくことになるのではないかと思います。

実際、Emscripten における runtime.js がそのような仕組みになっています。これは Emscripten が他言語で書かれたアプリケーションを動かすのを目的としているので、既存のプロセスのメモリ管理に相当する実装があるのは当然かも知れません。

つまり、人の手による温かみのある asm.js とは最終的にはほぼ Emscripten と同じようなコードになり、 asm.js の手書きとは人間 Emscripten になることであり、人権が失われ機械として生きていくということです。

zlib.js 0.3.0 リリース

致命的なバグの修正

HLIT と HDIST のデコードに関するバグ修正

Inflate において、リテラルと長さ符号(HLIT)と距離符号(HDIST)の展開において不具合があったため、Inflate に失敗あるいは正しくないデータになってしまうことがありました。 これはどういうことかと言うと、HLIT と HDIST は連続して格納されていますが、その中で同じ符号が連続する場合は繰り返しを行う処理があります。 0.2.0 までの実装では、HLIT と HDIST をそれぞれ別の配列として扱っていたため、 HLIT と HDIST をまたぐような繰り返し符号が出現していた際、誤ったデータが展開されてしまっていました。

0.3.0 では HLIT と HDIST の展開を連続する配列として展開し、その後のハフマン符号テーブルを構築する際に HLIT と HDIST を分離して行うようにしています。

仕様でいうと RFC1951 の 3.2.7 にある以下の部分を誤って実装していたということです。

The code length repeat codes can cross from HLIT + 257 to the
HDIST + 1 code lengths.  In other words, all code lengths form
a single sequence of HLIT + HDIST + 258 values.

不正な Deflate データによる無限ループの修正

0.2.0 までは細工された Deflate データを伸長しようとすると、無限ループに陥る場合がありました。 ハフマン符号を使ってリテラル・長さ符号と距離符号を取得する際、ハフマン符号のコード長が不正になっており、無限に読み込もうとして無限ループに陥ってました。

0.3.0 ではコード長をチェックして明らかに不正な場合、例外を投げるように修正しました。

その他のバグ修正

PKZIP 作成時、余計な領域が後ろに残っているバグの修正

0.2.0 までは PKZIP の作成を行うと、後ろに余計な領域が残っており、厳密なアーカイバで展開しようとすると「データのペイロード後にデータが存在します」という警告が出ていました。 これは "End of central directory record" のサイズ計算が誤っていて、余分にバッファを確保してしまうせいです。

https://pkware.cachefly.net/webdocs/casestudies/APPNOTE.TXT の 4.3.16 にある通り、22 が正しいサイズです。

このバグと修正方法についてはzlib.js 0.2.0のzip.js/zip.min.jsのバグの修正[ZIPファイルの破損]によって報告されていました。 @TakeshiOkamoto さん、ありがとうございました。

ビルド・テスト環境の変更

Ant によるビルドと BusterJS によるテストから、 Grunt によるビルドと Karma + mocha + power-assert によるテストに変更しました。 Grunt にする作業自体はだいぶ前に行っていたのですが、すでに時代遅れになっている気もするのでさらに変更するかもしれません…。

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