msgpack-lite メモリコピーを防いで高速化した話

バイナリ形式の軽量なオブジェクトのシリアライズフォーマットである MessagePack（以下、msgpack）のエンコード・デコードを行う JavaScript ライブラリ msgpack-lite を2015年7月にリリースしました。node.js v0.10 から最新の v5.3、またブラウザも含めて幅広い環境で動作するのが特徴で、fluent-logger ライブラリも、msgpack に替えて msgpack-lite を採用しています。

以下では、msgpack を実装した際に注意したポイントを、２つご紹介します。

C++ よりも高速なピュア JavaScript 実装

本題に入る前に、ベンチマーク結果を更新しておいたので、ここに載せておきます。

最新バージョン msgpack-lite 0.1.14 の node.js v4.2.3 におけるベンチマーク結果です。
msgpack-lite は JavaScript のみで実装しているにも関わらず、C++ で書かれた msgpack ライブラリよりも高速に動作します。

operation	op	ms	op/s
buf = Buffer(JSON.stringify(obj));	1055200	10000	105520
obj = JSON.parse(buf);	863800	10000	86380
buf = require("msgpack-lite").encode(obj);	969100	10000	96910
obj = require("msgpack-lite").decode(buf);	600300	10000	60030
buf = require("msgpack").pack(obj);	503500	10001	50344
obj = require("msgpack").unpack(buf);	560200	10001	56014
buf = Buffer(require("msgpack.codec").msgpack.pack(obj));	653500	10000	65349
obj = require("msgpack.codec").msgpack.unpack(buf);	367500	10001	36746
buf = require("msgpack-js-v5").encode(obj);	189500	10002	18946
obj = require("msgpack-js-v5").decode(buf);	408900	10000	40890
buf = require("msgpack-js").encode(obj);	189200	10000	18920
obj = require("msgpack-js").decode(buf);	375600	10002	37552
buf = require("msgpack5")().encode(obj);	110500	10009	11040
obj = require("msgpack5")().decode(buf);	165500	10000	16550
buf = require("notepack")().encode(obj);	847800	10000	84780
obj = require("notepack")().decode(buf);	599800	10000	59980
obj = require("msgpack-unpack").decode(buf);	48100	10002	4809

（１）case 文は廃して、小さな関数を事前生成

さて、msgpack は、0x0123 という正の16 bit整数値を cd 12 34 という３バイトで表します。

msgpack へのエンコードとは、JavaScript のデータ型を判定して、
バイナリデータの書き込みを繰り返していく処理です。

msgpack からのデコードとは、バイナリデータの先頭の識別子に応じて
続くデータを順に JavaScript オブジェクトへ変換していく処理です。

この型判定や識別子判定を素直に実装すると、if や case 文の羅列になるでしょう。

現代の JavaScript では、関数呼び出しコストはほぼ０と考えられます。
また、最近の実行環境はメモリも潤沢です。
そこで msgpack-lite では、予め必要なパターンの関数を全て生成しておいて、
変換処理の実行時には if や case の条件分岐も行わない方針を採用しています。

read-token.js がデコーダー、write-token.js や write-type.js がエンコーダの実装です。
ここに case 文は一切なくて、初期化時に無機質に関数を生成して、配列に並べています。

write-token.js

// 識別子 0xcd の初期化
token[0xcd] = write2(0xcd);

// バッファに識別子１バイト＋データ２バイトを書き込む関数を生成する関数
function write2(type) {
  return function(encoder, value) {
    encoder.reserve(3);             // 計３バイトのバッファを確保する
    var buffer = encoder.buffer;
    var offset = encoder.offset;
    buffer[offset++] = type;        // 識別子１バイトを書き込む
    buffer[offset++] = value >>> 8; // データ上位バイトを書き込む
    buffer[offset++] = value;       // データ下位バイトを書き込む
    encoder.offset = offset;        // カーソルを移動する
  };
}

複雑な条件分岐が並ぶ長大な関数よりも、シンプルで小さい関数の方が、JIT も効きやすいかも。
とはいえ、高速化については、次項のメモリ管理の方が重要です。
case 文が並んだ 200行を超える関数は JIT だけでなく人間にも読みにくいですから、
関数化方針については、高速化よりも、ソースコードの管理上の目的（趣味）が大きいです。

（２）可変長データに合わせた Buffer メモリ管理

