document

HTML5 & JavaScript side
twitter: @y_imaya

Emscripten によって生成された asm.js 対応コードは本当に人間が書いたコードより速いのか?

はじめに

先日、いつものように Twitter 監視業務に勤しんでいたところ、下記のような発言を見かけました。

なるほど、機械によって生成された asm.js 対応のコードはどんなブラウザでも速いよという主張です。
自分は JavaScript で高速に動作するように注意して書いた zlib.js というのを作っていたので、zlib の展開処理でこの発言が本当か試してみることにしました。
zlib の展開処理というのは asm.js に向いていそうな処理ですし、ちょうど良いベンチマークになると思います。

zlib-asm vs zlib.js

比較には asm.js の zlib 実装として @ukyo さんの zlib-asm を採用しました。
ほかの zlib を Emscripten でビルドする系のプロジェクトはベンチマークコードも一緒に Emscripten でビルドしていて、ライブラリとしての単体利用が面倒くさそうだったからです。
その他、zlib-asm では Emscripten の生成したデフォルト状態のコードで遅い部分を最適化していて、もっとも良さそうな感じがしました。
(最初は asm.js が type error になって有効になっていなかったり最適化されていなかったのですが、連絡したらすぐに対応していただけました。ありがとうございます。)

zlib-asm 補足

zlib-asm は zlib のそのままのビルドではなく、zpipe という入出力を圧縮、展開するソフトウェアの Emscripten ビルドです。

zlib.js 補足

zlib.js は zlib の移植ではなく、JavaScript で(それなりに)高速に、ファイルサイズが小さくなるように開発しているライブラリです。
つまり、ここでの比較は zlib という仕様には従っているがまったく異なる実装の速度比較ということになります。

比較結果

比較用のページを用意しました。
手元の環境で実行した結果も貼っておきますが、自分でベンチマーク用のコードを見て実行してみるのが一番正確です。

Chrome 31

Filename Size Compressed zlib-asm
(Emscripten)
zlib.js
Author: imaya
alice29.txt148,48153,63420.55 ms10.76 ms
asyoulik.txt125,17948,8973.12 ms4.28 ms
cp.html24,6037,9611.06 ms0.46 ms
fields.c11,1503,1220.42 ms0.22 ms
grammar.lsp3,7211,2220.35 ms0.11 ms
kennedy.xls1,029,744203,99222.06 ms12.56 ms
lcet10.txt419,235143,1069.72 ms10.67 ms
plrabn12.txt471,162193,73015.06 ms10.04 ms
ptt5513,21656,4657.32 ms6.43 ms
sum38,24012,9901.23 ms0.64 ms
xargs.14,2271,7361.43 ms0.12 ms

Firefox 25

Filename Size Compressed zlib-asm
(Emscripten)
zlib.js
Author: imaya
alice29.txt148,48153,6342.58 ms6.61 ms
asyoulik.txt125,17948,8971.72 ms4.69 ms
cp.html24,6037,9611.68 ms0.72 ms
fields.c11,1503,1220.55 ms0.27 ms
grammar.lsp3,7211,2220.42 ms0.15 ms
kennedy.xls1,029,744203,9927.01 ms16.51 ms
lcet10.txt419,235143,1065.21 ms7.7 ms
plrabn12.txt471,162193,7305.42 ms10.87 ms
ptt5513,21656,4653.05 ms5.2 ms
sum38,24012,9900.86 ms0.83 ms
xargs.14,2271,7360.46 ms0.41 ms

Safari 7.0

Filename Size Compressed zlib-asm
(Emscripten)
zlib.js
Author: imaya
alice29.txt148,48153,63416 ms4 ms
asyoulik.txt125,17948,8974 ms4 ms
cp.html24,6037,9611 ms1 ms
fields.c11,1503,1221 ms1 ms
grammar.lsp3,7211,2221 ms1 ms
kennedy.xls1,029,744203,99224 ms17 ms
lcet10.txt419,235143,10613 ms9 ms
plrabn12.txt471,162193,73016 ms11 ms
ptt5513,21656,4656 ms5 ms
sum38,24012,9902 ms1 ms
xargs.14,2271,7360 ms1 ms

傾向

asm.js が有効になっていないブラウザ(Chrome, Safariなど)では zlib.js が有利な結果になり、asm.js が有効になっているブラウザ(Firefox)では zlib-asm が有利な結果となりました。

まとめ

人間が書いた JavaScript でも機械の生成した asm.js 用のコードより速くなることもある。
あるいは、自分は人間ではなかった。

