明日から使えるasm.js - Low Level JavaScript - 「LLJS」 マイナー言語アドベントカレンダー・一日目

この記事は、マイナー言語 Advent Calendar 2013 - Qiita [キータ] の1日目です。

今日は、当初 Terraを予定していたのですが、昨日時点の最新版がLLVM3.3でビルドできなかったので面倒くさくなって、趣味と実益を兼ねて Low Level JavaScript, LLJSの話をしたいと思います。

LLJSとは

JavaScriptにコンパイルされるAltjsの一種ですが、ただのJSトランスレータとは一線を画します。名前の通りローレベルの操作を行えます。

LLJS : Low-Level JavaScript

何を持ってローレベルなのか？というのは公式ページから引っ張ってきた次のサンプルコードを見たほうが早いと思います。

// Import malloc. The casting is annoying -- we don't have a good
// story for typed imports yet.
typedef byte *malloc_ty(uint);
let malloc_ty malloc = (malloc_ty)(require('memory').malloc);

// Allocate an int on the heap using new.
let int *y = malloc(sizeof(int));
trace(y);

// Alternate, more convenient syntax.
let int *x = new int;
trace(x);

楽しい感じがしてきましたね。このようにシンボルに対する型指定が必須な、ヒープやポインタを扱える言語なっています。

追記：　紹介したのはいいんですが、上のコードは最新版だと記法変わってて動かない気がします

HelloWorld!

簡単な例から入りましょう。とりあえず書いてみた簡単なアッカーマン関数の一例です。普通ですが。

function int ack (int m, int n) {
  if (m === 0) {
    return n+1;
  } else if (n === 0) {
    return ack(m-1, 1);
  } else {
    return ack(m-1, ack(m, n-1))
  }
}

まだ普通の感じがしますね。たぶん数値計算しかしていないからでしょうが。
(これは僕のせいでもlljsのせいでもないんですが、m > 4 でコールスタック使いきって死にました。)

これを ljcでコンパイルすると以下のようになります。

function ack(m, n) {
  if (m === 0) {
    return n + 1 | 0;
  } else if (n === 0) {
    return ack(m - 1 | 0, 1);
  } else {
    return ack(m - 1 | 0, ack(m, n - 1 | 0));
  }
}

n | 0 はJavaScriptでintを表すイディオムですね。
このように低レベルで速度やメモリ操作を要求される箇所で、細かく制御できたり、特殊な最適化を施した関数を書けるというわけです。

LLJS to asm.js

上で見たイディオムは、どこかでみたことがあると思いませんか？そう、asm.jsです。

最近ではGoogleがasm.jsをサポートすることが話題になっていました。これでFirefoxだけの独自規格ではなく、Google/Firefoxという「一般的な」ご家庭のブラウザで高速なJavaScriptが実行可能ということになります。都合により政治的な表現をしております。

最新バージョンのChrome 31とOpera 18、asm.jsとWebGLで高速実行を実現。Unreal Engine 3対応に － Publickey

で、LLJSにはasm.jsを出力できるフォークがあり、今日本当に紹介したいのはそっちです。
jlongster/LLJS

実はlljsはマイナビニュースで紹介された記事で触れられてはいたのですが、記事中にlljsのコードサンプルはなく、実際に手元で動かした方は少ないのではないでしょうか。
LLJS/asm.jsにみる高性能プログラミング、Firefox | マイナビニュース

このフォークは僕が試した限りでは http://mbebenita.github.io/LLJS/ のドキュメント通りには全然動かなくて(マイナー言語ならドキュメントはメンテされなくて当然)、verlet積分を実装したこのコードの方が参考になります。

こいつは [e-mail]:jlongster/LLJS.git のヘッドでコンパイルできます。少なくとも今日は出来ました。明日は出来るんでしょうか。

物理エンジンのデモ Cloth with LLJS/asm.js 上のニュースで紹介されてるやつですね
そのコードはこちら jlongster/lljs-cloth

中身を見てみる

元のブランチはpackage.jsonが提供されてなくてbin/ljcを叩くのが面倒だったので、簡単に試すためにコマンドインストール用package.jsonを加えた版をForkしときました。

$ git clone https://github.com/mizchi/LLJS.git
$ cd LLJS
$ npm install -g
$ ljc
ljc: [option(s)] file

