失敗しない文字列シリアライザ選び.js

本記事は「[Node.jsのworker_threadsに使えるバイナリフォーマットを考えた件](https://qiita.com/ayatty/items/4b662dba4395388c7138)」のスピンオフ作品となっております。

# 1. お題目
「[Node.jsのworker_threadsに使えるバイナリフォーマットを考えた件](https://qiita.com/ayatty/items/4b662dba4395388c7138)」では、worker_threadを使った親子スレッド間でデータを共有するには`SharedArrayBuffer`[(MDN)](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/SharedArrayBuffer)を使うことを知りました。
`SharedArrayBuffer`はバイナリ配列ですから、JavaScriptの数値、文字列、オブジェクト、配列等々のデータは直接格納できません。そのため、ここに格納するためのシリアライザ、取り出すためのデシリアライザを検討しました。

わざわざ考えなくても似たようなものはあるのですが、いまいち目的に足りてないことがあって自分で作ってみた、という話なんですが、処理性能という面ではどうしても既存のものに勝てません。

そう、その者の名は**JSON**。

まあしょうがないんですよ。相手はネイティブコードで動いてますからね（多分）。目的もできることも違いますし。
にしてもちょっとでも差を縮めたいというのが親心というもの。

で、今回は、文字列のシリアライズ処理に目を付けて性能改善を図ってみた（図ろうとしてみた）という話になります。

# 2. 文字列シリアライズの方法いろいろ
本記事で「文字列シリアライズ」と言っているのは、`String`をバイナリ配列化すること、もっと具体的に言うと`(Shared)ArrayBuffer`に格納すること、とします。その逆をデシリアライズとします。

## (1) 自前(DataView使用)
`DataView`[(MDN)](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/DataView)は、`(Shared)ArrayBuffer`を扱うためのViewの一つです。
JavaScriptの`String`は、`charCodeAt()`を使ってUTF-16のコードを取り出すことができるので、UTF-16で良いならそのコードを一文字ずつ`ArrayBuffer`に`DataView.setUint16()`関数で書き込んでいきます。
That's Simple!
ざっくり書くと

```javascript
const buf = new ArrayBuffer(str.length * 2);
const dataView = new DataView(buf);
for (let ci = 0; ci < strLen; ci++) {
    dataView.setUint16(ci * 2, str.charCodeAt(ci), true/*UTF16LE*/);
}
```

こんな感じで使います。

UTF-8が良いならばサロゲートペアのことも考えて、`codePointAt()`で取り出してその値をごにょごにょした後、1byteずつ`DataView.setUint8()`で書き込んでいく感じになろうかと思います。

デシリアライズはその逆ですが、一文字ずつ取り出されるので、`str += String.fromCharCode(code);`みたいな感じで結合していきます。

```javascript
const dataView = new DataView(buf);
let decodedStr = "";
for (let ci = 0; ci < strLen; ci++) {
    decodedStr += String.fromCharCode(dataView.getUint16(ci * 2, true));
}
```

## (2) TextEncoder/TextDecoder
`TextEncoder`/`TextDecorder`[(MDN)](https://developer.mozilla.org/ja/docs/Web/API/TextEncoder)は最近のブラウザならどれでも使えます。もちろんChromeと同じエンジンであるNode.jsでも使えます。
なんか字面見ると普通にこれ使えばいいじゃんて感じしますよね。
まあ、後半のベンチマークをお楽しみってことで。
先に少しネタばらしすると、`TextEncoder`さんはUTF-8でしかエンコードをしてくれないので変換処理がはさまる関係上UTF-16より不利になりがちです。
なぜか`TextDecoder`はUTF-16にも対応している謎の仕様・・・。

```javascript
// シリアライズ(encodeを使用)
const buf = new ArrayBuffer(str.length * 3);
const uint8view = new Uint8Array(buf);
const encoder = new TextEncoder();
const encoded = encoder.encode(str);
uint8view.set(encoded);
// UTF-8は元の文字列長からbyte数を直接計算できないので読み込み時のために書き込みbyte数を保持しておく 
const encodedBytes = encoded.length;

// シリアライズ(encodeIntoを使用)
const buf = new ArrayBuffer(str.length * 3);
const encoder = new TextEncoder();
const encodeView = new Uint8Array(buf);
const encodeResult = encoder.encodeInto(str, encodeView);
const encodedBytes = encodeResult.written;

// デシリアライズ
const decoder = new TextDecoder();
const decodeView = new Uint8Array(buf, 0, encodedBytes);
const decodedStr = decoder.decode(decodeView);
```

## (3) Buffer
`Buffer`[(Node.js公式)](https://nodejs.org/api/buffer.html)はNode.js独自のAPIです。
`Buffer.from(String)`や、`Buffer.write(String)`なんかを使ってシリアライズしていきます。
デシリアライズは`Buffer.toString()`になります。
基本的に優秀なんですが、Node.jsでしか使えないのが玉にきず。

```javascript
// シリアライズ(Buffer.fromを使用)
const buf = new ArrayBuffer(str.length * 2);
const uint8view = new Uint8Array(buf);
const encoded = Buffer.from(str, encode);
uint8view.set(encoded);

// シリアライズ(Buffer.writeを使用)
const buf = new ArrayBuffer(strLen * 2 * repeat);
const nodeBufferView = Buffer.from(buf);
nodeBufferView.write(str, "utf16le");

// デシリアライズ
const decodeBufferView = Buffer.from(buf);
const decodedStr = decodeBufferView.toString('utf16le');
```

# 3. ベンチマーク
環境はこんな感じ（しょぼいです・・・）。

- OS: Windows10(1909)
- CPU: Core i3-3120M
- メモリ: 4GB
- Node.js: v12.16.0

処理条件はこんな感じ。

- 1億文字（UTF-16換算で200Mbyte）の`String`を`ArrayBuffer`に書き込む、読み出す。
- ただし、1億文字を「一つの文字列として一気に書き込む」～「10文字ずつ1000万回書き込む」のバリエーションで検証。読み出す（デシリアライズする）方も同様。
- 繰り返し書き込むパターンの場合、1度で済む処理はループの外でやる。例えば`TextEncoder` `TextDecoder`なんてのは一度newしとけばいいのでループの前でやる。
- 5回計測してその平均を取る。

[ソース(Gist)](https://gist.github.com/ayatty/f9c4ef7b5ec822009d712d949224b7e6)

## (1) シリアライズ結果

||文字コード|1回|100回|10000回|1000000回|10000000回|
|:-----|:-----|--:|---:|-----:|-------:|--------:|
|DataView.setUint16|utf16le|898|922|922|950|924|
|TextEncoder.encode|utf-8|1025|873|933|1662|9101|
|TextEncoder.encodeInto|utf-8|616|463|474|660|2740|
|Buffer.from|utf16le|362|350|315|643|4390|
|Buffer.write|utf16le|293|139|132|339|2239|
|Buffer.from|utf-8|1270|1135|1222|1405|6327|
（単位はms）

どうでしょうか。書き込み回数が少ない（＝一度の書き込みbyte数が多い）時にはBuffer.write(utf16le)無双状態ですが、一度に200byte（100万回書き込み）あたりから効率が悪化し、20byteずつになると目も当てられなくなってきます。
UTF-8一族はやはり遅い。ごにょごにょする分どうしても遅くなるのだと思われます。TextEncoder.encodeIntoは惜しいところまでは行ってますがBufferにはかないません。ただ、Bufferがブラウザにないことを考えるとencodeIntoを使ってもいいかもしれません。
DataView.setUint16は書き込み回数に関係なく一定の処理時間になりました。考えてみれば書き込み回数分のループと、文字列長のループの二重ループで回していますが、中と外のループの比率が違うだけで、ループの中の処理（`charCodeAt()`と`setUint16()`）は同じ回数動いてるので変わらないはずです。

## (2) デシリアライズ結果

||文字コード|1回|100回|10000回|1000000回|10000000回|
|:-----|:-----|--:|---:|-----:|-------:|--------:|
|DataView.getUint16|utf16le|N/A|22600|1480|1984|7276|
|TextDecoder.decode|utf16le|327|375|386|2486|26230|
|TextDecoder.decode|utf-8|887|905|924|2931|26384|
|Buffer.toString|utf16le|123|155|64|422|4473|
|Buffer.toString|utf-8|1998|1933|1880|2312|7030|
（単位はms）

ここでも「Buffer優位」「UTF-16優位」「読み込み回数増で効率悪化」の傾向は同じですが、UTF-8に関してはTextDecoderがBufferを凌駕してますね。どうしたんでしょう。
DataViewはシリアライズと違ってずいぶんと不安定な結果になりました。1回読み込みはエラーが出てしまい計測できませんでした。
これは、文字列に一文字ずつ文字を足しては新しい文字列を作ってるからで、（それでも結構速いんだよって記事をどっかで見ましたが・・・）さすがに1億回の結合には耐えられなかったようです。例えば1000文字ずつ結合した配列に入れておいて、最後にまとめてjoinみたいなやり方にすれば回避はできるかもしれませんが、どちらにせよそれほど効率は良くないですね。
ただ、1000万回の時はTextDecoderより速くなってます。

# 4. さあ教えたまえ！失敗しない文字列シリアライザとやらを！
そんなものは最初からなかったんだ・・・。

決定版！はないわけですが、以下のような条件を考慮して使い分けになるのかなあと思います。

- シリアライズ結果のサイズより速度重視ならUTF-16を使う。[^ascii]
- Bufferが使えるとき（つまりNodeの時）はBufferを使う。
- ただし、小さい文字列を扱う時はシリアライズはDataView、デシリアライズはBufferかDataViewを使う。

# 5. で
roJson高速化を目指してベンチマーク取ってみたわけですが、roJsonは小さい文字列（主にkeyですね・・・）を相手にするので`DataView`が無難。もともと`DataView`で作ってたので結果変わらず！ということになりました。残念。。。

[^ascii]: ただし、対象の文字列の大部分がUTF-8で1byte（いわゆる半角文字）の文字の場合は、変換が軽いこと（実装にもよると思いますが）と、書き込むbyte数が半分になることでメモリ確保を含む書き込み処理が軽減されることから、UTF-16より常にダメってこともないと思います。今回はベンチ割愛しましたが。