今回は人間で書いたコードのほうがasm.js非対応な環境では速くなることがありましたが、Emscriptenが出力するコードにはまだ非効率な部分が残っているため、これからもこの状況が続くとは限りません。
今後も見守っていこうと思います。

Canvas でカラーハーフトーン

はじめに

ネット上で Photoshop にはカラーハーフトーンというフィルタがあることを知って、面白そうなので実装してみました。
適当にググってカラーハーフトーンフィルタを使った画像を見ながら「多分こういうものだろう」と考えて実装したものなので Photoshop のものとは大きく異なる可能性があります。

カラーハーフトーンってなに

元々は網点という印刷まわりの技法のようですが、Photoshop のものは完全に画像の効果としてあつかった方が良いみたいです。
ネットで使用例を見た感じ、各色ごとに指定された角度の正方形に画像を分割して、色の多いところは大きく、少ないところは小さく円を描いて水玉模様みたいにする効果だと思います。

実装1: 独自実装(わりとゴリ押し)

(0, 0) から角度と正方形のサイズから dx, dy を計算してそれを加算していきます。
走査の改行は 90 度回転させた角度で同じように計算します。
この場合、斜めに進んで行くので Y 方向に加算していくだけでは走査に漏れが発生するため、X 方向に進ませた時 Y が 0 以下のときは Y を負の方向に進ませてみて描画できそうなら描画してさらに負の方向にすすませるということをしています。

scanline

描画すべきかどうかは、四隅の点のどれかが描画領域にはいっているかどうかで判定しています。

実装2: 行列を使った変換

回転行列を使って、全てのピクセルを矩形サイズで割った大きさの画像に縮小&回転させた画像に変換し、そこから元の大きさ・角度に逆変換することで上記のような走査ではなく、適切に処理できると考えました。

実際にやってみたところ、変換時に角度によっては微妙にピクセルがずれ、それを戻すと割と目立つ違いになってしまうので微妙な感じになってしまいました。
うまく変換する方法を思いつくまでこちらの方法はひとまず置いておこうと思います。

half

各色毎に回転・縮小して…

inverse

逆行列で元にもどします。

行列の計算は goog.math.Matrix という Closure Library のコードを使っています。

実装例

jsdo.it に置いておきました。
事前にグレイスケール化や二値化するフィルタをかけたり、カラーハーフトーンが終わった後に特定の色で塗りつぶしたりできるようになってます。

まとめ

Canvas + JavaScript は画像加工ツール

Canvasできれいな色相環を描画する

はじめに

JavaScript で Canvas を使っていると、HSV の Color Picker とか作りたくなって色相環を描画したくなることがよくあるとおもいます。
ここでは、自分の行っている色相環の描画方法を説明します。

準備

色相を扱うのために HSV 色空間を使います。HSV から RGB への変換は以下の function を用います。

function hsvToRGB(hue, saturation, value) {
    var hi;
    var f;
    var p;
    var q;
    var t;

    while (hue < 0) {
        hue += 360;
    }
    hue = hue % 360;

    saturation = saturation < 0 ? 0
        : saturation > 1 ? 1
        : saturation;

    value = value < 0 ? 0
        : value > 1 ? 1
        : value;

    value *= 255;
        hi = (hue / 60 | 0) % 6;
        f = hue / 60 - hi;
        p = value * (1 -           saturation) | 0;
        q = value * (1 -      f  * saturation) | 0;
        t = value * (1 - (1 - f) * saturation) | 0;
    value |= 0;

    switch (hi) {
        case 0:
            return [value, t, p];
        case 1:
            return [q, value, p];
        case 2:
            return [p, value, t];
        case 3:
            return [p, q, value];
        case 4:
            return [t, p, value];
        case 5:
            return [value, p, q];
    }

    throw new Error('invalid hue');
}

距離で判別する

まず最初に思いつくのが、以下のような方法でしょう。

  1. x, y から中心となる点までの距離を計算する (三平方の定理)
  2. 距離が円の範囲内ならば、中心までの角度を計算する (Math.atan2)
  3. 角度から色相を計算し、RGBに変換して描画する

1の距離の計算ですが、距離の比較にしか使わないため、平方根を取らずに半径を二乗する事で高速化してもよいですね。
ただし、この場合アンチエイリアスなどがかからず、端の方がギザギザになってしまいます。

これを JavaScript で書くと以下のようなコードになります。

var width = 300;
var height = 300;
var canvas = document.createElement("canvas");
var ctx = canvas.getContext("2d");

canvas.width = width;
canvas.height = height;
document.body.appendChild(canvas);