Options:
  -a  --asmjs           Compile as asm.js module
  -m  --module-name     Export asm module as this name
  -e  --exported-funcs  Functions to export from the asm module (comma-delimited)
  -E  --only-parse      Only parse
  -A  --emit-ast        Do not generate JS, emit AST
  -P  --pretty-print    Pretty-print AST instead of emitting JSON (with -A)
  -b  --bare            Do not wrap in a module
  -W  --warn            Print warnings (enabled by default)
  -Wconversion          Print intra-integer and pointer conversion warnings
  -0  --simple-log      Log simple messages. No colors and snippets.
  -t  --trace           Trace compiler execution
  -o  --output          Output file name
  -h  --help            Print this message
  -w  --nowarn          Inhibit all warning messages

準備も整ったとところで、$ ljc --asmjs verlet.ljs した結果の要所を覗いて、雰囲気を掴んでみましょう

とりあえず元のコードと出力コードをgistにあげておきました。 https://gist.github.com/mizchi/7729609

では、コンパイルされた中身をちょっと覗いてみましょう。

var asm = (function (global, env, buffer) {
    "use asm";

    var stackSize = env.STACK_SIZE|0;
    var heapSize = env.HEAP_SIZE|0;
    var totalSize = env.TOTAL_SIZE|0;

    var print = env.print;
var currentTime = env.currentTime;

    var U1 = new global.Uint8Array(buffer);
    var I1 = new global.Int8Array(buffer);
    var U2 = new global.Uint16Array(buffer);
    var I2 = new global.Int16Array(buffer);
    var U4 = new global.Uint32Array(buffer);
    var I4 = new global.Int32Array(buffer);
    var F4 = new global.Float32Array(buffer);
    var F8 = new global.Float64Array(buffer);

    var acos = global.Math.acos;
    var asin = global.Math.asin;
    var atan = global.Math.atan;
    var cos = global.Math.cos;
    var sin = global.Math.sin;
    var tan = global.Math.tan;
    var ceil = global.Math.ceil;
    var floor = global.Math.floor;
    var exp = global.Math.exp;
    var log = global.Math.log;
    var sqrt = global.Math.sqrt;
    var abs = global.Math.abs;
    var atan2 = global.Math.atan2;
    var pow = global.Math.pow;
    var imul = global.Math.imul;

"use asm"; 宣言ですね。どうやらArrayBufferを使ってメモリ領域をを準備している様子です。

どうやらこの作者、元の --asmjsオプション付けない時の互換性あんまり意識してないので、--asmjsつけないときのコードにasm用コードが一部混ざって壊れてました。まああんまり気にしないことにします。

次に、そのメモリ領域を使ってる部分を見てみましょう。

function distPointToLine(x, y, p1, p2) {
  x = +x;
  y = +y;
  p1 = p1 | 0;
  p2 = p2 | 0;
  var _ = 0.0, _$1 = 0.0, _$2 = 0.0, A = 0, B = 0, lenA = 0.0, lenB = 0.0, det = 0.0, bool = 0, C = 0, $SP = 0;
  U4[1] = (U4[1] | 0) - 24 | 0;
  $SP = U4[1] | 0;
  F4[(($SP)) >> 2] = +(+(+F4[(p1) >> 2]) - +x);
  F4[((($SP)) + 4 | 0) >> 2] = +(+(+F4[((p1) + 4 | 0) >> 2]) - +y);
  F4[(($SP) + 8 | 0) >> 2] = +(+(+F4[(p2) >> 2]) - +(+F4[(p1) >> 2]));
  F4[((($SP) + 8 | 0) + 4 | 0) >> 2] = +(+(+F4[((p2) + 4 | 0) >> 2]) - +(+F4[((p1) + 4 | 0) >> 2]));
  lenA = +(+(+F4[(($SP)) >> 2]) * +(+F4[(($SP)) >> 2]) + +(+F4[((($SP)) + 4 | 0) >> 2]) * +(+F4[((($SP)) + 4 | 0) >> 2]));
  lenB = +(+(+F4[(($SP) + 8 | 0) >> 2]) * +(+F4[(($SP) + 8 | 0) >> 2]) + +(+F4[((($SP) + 8 | 0) + 4 | 0) >> 2]) * +(+F4[((($SP) + 8 | 0) + 4 | 0) >> 2]));
  if (+lenA > +lenB) {
    return +(_ = +1000, U4[1] = (U4[1] | 0) + 24 | 0, _);
  }
  det = +(+-+F4[(($SP)) >> 2] * +(+F4[(($SP) + 8 | 0) >> 2]) + +-+F4[((($SP)) + 4 | 0) >> 2] * +(+F4[((($SP)) + 4 | 0) >> 2]));
  bool = +(+det) < +(+(+0));
  if (+det > +lenB) {
    bool = 1;
  }
  if (bool) {
    F4[(($SP) + 16 | 0) >> 2] = +(+(+F4[(p2) >> 2]) - +x);
    F4[((($SP) + 16 | 0) + 4 | 0) >> 2] = +(+(+F4[((p2) + 4 | 0) >> 2]) - +y);
    return +(_$1 = +(min(~~lenA, ~~(+(+F4[(($SP) + 16 | 0) >> 2]) * +(+F4[(($SP) + 16 | 0) >> 2]) + +(+F4[((($SP) + 16 | 0) + 4 | 0) >> 2]) * +(+F4[((($SP) + 16 | 0) + 4 | 0) >> 2]))) | 0 | 0), U4[1] = (U4[1] | 0) + 24 | 0, _$1);
  }
  det = +(+(+F4[(($SP) + 8 | 0) >> 2]) * +(+F4[((($SP)) + 4 | 0) >> 2]) - +(+F4[((($SP) + 8 | 0) + 4 | 0) >> 2]) * +(+F4[(($SP)) >> 2]));
  return +(_$2 = +(+det * +det / +lenB), U4[1] = (U4[1] | 0) + 24 | 0, _$2);
  U4[1] = (U4[1] | 0) + 24;
  return 0.0;
}

ヒープを操作している様子です。全然わからないですね。だいぶヤバ…盛り上がってきました。

コンパイル前のverlet.ljsのコードを見てみると、それなりに簡略なコードでかけていることがわかります。

function float distPointToLine(float x, float y, Vec2d *p1, Vec2d *p2) {
    let Vec2d A;
    A.x = p1->x - x;
    A.y = p1->y - y;
    let Vec2d B;
    B.x = p2->x - p1->x;
    B.y = p2->y - p1->y;

    let float lenA = A.x * A.x + A.y * A.y;
    let float lenB = B.x * B.x + B.y * B.y;

    // It can't intersect if it's too far away
    if(lenA > lenB) {
        return 1000.0;
    }

    let float det = (-A.x * B.x) + (-A.y * A.y);

    // LLJS doesn't support logical operators yet
    let int bool = det < float(0.0);
    if(det > lenB) {
        bool = 1;
    }

    if(bool) {
        let Vec2d C;
        C.x = p2->x - x;
        C.y = p2->y - y;
        return min(lenA, C.x * C.x + C.y * C.y);
    }

    det = B.x * A.y - B.y * A.x;
    return (det * det) / lenB;

}

これは独特な雰囲気がありつつも読めなくはないですね。覚えるべきことも少なそうです。記法がJSのC言語といった趣です。

このようにasm.jsは人間が手で書くものではないことがわかります。で、結局静的型付け言語から生成したほうがマシなので、ある程度以上の規模で速度が必要な物は、結局Emscripten等が流行りつつあるといった感じです。

で、肝心の速度としては、上記のlljs-clothはasm.jsの恩恵で2.5倍ほど高速化しているようです。吐出されるコードも、ヒープ操作以外はEmscriptenが吐くほどはおぞましい感じではないので、asm.jsにしては「それなり」の可読性があります。

どうやって使うか

比較的カジュアルに高速に動作するかもしれない関数(本当に速くなったかは要ベンチですが)を書くことが可能なので、ピンポイントに運用することはできるでしょう。たとえばゲームならば経路探索や物理エンジンをlljsで書くとかそういう用途が考えられます。

まとめ

ということで、初日なのでそれなりに頑張って書いてみたんですが、ちょっと書きすぎました。このカレンダー、深夜に思いつきで適当に作った割には人が集まったほうなのですが、まだ人埋まってないので、一芸がある方は是非ご参加を。

マイナー言語 Advent Calendar 2013 - Qiita [キータ]

マイナー言語といえば、僕はCeylonのカレンダーの方も気になってます。