本記事はNode.jsのworker_threadsに何を渡すべきかの続きです。
よろしければそちらも是非お読みになってください。
1. 前回のquickおさらい
- 大量のメモリを使う処理を並列で動かしたい。並列であることと省メモリであることが条件。
- Node.jsには、メモリを共有できるマルチスレッドの仕組みとしてworker_threadsが備わっている。
- ただしメモリ共有にはSharedArrayBufferを使う必要がある。
- SharedArrayBufferはバイナリ配列なので、JSON-likeな複雑な構造は直接は表現できない。
- JSON.stringify等のシリアライズ結果をBufferに載せることはできるがデシリアライズしないと使えないので省メモリにならない。
- デシリアライズせずにJSON-likeな構造を扱えるシリアライザーが欲しい！作ろう！
そして作ったものをにroJson(read only JSON)という仮称を付けました。
現時点(2020/3/19)のソースはGistにあります。
2. 早速ベンチマーク取ってみる
最初に言っておきますが、Buffer全体をデシリアライズしないで必要時に必要なところだけ読む仕組みである関係上、何度も何度も同じところを読むような処理だと、部分的なデシリアライズを何度もしているのと同じなので不利です。
結局は得手不得手があるのでケースバイケースで使い分けましょうって話なんですが、今回は自作シリアライザに有利な処理ロジックとしました。
条件です。
- ObjectのArrayに対して検索する、をマルチスレッドで2回実行する
- 配列のサイズは50万
- Objectにはいくつかキーがあるが、必ず
"name"というkeyがあって、Array内で一意である - 検索したいものとして上記50万Objectのうち100個の
"name"を対象としたリストsearchTargetを用意する - 検索処理では
Array.filter(a => searchTarget.includes(a.name))1として、50万レコードに対して"name"が「検索したいものリスト」に合致するものがあるものを選び、結果として返却する - worker_threadsに渡すデータはあらかじめシリアライズしておく。検索の度にはシリアライズ処理を走らせない
検索2回だとマルチスレッドの効果があんまり出ませんが、手持ちのCPUが2コア/4スレッドゆえ・・・。
3. ベンチマーク結果
時間の単位はmsでconsole.time()を使用。
メモリの単位はMBでprocess.memoryUsage()からrssの値を使用。
| シリアライザ | シリアライズ時間(a) | 検索2回の平均処理時間(b) | トータル処理時間(c) | 使用メモリ(最大時) |
|---|---|---|---|---|
| (参考：シングルスレッド)生Object/Array | - | 3,022 | 7,394 | 229 |
| 生Object/Array | - | 13,957 | 20,704 | 597 |
| JSON | 1,857 | 4,800 | 7,449 | 1,026 |
| messagePack(msgpack-lite) | 4,392 | 10,883 | 16,084 | 997 |
| roJson | 3,620 | 6,376 | 10,653 | 407 |
どうですか？シングルスレッドが最強という、なんとも微妙な結果になりました。。。
処理時間
シングルスレッドが1位ですが、
理論的にはシングルスレッドは検索回数分だけ線形に処理時間が伸びるのに対して、マルチスレッド勢はCPUコア数分までは時間がほぼ同じに収まるはずなので、シングルスレッドとroJsonは3スレッドでほぼ同等、4スレッド以上なら逆転できることになり、まあ、、、まあまあですかね・・・。
マルチスレッド勢で最強はやっぱりJSONですね。JSON憎し。2並列でもシングルスレッドとほぼ同等です。
messagePackが意外と遅かったですね。roJsonに対しても遅いのはどうしてなんでしょう。後ほど考察します。
マルチスレッドの生Objectは顕著に遅かったです。
生ObjectをWorkerのworkerDataに渡すと、structured clone algorithmという仕組みを通して子スレッド側にデータがコピーされるのですが、これはJSONなどよりもかなり効率が悪いようです。2
マルチスレッドの他のシリアライザの場合は(a)+(b)=(c)がだいたい成り立つんですが、生Objectの場合はこれが成り立っていません。これはstructured clone algorithmが親スレッド側で結構な時間、しかも（まだ親スレッド内なので）直列で処理されているからだと思われます。
メモリ使用量
これは狙い通りですね。
シングルスレッドが1位なのは当たり前なので置いておくとして、2位はroJsonになりました。もちろん並列度を上げてもほとんどメモリ使用量は増えません。逆にJSONやmessagePackは並列度を上げるのに従ってメモリ使用量も増えていきます。
ベンチマーク結果に対する総括
使いどころが難しい感もあるんですが、うまく使えば処理時間とメモリ使用量の削減になることが分かりました。
4. roJson作成の勘所
ポイントは、処理時間とメモリ使用量のバランスを取ることでした。
理想のイメージは両方が90点。
どちらかを95点にするためにどちらかが50点になってしまうのだったらやめましょう、ということです。3
というところを念頭に置きつつ、JSONでちょっといまいちだなと思うところを補完しつつやってみた、そのポイントを挙げていきます。
Objectのkey,valueあるいは配列要素へのアクセス時間を定数にする
時間効率＋、メモリ効率－
これは前回も書きましたね。先頭から順繰りに読んでいってる暇はないのです。戦う相手は生Object/Arrayなのです。メモリ効率がやや犠牲になりますがこれは譲れないラインです。
逆に一番めんどくさいところでもあります。
keyの検索時間を定数化するのはおなじみのハッシュマップですね。roJsonではこのハッシュマップもシリアライズされたバイナリの中に埋め込んでます。
また、keyに対応するvalueがバイナリの何バイト目から配置されているのかを持たせることでvalueへのアクセス時間も定数化しています。
配列要素へのアクセスもほぼ同じです。
配列要素「へのアドレス」を持ったテーブルを用意することで、アドレスは固定バイト数(現状4byte)なので、オフセットアドレス＋要素番号×4の場所にアドレスが入ってる、と即わかるようになってます。
Number型は適切な数値型でバイナリ化
時間効率－、メモリ効率＋
これはmessagePackからアイデアを拝借しています。
Number型は本来double型なので64bit=8byteで、型識別子を付けると9byteにもなってしまうのですが、JSONに頻出するのって0とか1とかだったりしませんか？1+1byteで表現できるところを常に9byteではあまりにもったいないです。
ということで、数値の範囲を判定するという余分な処理を加わることになりますが、数値はそもそもシリアライズ対象の値の他にも、ハッシュマップのサイズだったり配列のサイズだったり文字列長だったりと結構使うところが多いので、入れたほうが良かろうと判断して取り入れました。
なんと0～15の4bitで収まる範囲は、型識別子と合わせても1byteで済むようにしています。4
疎配列に対応
時間効率＋、メモリ効率＋、対JSON＋
疎配列っていうのは、値が定義されていない要素のあるArrayのことです。
const a = new Array(100000);
a[5000] = undefined;
console.log(a)
// (100000) [empty × 5000, undefined, empty × 94999]
undefinedですらないことに注意。本当に何もないんです。5
が、これをJSON.stringifyに渡すとご丁寧にnullで埋めてくれるんですよね・・・。
同じことをすると時間もメモリも無駄なので定義されている要素番号だけ保持するようにしました。
Objectのkey/valueとほぼ同じように扱えるので、ロジックはほぼ共通になってます。
文字列はUTF-16
時間効率＋、メモリ効率－？
JavaScriptの内部文字コードはUTF-16です。常に1文字に対して2byte(サロゲートペア除く)が必要になります。
大抵のデータでString型の箇所(Objectのkeyも含む)は、半角英数なことが多いと思いますので、UTF-8に比べて倍のメモリを食うことになります。
ただ、UTF-16をUTF-8に変換する処理はそれなりに重い処理になると想定されるのでやめました。これは後述するmessagePackとの比較でも考察しています。
それに全角文字が多用されてるデータかもしれませんしね。その場合はUTF-16の方が有利です。
対JSONで他にもやりたいことがあります
下記は未実装ですが入れたいなと思ってるものです。
(1) 循環参照
JSONでは無理ですね。JSONで頑張って表現する方法を考えてる方もいますが、JSON仕様にない以上は実装依存にならざるを得ないので、一般的にはならないでしょう。roJsonは値の場所をアドレスで示す仕組みがあるので後は「Object/Arrayが同じもの」ってわかりさえすれば同じアドレスを指すだけなので簡単です。バイナリフォーマット仕様的には既に対応済みと言っても良いでしょう。
(2) undefined
JSON.stringifyに渡すとvalueがundefinedだと対応するkeyを消してくれたりだの、そうでなくてもnullにしてくれたりだのおせっかいが過ぎます（私見です6）。JSON縛りがないのなら、undefinedはundefinedのままにしといた方が幸せではないかと思うのです。
これはいつでもできますね。やってないだけです。
(3) 同一の文字列値は共通する一か所に格納する
今回扱ってるような巨大なJSONだったら、まず間違いなく繰り返し構造が存在しているはずです。リストにしろツリーにしろ。
ということは同じkeyが何度も出てくるはずなので、その度に何バイトかの領域を使うのはもったいないです。同じ場所を参照させてもいいでしょう。
これはメモリに効くことは自明（かつJSONには絶対真似できない）なんですが、将来、仮に読み出し専用じゃなくて更新も可能にしたいなあ、、、なんて色気を出し始める可能性を考えて二の足を踏んでるのが現状です。その文字列がまだ使われてるのかいないのか参照数を意識しないと捨てることができなくなっちゃいますからね。
msgpack-liteより速かった理由を考える
ベンチマークのコードが誤ってる可能性もありますが・・・。
特に(a)のシリアライズ処理のところですね。(b)はworkerData全体をデシリアライズしてから検索するというroJsonに対する不利な点があるのでまあそういうこともあるかな、という感じです。
roJsonはmessagePackに大いに影響を受けているのでシリアライズ方法は結構似通っているんです。加えて、ハッシュマップなどを余分に作ってる分遅くなると思ったんですよ・・・なんか大事な処理が漏れてるんだろうかと心配になります・・・。
それ以外に思いつくものを挙げてみました。
(1) StringをUTF-8にエンコードしている
一番に思いつく原因。
先にも書きましたがroJsonはJSの内部文字コード（charCodeAt()で取れる値）であるUTF-16の値をそのままUINT16型の値としてバイナリに書き込んでいます。一方、messagePackはメモリ効率を考慮してUTF-8に変換しています。これが遅い可能性。これであればmessagePackのバイナリフォーマットに起因する問題なので、msgpack-lite以外のライブラリであっても同じ理由で遅くなっている可能性があります。
(2) Bufferに書き込む値をbyte単位に分割して入れている
例えばUINT16な整数は2byteになるわけですが、上位byteと下位byteに分割して書き込む、というのをmsgpack-liteは自前でやってるようです（確信なし）。
それに対してArrayBufferをDataViewを通して使うとbyte単位に分割する処理は不要で済みます。DataViewの効率はかなり良いのだと聞きます。であればmsgpack-liteもDataViewを使うようにすれば速くなる可能性があります。
なお、messagePackはRPC等のデータ交換用途も考慮しているのでエンディアンを意識する必要があり、それがためにbyte単位の処理をしている可能性もあります。が、DataViewもsetXXX/getXXXはデフォルトでビッグエンディアン固定、引数指定によりリトルエンディアン固定にもできるのでDataViewで済ますことはできそうです。
(3) 多環境/異常系を考慮した堅牢な作りになっている
はいごめんなさい。その辺roJsonは結構雑です。
堅牢な作りの分遅くなっている、という可能性はありえそうです。
5. 以上
作ってみてそれなりの成果は得られたものの、正直微妙・・・。
もうちょっと処理自体を見直すか、もっと有用なユースケースを見つけるかして、いずれちゃんとnpmとして公開できたらな、と思ってます。
-
そもそもね君ぃ。
Array.includes()なんて使ってたら遅くて話にならんじゃないか！というご指摘はごもっとも。Set使いなよって話ではあるし、nameが一意なんだったらMapにnameをkeyにして突っ込んでsearchTargetの方でぐるぐる回す（mapとかforEachとか）方が速いっしょって言われるとぐうの音も出ない。が、聞かない。うそ。それだと速すぎてroJsonの優位が生かせるベンチにならないのだ。もうちょっと良いユースケースがあるといいんだが。 ↩ -
効率と引き換えにかなり広い範囲の組み込みクラスをカバーしているという汎用性もありますので「だからこいつはダメなんだ」などというつもりはないです。 ↩
-
もちろん点数は感覚的なものなので絶対的な指標があるわけではありません。 ↩
-
実は参考にしているmessagePackはもっとラディカルで、7bitまでの正の整数を識別子と合わせて1byteで表現しています。つまり識別子は1bitなわけです。恐ろしい・・・。 ↩
-
ただし、empty要素に対して例えば
a[0]===undefinedとかやったりするとtrueだったりします。やっかいです。 ↩ -
もちろんJSONである以上はemptyもundefinedもないのでnullにするしかないという事情は理解してます。 ↩