// 円の外側の距離
var r1 = Math.min(canvas.width, canvas.height) / 2;
// 円の内側の距離
var r2 = r1 - 30;
// 中心
var cx = canvas.width / 2;
var cy = canvas.height / 2;

var imageData = ctx.getImageData(0, 0, width, height);
var pixelArray = imageData.data;

for(var x = 0; x < width; x++) {
    for(var y = 0; y < height; y++) {
        var d = (- cx) * (- cx) + (- cy) * (-cy);

        if(< r1 * r1 && d > r2 * r2) {
            var baseIndex = (* width + x) * 4;
            var hue = Math.atan2(- cx, y - cy) / Math.PI / 2 * 360;
            var color = hsvToRGB(hue, 1, 1);

            pixelArray[baseIndex  ] = color[0];
            pixelArray[baseIndex+1] = color[1];
            pixelArray[baseIndex+2] = color[2];
            pixelArray[baseIndex+3] = 255;
        }
    }
}

ctx.putImageData(imageData, 0, 0);

一度円を描画してアルファ値で描画対象か判別する

自分はこのギザギザが許せなかったので何か良い方法がないか考えたところ、一度適当な色の円を書いて、その場所に色を上書きしていく方法を思いつきました。

var width = 300;
var height = 300;
var canvas = document.createElement("canvas");
var ctx = canvas.getContext("2d");

canvas.width = width;
canvas.height = height;
document.body.appendChild(canvas);

// 円の外側の距離
var r1 = Math.min(canvas.width, canvas.height) / 2;
// 円の内側の距離
var r2 = r1 - 30;
// 中心
var cx = canvas.width / 2;
var cy = canvas.height / 2;

// 円を描く
ctx.arc(cx, cy, r1, 0, Math.PI * 2, true);
ctx.arc(cx, cy, r2, 0, Math.PI * 2, false);
ctx.fill();

そして、その描画された部分のアルファ値を見て色を上書きします。

var imageData = ctx.getImageData(0, 0, width, height);
var pixelArray = imageData.data;

for(var x = 0; x < canvas.width; x++) {
    for(var y = 0; y < canvas.height; y++) {
        var baseIndex = (* width + x) * 4;

        // 透明でなければ上書きする
        if(pixelArray[baseIndex + 3] > 0) {
            var hue = Math.atan2(- cx, y - cy) / Math.PI / 2 * 360;
            var color = hsvToRGB(hue, 1, 1);

            pixelArray[baseIndex  ] = color[0];
            pixelArray[baseIndex+1] = color[1];
            pixelArray[baseIndex+2] = color[2];
        }
    }
}

ctx.putImageData(imageData, 0, 0);

パフォーマンス

どちらの方法も手元の Chrome 28, Firefox 23 だと 9-14ms 程度だったので性能的な違いはあまりないと思います。

追記: 2013/08/16

CanvasRenderingContext2D#arc の endAngle を Math.PI * 2 より大きい整数である 7 としていましたが、Math.PI * 2 を超える値の扱いが safari でおかしくなるため、Math.PI * 2 に修正しました。

あとから線の編集が可能なお絵描きツールの描画高速化

はじめに

2010 年くらいからのんびり開発している趣味のお絵かきツール Diceros の実装について、ドキュメントを残しておいたほうがよさそうなのでこの文章を書きます。
まだ未完成ですが、お絵描きツールは以下の URL で開発バージョンを触ることができます。IE10+, Google Chrome 17+ あたりで動作すると思います。Wacom のペンタブレットプラグイン(MouseEvent)、Android Chrome(TouchEvent)、IE10(PointerEvents) あたりの筆圧に対応してます。 

しばらく触るとわかると思うのですが、このお絵描きツールは(VectorLayer/SVGLayerでは)一度書いた線をあとから調整することができるようになっています。

一度描いた線の再描画が多い

Diceros では描いた線を後から編集することができるため、それぞれの線を個別に保持しておかなくてはいけません。
個別の線をそれぞれ専用のオフスクリーンバッファ(DOMツリーから分離されているCanvas)に描画しても良いのですが、バウンディングボックスなどで極力小さくなるようにしても莫大な量のメモリを消費してしまいますし、余白部分が多いので描画自体もあまりはやくありません。
そこで、Diceros では描画命令を記録しておく方法を採用し、再描画処理を高速に行うように工夫しています。

描画命令を保存する

Diceros では高速化のため CanvasRenderingContext2D の一部メソッドと同じインターフェースを持った別のオブジェクトに保存しています。
再描画のたびに描画に(制御点の位置など)必要な情報を計算しなおすのはムダなため、描画命令自体をフックして覚えておこうという作戦です。

