msgpack.js improvement
msgpack.pack will return "Maximum call stack size exceeded" when passing big data
数日前に、「msgpack.pack が文字列を返してないよ」という issue が付いたので、第二引数が true なら、String.fromCharCode.apply を行いバイナリ文字列を返すように機能を追加したのですが、String.fromCharCode.apply は巨大なデータ(20万個の要素をもつ配列など)で例外を吐くようなので、対策を施しました。
https://github.com/uupaa/msgpack.js/blob/master/msgpack.js
before
function msgpackpack(data, // @param Mix: toString) { // @param Boolean(= false): // @return ByteArray/BinaryString: var byteArray = encode([], data), rv, i, iz, num2bin = _num2bin; return toString ? String.fromCharCode.apply(null, byteArray) // toString : byteArray; }
after
function msgpackpack(data, // @param Mix: toString) { // @param Boolean(= false): // @return ByteArray/BinaryString: var byteArray = encode([], data), rv, i, iz, num2bin = _num2bin; if (toString) { try { return String.fromCharCode.apply(this, byteArray); // toString } catch(err) { ; // avoid "Maximum call stack size exceeded" } for (rv = [], i = 0, iz = byteArray.length; i < iz; ++i) { rv[i] = num2bin[byteArray[i]]; } return rv.join(""); } return byteArray; }
- Chrome等で、 msgpack.pack(new Array(200000), true) としたときに "Maximum call stack size exceeded" が出てしまうため、例外を拾うように
- 例外発生時は String.fromCharCode.apply ではなく、自前で文字列化する処理実行するように。
String.fromCharCode.apply ブロック(↓)は、バッサリ削ることも可能ですが、通常サイズのデータを扱う場合に20%程遅くなります。
try { return String.fromCharCode.apply(this, byteArray); // toString } catch(err) { ; // avoid "Maximum call stack size exceeded" }
msgpack.pack("string") を改善する
MessagePackの仕様 では、文字列の開始を意味する符号(長さ別に3種類あります)と長さを文字列データの前に格納する形で埋込みを行います。
これまでの処理方法では、以下の手順で、文字列を埋め込んでいます。
- 配列(ary)に UTF-8 エンコードした数値を貯める
- setType() で符号と長さを配列(rv)の末尾に追加
- Array.prototype.push.apply で配列(rv)の末尾に配列(ary)を結合
case "string": // utf8.encode for (ary = [], iz = mix.length, i = 0; i < iz; ++i) { c = mix.charCodeAt(i); if (c < 0x80) { // ASCII(0x00 ~ 0x7f) ary.push(c & 0x7f); } else if (c < 0x0800) { ary.push(((c >>> 6) & 0x1f) | 0xc0, (c & 0x3f) | 0x80); } else if (c < 0x10000) { ary.push(((c >>> 12) & 0x0f) | 0xe0, ((c >>> 6) & 0x3f) | 0x80, (c & 0x3f) | 0x80); } } setType(rv, 32, ary.length, [0xa0, 0xda, 0xdb]); Array.prototype.push.apply(rv, ary);
改善するには、一時配列(ary) と Array.prototype.push.apply による結合処理をなんとかすれば速くなりそうです。特に一時配列(ary)を使うと、裏でGCが走るため、GCを減らす意味でも使わずに済ませたいところです。
改善後は、
- 一時配列(ary)を使わない
- 予め、文字列が全てASCIIコードだと仮定した符号を埋め込んでおく → rv.push(0xa0 + iz);
- UTF-8に変換した文字列を配列(rv)に直接追加
- 文字列が32byte以上だったり、非ASCIIな文字が含まれている場合は、予め埋め込んだ符号部分を Array#splice()で捨て、符号を差し込み直す
といった、若干の説明が必要なぐらい、めんどくさい処理に変更しています。
- Array#splice() は配列途中に挿し込みを行うため、リンクリストの付け替えが発生する。ちょっと遅いが、一時配列を作成しマージするよりは高速
- pos には 上書きする時に備え 符号化したコードを埋め込んだ配列の index を格納しておく
- 0xa0 + iz は、ここから「32byte未満の文字列をこれから埋め込むよ、長さはこんだけだよ」を意味する符号。長さが変化した場合も書きなおす必要がある
iz = mix.length;
pos = rv.length; // keep rewrite position
// set default type [0xa0 + ASCIIString.length]
rv.push(0xa0 + iz);
for (i = 0; i < iz; ++i) {
c = mix.charCodeAt(i);
if (c < 0x80) { // ASCII(0x00 ~ 0x7f)
rv.push(c & 0x7f);
} else if (c < 0x0800) {
rv.push(((c >>> 6) & 0x1f) | 0xc0, (c & 0x3f) | 0x80);
} else if (c < 0x10000) {
rv.push(((c >>> 12) & 0x0f) | 0xe0,
((c >>> 6) & 0x3f) | 0x80, (c & 0x3f) | 0x80);
}
}
size = rv.length - pos - 1; // -1 = default type(0xa0 + length)
// rewrite string type.
if (iz !== size) {
// has none ascii string or length >= 32
if (size < 32) {
// rv.splice(pos, 1, 0xa0 + size);
rv[pos] = 0xa0 + size;
} else if (size < 0x10000) { // 16
rv.splice(pos, 1, 0xda, size >> 8, size & 0xff);
} else if (size < 0x100000000) { // 32
rv.splice(pos, 1, 0xdb, size >>> 24, (size >> 16) & 0xff,
(size >> 8) & 0xff, size & 0xff);
}
}
string エンコード処理改善前(in Google Chrome9 dev)
data size = 100000 --------------------- JSON.stringify = 606ms JSON.parse = 393ms JSON = 1000ms --------------------- msgpack.pack = 853ms msgpack.unpack = 455ms msgpack = 1309ms
string エンコード処理改善後(in Google Chrome9 dev)
data size = 100000 --------------------- JSON.stringify = 602ms JSON.parse = 455ms JSON = 1057ms --------------------- msgpack.pack = 809ms msgpack.unpack = 454ms msgpack = 1264ms
ランダムデータを元にしたテストでは、msgpack.pack が 853ms → 809ms で 5%程改善しています(誤差といえば誤差)
msgpack.pack(0.1) や msgpack.pack(-0.1) を改善する
浮動小数点演算(IEEE754 エンコード)速度を改善します。
before
hash = _bit2num;
sign = mix < 0;
sign && (mix *= -1);
// add offset 1023 to ensure positive
exp = Math.log(mix) / Math.LN2 + 1023 | 0;
// shift 52 - (exp - 1023) bits to make integer part exactly 53 bits,
// then throw away trash less than decimal point
frac = (Math.floor(mix * Math.pow(2, 52 + 1023 - exp))).
toString(2).slice(1);
// exp is between 1 and 2047. make it 11 bits
// ▼▼▼▼
exp = ("000000000" + exp.toString(2)).slice(-11);
ary = (+sign + exp + frac).match(_split8char);
// ▲▲▲▲
rv.push(0xcb, hash[ary[0]], hash[ary[1]],
hash[ary[2]], hash[ary[3]],
hash[ary[4]], hash[ary[5]],
hash[ary[6]], hash[ary[7]]);
exp と ary を求める処理に改善可能なポイントが残っています。
- exp は11桁の2進文字列を生成しているが、必ず12桁の数値になるようにゲタを履かせることにより "000000000" + ... slice(-11) は不要にできそう
- sign は Boolean値だが、最終的に "0" または "1" に置換されるため、exp 生成時のゲタに利用できそう
こうしました(↓)
after
// exp is between 1 and 2047. make it 11 bits // exp = ("000000000" + exp.toString(2)).slice(-11); // ary = (+sign + exp + frac).match(_split8char); if (sign) { ary = ((exp + 2048).toString(2) + frac).match(_split8char); } else { ary = ((exp + 4096).toString(2).slice(1) + frac).match(_split8char); } rv.push(0xcb, hash[ary[0]], hash[ary[1]], hash[ary[2]], hash[ary[3]], hash[ary[4]], hash[ary[5]], hash[ary[6]], hash[ary[7]]);
msgpack.pack(0.1) のケースでは、さほど改善できていませんが、負数を扱う msgpack.pack(-0.1) では、slice() 関数を呼び出すコストをカットできています。
2048を加算することにより、expの12ビット(S)が必ず 1 になります。12ビットはIEEE754で言うところの倍精度の63ビット目です。これを1にすると Nagative な数値として扱われます。
4096を加算することにより、expの12ビット(S)が必ず 0 になります。(略) 12(63)ビットを 0 にすると Positive な数値として扱われます。13(64)ビットの部分が余計なため、slice(1) することで先頭1bitを切り落とします。
簡単ですね!
