プログラミング言語は世の中にたくさんありますし、用途や好みによって自由に使えることが多いのですが、一部どうしても置き換えができない言語というものがあります。ブラウザやFlashマクロやPhotoshopマクロのJavaScript、Action Script、GPUのシェーダ言語、Visual Basic for Application、SQLなどなどです。それでもaltJSやORMなど、直接書かないという選択肢もあったりもしますが、どうしても直接書くほうが実行効率が良かったりチューニングが効いたりします。
JavaScriptを使ったコーディングを何年かやっていると、C言語で書かれたアルゴリズムをJavaScriptに移植しないといけない事態に遭遇する機会も増えてくると思いますので、それについて説明します。
整数型としてデータを扱う
JavaScriptの言語仕様ではJavaScriptの整数型はIEEE 754の64ビットデータ型であると書かれています。C言語で言うところのdouble型しかない状況。
- 符号:1ビット
- 指数:11ビット
- 仮数:52ビット
>>> Math.pow(2, 53)
9007199254740992
>>> Math.pow(2, 53) + 1
9007199254740992
>>> Math.pow(2, 53) + 2
9007199254740994
2^52を超えると、指数に1が入り、仮数部の数値の1が2として扱われるようになります。1を足しても有効な桁以下なので無視されます。この範囲内であれば数値型として扱えます。
node.jsではデフォルトで有効になっているv8最適化オプションに--opt_safe_uint32_operationsというものがあります。
- --opt_safe_uint32_operations (allow uint32 values on optimize frames if they are used only in safe operations)
node.jsは安全だとわかっている数値はuint32として最適化するっぽいです。たまに以下の様なコードを見かけますね。
a &= 0xffffffff; // こうすると早くなるよ！
また、ビット演算する場合は一度32ビットに変換されます。2^32を以上のビットの数値はなかったことにされます。
> Math.pow(2, 34) >>> 10
0
64ビット整数は難しいですが、32ビット整数なら大丈夫です。
浮動小数点数をバイト列として扱う
TypedArrayを使えば、64ビットの浮動小数点数型の数値をバイト列に入れて、それをバイト単位で取り出すことができます。このテクニックも年に1度ぐらいは使うことになるんじゃないかと思います。
> a = new ArrayBuffer(8)
> b = new Float64Array(a)
> c = new Uint8Array(a)
{ '0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0 }
> b[0] = 0.123456789
0.123456789
> c[0]
95
> c[1]
99
> c[2]
57
> c[3]
55
>
掛け算
32ビットの数値同士の掛け算をする場合、52ビットを超えてしまうと数値が落ちて誤差が発生してしまいます。FirefoxやChromeならMath.imulが使えます。node.jsの0.11は--harmony_mathsオプションをつければ使えますし、今一部で話題になりつつあるio.jsなら最初から使えます。そうでない場合は下記のpolyfillでエミュレートします。
入力値的に52ビットを超える可能性が低い場合は、いったん普通に計算してみて、2^52以下なら& 0xffffffffでマスクして、それ以上なら下記のimulを呼べば、高速化になります(@uupaaさんアイディア)。
function imul(a, b) {
var ah = (a >>> 16) & 0xffff;
var al = a & 0xffff;
var bh = (b >>> 16) & 0xffff;
var bl = b & 0xffff;
// the shift by 0 fixes the sign on the high part
// the final |0 converts the unsigned value into a signed value
return ((al * bl) + (((ah * bl + al * bh) << 16) >>> 0)|0);
}
ビットシフト
uint32的に数値を扱うときは、シフト演算子は>>ではなく、>>>を使います。>>は符号を維持するため、マイナスの数値の場合、シフトしても32ビット目が立ち続けます(シフトしないで)。ちなみに、<<<は存在しません。左シフトは<<で大丈夫です。
> (0xffffffff >>> 1).toString(16)
'7fffffff'
> (0xffffffff >> 1).toString(16)
'-1'
ビットローテーション
これは存在しないので自分で書かないとダメですね。
function rotl(v, n) {
return (v << n) | (v >>> (32 - n));
}
その他のビット演算
and(&), or(|), xor(^)はC言語と同じように扱えます。
メモリコピー
C言語だとmemcpy関数でいっぱつでできますが、JavaScriptにはそのような便利なものはありません。
FirefoxのTypedArrayにはcopyWithinというメソッドがあり(ECMAScript 6に提案中らしい)、同じメモリブロック内でのコピーができます。スライド辞書式の展開アルゴリズムを実装したときの展開速度が数倍になってくれそうです。
そうじゃない場合はUint8Arrayを使って1バイトずつコピーする必要があります。
// Copy the literals
var end = i + literals_length;
while (i < end) {
output[j++] = input[i++];
}
勘の良い人は「あれ？Uint32Array使えばいいんじゃね？」と思われるかもしれません。確かに、これを使えばループの数が1/4になります。実際、うまくハマれば2倍以上早くなります。Float64Arrayを使えば1/8です。
ただし、TypedArrayには制約があります。世の中には、メモリアクセスの単位と、メモリの境界（アライメント）がそろってないとうまく処理してくれないCPU(ARMとかARMとかARMとか、それ以外だとARMも)があります。ARM、アラインメントあたりのキーワードでぐぐるとすぐに情報が出てくると思います。
JavaScriptもそのようなアーキテクチャに配慮してか、アクセスの単位をそろえる必要があります。Uint32Arrayを、ArrayBufferに対してオフセットが4の倍数じゃないとエラーになります。
> a = new ArrayBuffer(16);
> b = new Uint32Array(a, 1);
RangeError: Byte offset / length is not aligned.
コピー元とコピー先のオフセットが両方2の倍数ならUint16Arrayを使い、両方4の倍数ならUint32Arrayを使い、余ったところはUint16ArrayとUint8Arrayで隙間を処理する・・・みたいにやればいいんでしょうけど、一度実装しようとしてめんどくさくてやめました。誰か賢いmemcpyのJS実装を作ってくれるとうれしいです。
2/11追記
オフセット合わせのmemcpy作りました。同じバッファ内での移動に限定しています。ただ、速度はそんなに変わらないです。キャッシュもJITもある21世紀は、細かいことせずにループでぶん回す方がいいみたいです。
このあたりを使ったコードは、僕のgithubリポジトリのbit-vector.jsx(FM-indexを使った検索エンジンOktaviaで使っている簡潔データ構造)や、xxhash.jsx(最速ハッシュ計算アルゴリズムのJSX移植)、lz4.jsx(最速圧縮アルゴリズムの展開コードのJSX移植)あたりで使っています。JSXいいですよ。
こんなところでしょうか？明日はmizchiさんです。
2/11に追加
Goto文
Goto文を書き直すのは大変ですよね？ifとかforの中に飛び込むようなgotoはちょっと大変ですが、同じ制御構文の階層の中で移動、もしくは親のスコープに出る系のジャンプなら機械的に変換可能です。
まずはCのコードです。firstのラベルの中からsecondを抜けてthirdを実行しています。
first:
printf("first\n")
goto third;
second:
printf("second\n");
third:
printf("third\n");
同じコードのJavaScript版です。動きがわかりにくいのですが、一度breakで抜けて、お尻に行ったあと、ラベル付きcontinueで先頭にジャンプしてから目的地に行きます。ジャンプ元から前に行くジャンプもできますし、後ろに行くジャンプもできます。ジャンプの移動範囲のところにラベル付きwhile文を置くのがポイントです。
もし、同じブロック内で、ジャンプ先のラベルが複数の階層(for/if/whileなどのブロック単位で)に分かれている場合は、フラグやラベルを工夫する必要があります。
var destination = "first"
topLabel: while (true) {
var jump = false;
switch (destination) {
case "first": // caseがラベル相当
console.log("first");
//ここから
destination = "third";
jump = true;
break;
//ここまでが goto third;
case "second":
console.log("second");
case "third":
console.log("third");
}
if (jump) {
continue topLabel;
}
break;
}
4/27に追加
ポインタ
C言語をC言語たらしめているのがポインタです。JavaScriptは基本参照渡しと考えて差し支えなく、使用上はメモリコピーのコストがどうのこうのと考える必要はありません。ですが、ポインタだけを渡しておいて、ポイント先のデータは後で変わる可能性がある/ポイント先のデータを書き換える、といった使い方はできません。
function pointer(initialValue) {
var _value = initialValue;
return function (value) {
if (value === undefined) {
return _value;
} else {
_value = value;
}
};
}
var p = pointer(10); // 値10が入っているポインタ
var value = p(); // ポインタの値を取り出す = 10
p(20); // ポインタの参照先のメモリに20を格納
console.log(p()); // ポインタの値を取り出す = 20
pのまま渡せばポインタ渡しです。他の関数やオブジェクトに渡すことができます。関数呼び出しをするとdereferenceです。やろうと思えばポインタのポインタとかもできますね。
1要素の配列とかでもできます。