Javascriptのコンテナ性能比較
ちょっとスピード狂をやる必要があって色々調査した。
こういう選択は用途によってコンテナのアルゴリズムが決まる。 しかしJS標準ではC/C++のSTLのようなアルゴリズムの選択肢が無くNPMに頼ることになるが実装まで読まないと何をしているのか解らないモジュールや効率的に実装されているかどうかも解らない。 一々性能試験をしなきゃならず面倒だが、やらない訳にもいかない。。
想定状況
- 数値データ
- 値は重複する
- insert / delete が頻繁に発生する
- 指定値による参照が大量に発生する
- 範囲検索が起きる
- 長時間安定稼働する必要がある
分岐検索とイテレータブルを両立し、かつ効率的な挿入削除ができること。が必要。
アルゴリズムとしてはバイナリーツリーとデータ量によってはソート済み配列が候補になる。
AVLやRedBlackはinsert / deleteがランダムに入る状況では採用したくないので除外。
テストコード
GitHub - crumbjp/test_js_containers
テスト対象モジュール
期待しているのは、★ だけ。あとはネタ枠。ほんの少しだけ掘り出し物を期待。
標準Array（比較対象）
ソートせずにpush。線形探索。spliceで削除。
★ 標準Arrayをソート済みに保つ
ソート済みを保ちlodashのsortedIndexByで２分探索。 insert / delete はsplice。位置の特定までは早いが、spliceのindex付け替えコストが高い。
★ @tylerbu/sorted-btree-es
sorted-btree のクローン。
ウクライナの問題もあって、本家がCommonJS形式で読み込めなくなっている状態に対処している。’
そのままでは、値の重複が許されないため、データ構造側で少し工夫をしている
taffydb
GPT4oが教えてくれた。古すぎる・・・ インデックスを指定しなくともクエリーを最適化してくれるらしい。（そんな馬鹿な）
★ LokiJS
コンテナというよりインメモリーデータベース。有名どころだが、もう何年も更新がない。
柔軟にインデックスを貼れるので便利。
ただクエリーが思ったように動かない事があり、複雑が故にその解析も大変で、多く個人的には好きではない。
nedb（比較対象）
昔気になっていたもの。インメモリーでも使えるデータベース。
TingoDB
昔気になっていたもの。MongoDB互換のクエリーを謳ったインメモリーデータベース。
この頃流行ったスタイルだなぁ・・・と懐かしくなる。
結果
M3 Mackbook pro で計測
コンテナに保持しているデータ数毎、各処理を1000回試行した際の処理時間（ms） ただしrange処理は１回だけ試行
insert
| class | 1067 | 5257 | 10744 | 53009 | 105667 | 317043 | 528166 | 739974 | 1056478 |
|---|---|---|---|---|---|---|---|---|---|
| TestArray | 0 | 0 | 1 | 0 | 1 | 14 | 1 | 1 | 2 |
| TestLoki | 1 | 1 | 3 | 6 | 11 | 88 | 153 | 206 | 325 |
| TestNedb | 23 | 21 | 20 | 25 | 24 | 26 | 30 | 30 | 27 |
| TestTingodb | 8 | 5 | 4 | 8 | 4 | 6 | 13 | 5 | 12 |
| TestBTree | 1 | 1 | 1 | 0 | 2 | 1 | 1 | 1 | 2 |
| TestSortedArray | 1 | 0 | 0 | 15 | 19 | 404 | 709 | 976 | 1707 |
| TestTaffy | 6 | 5 | 6 | 6 | 6 | 5 | 5 | 5 | 5 |
SortedArrayはデータが大きくなるとspliceの処理が如実に効いてくる。
Lokiはインデックス構築のコストが高い。
adaptiveBinaryIndices: false を指定するとindexの処理を遅延実行（その後の最初のfind時）してくれるためbulkinsertで使えると思いきや、indexへの挿入ではなく完全再構築になり余計遅くなる。
findOne
| class | 1067 | 5257 | 10744 | 53009 | 105667 | 317043 | 528166 | 739974 | 1056478 |
|---|---|---|---|---|---|---|---|---|---|
| TestArray | 9 | 28 | 53 | 237 | 446 | 1204 | 1730 | 2326 | 2815 |
| TestLoki | 3 | 1 | 2 | 2 | 4 | 3 | 3 | 2 | 4 |
| TestNedb | 44 | 42 | 42 | 50 | 42 | 41 | 42 | 46 | 49 |
| TestTingodb | 63 | 58 | 59 | 64 | 59 | 58 | 72 | 73 | 75 |
| TestBTree | 2 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| TestSortedArray | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 2 |
| TestTaffy | 234 | 727 | 1337 | 6192 | 12202 | 36712 | 61332 | 87991 | 127708 |
単純に２分探索を実現できているものとそうでないものに分かれる。
線形探索より遅いtaffyはどうした（笑）。GPTもこんなものを勧めるんじゃないよ。
rangeGet
| class | 1081 | 5314 | 10585 | 52874 | 105466 | 317402 | 528743 | 739463 | 1057958 |
|---|---|---|---|---|---|---|---|---|---|
| TestArray | 1 | 0 | 0 | 1 | 2 | 5 | 14 | 10 | 16 |
| TestLoki | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 6 | 6 |
| TestNedb | 2 | 1 | 1 | 3 | 3 | 12 | 20 | 26 | 36 |
| TestTingodb | 12 | 12 | 14 | 35 | 56 | 148 | 250 | 325 | 613 |
| TestBTree | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 2 | 2 |
| TestSortedArray | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| TestTaffy | 1 | 1 | 1 | 9 | 15 | 43 | 73 | 119 | 142 |
線形探索が侮れない速さ。下手にインデックスを追う処理より全部舐めた方が早いケースも多々あるということ。
delete
| class | 1081 | 5314 | 10585 | 52874 | 105466 | 317402 | 528743 | 739463 | 1057958 |
|---|---|---|---|---|---|---|---|---|---|
| TestArray | 6 | 27 | 35 | 255 | 477 | 1006 | 2534 | 2264 | 3012 |
| TestLoki | 7 | 9 | 13 | 40 | 108 | 282 | 502 | 655 | 896 |
| TestNedb | 45 | 43 | 48 | 46 | 48 | 50 | 51 | 58 | 56 |
| TestTingodb | 117 | 114 | 115 | 164 | 140 | 118 | 129 | 126 | 131 |
| TestBTree | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 3 | 3 |
| TestSortedArray | 1 | 1 | 1 | 24 | 51 | 411 | 664 | 980 | 1502 |
| TestTaffy | 455 | 1675 | 3293 | 17075 | 35283 | 102415 | 12309541 | 29964609 | 17357942 |
やはりspliceのコストが目立つ
まとめ
- sorted-btreeの実装は期待通りだった。
- 期待していなかったnedbは完成度が高かった。もっと複雑な用途でインデックスを複数貼りたいようなケースでは検討できる
- LokiJSはinsert / delete に弱く、クエリーは早い。データ量が少なかったり、更新頻度が低いならば検討できる
- やはりNPMモジュールは期待通りに動かないので、検証活動は必須