また、これは当初想定していなかったのですが、Canvas の他にも SVG で描画するのも中間形式から変換するだけなので簡単に実装することができました。

中間形式のデータはとても簡単になっていて、以下の様な Array で実装されています。

[[メソッドID], [メソッドの引数の数], [引数1], [引数2], ... ]

fillStyle のようなプロパティも Object.defineProperty で setter を設定して、この配列に入るようになっています。

線の編集

線の編集では、編集中の動作を重くしないために以下の三つのオフスクリーンバッファに描画したあと、結合しています。

  • 編集中の線より前の線
  • 編集中の線
  • 編集中の線より後ろの線

diceros_line_layer

ここで重要なのは、頻繁に再描画されるのは「編集中の線」だけで、それ以外は一度描画したらあとはそのまま再利用できる点です。

編集中の前後の線の再描画

編集前後の線は、(線の編集中は)めったに更新されないため "function 生成" というテクニックを使うことで高速化することができます。
なぜ高速になるのか、簡単な例で説明します。

たとえば、上記の中間形式を描画させようとしたら以下のようなコードになると思います。

function draw(ctx) {
    // 描画命令の中間形式配列
    var codeArray = [...];
    // メソッドID から メソッド名への変換テーブル
    var codeToName = [...];
    // CanvasRenderingContext2D のメソッド名
    var method;
    // 引数の個数
    var argnum;

    for (var i = 0, il = codeArray.length; i < il; ++i) {
        // メソッド ID からメソッド名への変更
        method = codeToName[codeArray[i++]];
        // 引数の個数の取得
        argnum = ctx[codeArray[i++]];
        // メソッドの実行
        ctx[method].apply(ctx, codeArray.slice(i, i += argnum));
    }
}

これを function 生成するコードにすると以下のようになります。

function createDrawFunction() {
    // 描画命令の中間形式配列
    var codeArray = [...];
    // メソッドID から メソッド名への変換テーブル
    var codeToName = [...];
    // CanvasRenderingContext2D のメソッド名
    var method;
    // 引数の個数
    var argnum;
    // 生成される function の中身
    var functionBody = [];

    for (var i = 0, il = codeArray.length; i < il; ++i) {
        // メソッド ID からメソッド名への変更
        method = codeToName[codeArray[i++]];
        // 引数の個数の取得
        argnum = ctx[codeArray[i++]];
        // メソッド呼び出しを作成
        functionBody.push(
            "ctx." + method + "(" + codeArray.slice(i, i += argnum).join(',') + ')'
        );
    }

    return new Function("ctx", functionBody.join('\n'));
}

これを実行すると、例えば以下のような function が生成されます。

function(ctx) {
    ctx.beginPath();
    ctx.moveTo(0,0);
    ctx.lineTo(50,50);
    ctx.lineTo(100,100);
    ctx.closePath();
    ctx.fill();
}

このように、中間形式を使わず純粋に描画するためだけの function が作成されます。
この生成された function は配列やループ、変数の参照など、描画命令以外の余計な処理が一切入らないのでかなり高速に動作します。

編集中の線の再描画

編集中の線の再描画は、頻繁に更新されるため、小細工を加える余地がすくないです。
中間形式を用いてそのまま描画しています。
上記の function 生成を利用しないのは、編集中の線は「変更=再描画」となるので function を生成するメリットがないからです。
(むしろ、function を生成するコスト分だけ損になります。)

その他

紀平さんが Chrome+HTML5 Developers Live Japan #5 で function 生成についてライブコーディングしながら説明しているので、より丁寧な説明が必要な方は参考になると思います。

Web Audio API で Sound Font を使った標準 MIDI ファイルの再生

はじめに

Google Chrome では Web Audio API という API を使って音を鳴らすことができます。
今回、これをつかって Sound Font を使った標準 MIDI ファイル(以下 SMF と表記)のプレイヤーを作ってみました。
なお、仕様の具体的な話しなどはほとんどしません。
音楽的な知識などもほとんどないため、何かおかしなことをしていたらご指摘いただけるとありがたいです。

また、今回の実装はあくまでも実験・検証用のものなので実用にはまだ手を加えなくてはいけないところが多いため、もし利用としようと思う方がいたらそこは注意してください。
動作環境は PC 版の Google Chrome のみです。
現在開催中の Google I/O で Chrome for Android でのサポートも明言されたそうですので、そのうち Android でも利用可能になるかも知れません。