最初に、node.js でバイナリデータを扱う仕組みをおさらいします。

node.js でデータをファイルに書き込んだりネットワーク通信する際に使う Stream クラスは、
内部でバイナリ形式の Buffer オブジェクトを扱います。

Buffer オブジェクトを作る際には、毎回、その容量のメモリを malloc するわけではありません。
細切れのメモリが個別に確保されないように、Buffer は容量 8KB の共用プールを持っています。
4KB 未満の Buffer を作る場合は、プールから割り当てることで高速化が図られています。
4KB 以上の Buffer を作る場合は、新規のメモリを確保します。
8KB のプールを使い切ったら、次の 8KB プールを確保する仕組みです。

もともと JavaScript にはこの Buffer オブジェクトは存在しませんでした。
node.js v0.1.90 から独自に実装された Buffer オブジェクトは、
io.js の成果を取り込んだ v4 で、内部が HTML5 の Uint8Array ベースに変わりました。
v0.12 までの Buffer オブジェクト と v4 以降の Buffer オブジェクト では、
処理速度の傾向が変わったものの、8KB 単位のプールの仕組み自体は現在も変わっていません。

msgpack-lite の実装の話に戻ります。

msgpack は可変長フォーマットのため、エンコード後に必要になるメモリ容量が事前には分かりません。
しかし、オブジェクトごとに個別に細かくメモリを確保していては、処理が遅くなります。
とはいえ、最初から大きすぎるメモリを確保するのは、無駄になり、これもまた遅くなります。

msgpack-lite では、エンコーダ時に Buffer オブジェクトを直接使わずに、
EncodeBuffer クラスを介してメモリ管理を行います。

EncodeBuffer は、msgpack のエンコード処理を始める最初の１回目については、
Buffer よりも細かく、まずは 2KB 単位でメモリを確保します。
msgpack の小さなデータのエンコードが続く場合は、2KB 以下のメモリで足りますから、
Buffer の共用プールを使うことで、メモリ確保の回数を減らしています。

しかし、エンコード結果が 2KB に収まらない場合は、さらにメモリ確保が必要になります。
今度は 4KB、それでも足りなければ 8KB、その次は 16KB、32KB…と、
確保する容量を倍増させながら、メモリを確保していきます。
これにより、大きなデータのエンコードを行う場合にも、メモリ確保の回数を減らしています。

encode-buffer.js

EncodeBuffer.prototype.reserve = function(length) {
  if (!this.buffer) return this.alloc(length);

  var size = this.buffer.length;

  // is it long enough?
  if (this.offset + length < size) return;

  // flush current buffer
  if (this.offset) this.flush();

  // resize it to 2x current length
  this.alloc(Math.max(length, Math.min(size * 2, MAX_BUFFER_SIZE)));
};

実際に使うメモリ量に合わせて、メモリを確保する回数を調整していく仕組みです。
このほかにも個別のデータのエンコード処理でもメモリコピーを防ぐ処理を組み込んでいます。

また、msgpack にエンコードした結果をファイルに書き込むなどのストリーミング出力時も、
細切れになったバッファを結合せずに、そのまま Stream に出力していきます。
ここでも、いかにメモリのコピー回数を減らして、ゼロコピーに近づけるのを目標としました。

このほかにも、msgpack-lite 実装時は細かいチューニング・小手先の改良もたくさん入れたものの、
Buffer 以外のテクニックで得られた高速化効果は、もはや誤差範囲と言っても過言でないほど、
大きな性能差を産んだのが、Buffer 周りのメモリコピー回避でした。

おわりに

従来の JavaScript 実行環境は、ブラウザごとの実装の違いも大きく、
言語的にも、バイナリ形式もなく、文字列形式の参照渡しもないこともあって、
メモリ内部の動きに配慮したプログラミングで処理を最適化できる範囲は限られました。

しかし現在では、TypedArray などで大容量のバイナリデータを扱うことも増えてきています。
V8 の JIT は賢いので、物理的に時間がかかるメモリコピーのロジックだけ気をつけてあれば、
pure JavaScript 実装でも、ネイティブ実装と遜色ない速度で実行できるのです。

富豪プログラミングの時代にありながら、低レイヤーのメモリコピーを避けるプログラミングは、
今回の msgpack エンコーダに限らず、他のライブラリやアプリを実装する際にも重要なポイントと言えます。