もう少し完成度たかめてから公開しようかとも思っていたのですが、旬の話題みたいなのでビッグウェーブに乗ろうと思います。

デモ

以下のページで公開しています。
サウンドフォント(約10MB)のダウンロードがあるのでロードが終わるまでは気長に待ってください。

構成

まず、大きく分けて SMF を扱う部分と Sound Font を扱う部分に分かれます。
そして、この二つの部分を WebMidiLink というものでつないています。

  • SMF
    • SMF の Parser
      • MFi(着メロで使われたファイルフォーマット。拡張子は mld ) から SMF への変換モジュールもあります
    • MIDI メッセージのスケジューリングを行い、WebMidiLink へメッセージを流すプレイヤー
  • Sound Font
    • Sound Font version 2 の Parser
    • WebMidiLink のメッセージを受け取り実際に音を鳴らすシンセサイザー

WebMidiLink とは g200kg さんの提唱している window の message イベントを利用した MIDI メッセージをやり取りする仕様です。
http://www.g200kg.com/en/docs/webmidilink/

Sound Font

Sound Font では音色毎にいくつかの音域に分けてサンプルが格納されています。
このサンプルにはキーが設定されているため、その音域はその指定されているキーをもとにして平均律で算出し、再生速度を調整することで鳴らす事が出来ます。
また、各サンプルには Loop Start, Loop End が設定されていて、Note On されている時はこのループをぐるぐる再生し続けます。
(この再生方法のため、Safari では loop の実装が整っていないためおかしく聞こえます)

Sound Font の再生では他に以下の機能に対応しています。(しているつもりです…。)

  • Attack, Decay, Sustain, Release
  • Pitch Bend 変更
  • ピッチの補正
    • coarseTune
    • fineTune
    • Pitch Correction
    • modEnvToPitch
  • Web Audio API で扱えないサンプリングレートの補正(22,050 未満を引き延ばす)

また、今回つくったものでは A320U という GPLv2 ライセンスで公開されている Sound Font を標準で利用するようにしています。

ループ

一部のゲームなどでは SMF 内で独自にループ再生の目印を付けていることがあります。
Ys2 Eternal で使われているメタイベントの Marker を用いたループや、PC 版 RPG ツクールシリーズなどで使われている CC#111 のループが有名です。
今回作成したプレイヤーでは上記の2つのループ方式にも対応しています。

音を鳴らす

SMF では 16 のチャンネルがあり、それぞれに Volume, Panpot, Pitch Bend などが設定できます。
今回作成したものでは、各ノートを以下のように接続して鳴らしています。

[BufferSource] ---> [Panner] ---> [Gain(Volume, ADSR)] ---+
[BufferSource] ---> [Panner] ---> [Gain(Volume, ADSR)] ---+---> [Gain(Master)] ---> [Destination]
[BufferSource] ---> [Panner] ---> [Gain(Volume, ADSR)] ---+

BufferSource は各ノートで、PannerGain(Volume, ADSR) でチャンネル毎の設定を適用しています。
そして最後はマスター・ボリュームである Gain(Master) に繋いでそれを出力するという感じになっています。

現在は割と大雑把に上記のような構成の AudioNode を NoteOn ごとに作って使い捨てているのですが、今後はこのあたりをもっと効率的に行う予定です。

謝辞

g200kg さんの Web Audio API の解説 にはかなりお世話になりました。
また、音がずれてるなどの指摘をくださった @miyazaqui さん、音楽関係の基礎知識などについて丁寧に説明してくださった @yoya さんのおかげでなんとか聞こえるレベルまでこぎ着ける事が出来ました。ありがとうございます。

その他

今回は minify したファイルのみの公開とします。
もったいぶってるわけではなくて、近いうちに大規模な書き直しを行おうと思っているからです。
minify されててもいいってひとは適当にデモからソースを読んでください。

また A320U を使用しているとき Cello の音がズレているという指摘をもらっています。
これはサウンドフォントの modEnvToPitch という設定を無視するようにすれば正しい音程になるようですが、これを無効にすると他の音でおかしくなるので現在調査中です。

音程がずれる問題の原因 (2013/06/03 16:15 追記)

@g200kg さんからご指摘をいただきまして、Modulation Envelope の適用を行ったら改善したようです。 modEnvToPitch では Attack でピッチ・ローパスフィルタの設定が最も変わるというだけで、この記事を公開した段階ではその実装のみを行っていたのですが、Envelope なので Attack と Sustain の差によってピッチの変化がずれ、その結果音程がずれていたものだと思います。

追記:2013/06/03 16:15

以下の場所でソースコードの公開を行いました。

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