JavaScriptで b-tree

導入

ある日突然、JavaScript上で高速に追加・削除が行えて爆速で最小値を検索できる入れ物が欲しくなった。
普通(JavaとかFORTRANとか)ならここで素直に b-tree の実装に入るのだけども、JavaScriptは例によって変態言語なので、実は面倒なことせずにArrayに普通に入れて、素直にソートとか線形探索したほうが速いのかもしれないという疑問を持った。

しかも「最近全然技術日記してない」という突込みが入り、ついカッとなってベンチマークをとってみた。*1

調べ方

以下の3つの入れ物を実装。適当な実装を探してみたが、あまりいいものが無かったので車輪の再実装。

BTree
素直にb-treeを実装。速度よりは読み書きしやすさ優先。スペック通りなら、追加・削除、値の探索が高速。
SortedList
配列を常にソートしておいてb-searchで値探索、spliceで追加・削除。配列の追加削除が十分速ければb-treeよりも楽でいいかもしれない。
EasyList
配列に普通にpushで入れておいて、必要になってからソートや線形探索を行う。値の追加は速いはずだが、ソートや線形探索が十分速ければ上のような複雑なことをする必要がないということになる。

これらに対して、以下の操作のマイクロベンチマークを実行。極端な差や傾向がつかめればよいという方針により、計測対象の処理はかなりいい加減。

add
単純にランダムな値を連続で追加する。ツリーのノード追加、配列の値挿入、pushの速度比較。
head
最小値を探す。ツリートラバースと線形探索の速度比較。
tail
最大値を探す。これも同じ。
toArray
ソートされた配列を返す。配列コピーとツリーから配列生成の速度比較。
iterate
順不同でかまわないので全要素を参照する。ツリーと配列のループ速度比較。
remove
中身が空になるまで値を指定して連続で削除する。ツリーのノード操作と、配列の中身削除の速度比較。

自分が欲しいのは、add,head,removeが速い入れ物。

JavaScriptでのソートの実装に当たっては、Array.sortが遅すぎるため子飼さんのqsortを参考にした。

結果

ソースと動く結果 (※IEだと「固まった」と文句言われる可能性がある)

手元での実行結果:

表の中の数値はかかった時間(msec)。

b-tree圧勝が安定した速さを示した。それぞれの結果について詳しく見てみる。まず、Firefoxでの結果について述べて、IEについてはFirefoxとの違いについて触れる。

add:追加に関する性能

EasyListが最速で、次にBTree、重すぎるのがSortedList。

EasyListの速度が速いのは、結局Arrayも単純な追加はプロパティの追加でしかないから。BTreeもノードの操作が入る以外はプロパティの追加。

SortedListは、spliceで間に挿入する際に、プロパティのコピーによる再配置が起きて遅くなっている。

head,tail:最小・最大値

BTree、SortedListは爆速。BTreeはO(log(n))でアクセスできるので、数千個あっても大体数ステップで到達できる。SortedListは一発。

EasyListは値の位置に依存するので今回の実装はあまり適当ではないが、値としてはそれらしい値が出ている。数値を見る限りは線形探索でもそれなりに使えなくはない問題無い速度は出ている。*2

toArray:ソートされた配列生成

SortedListは配列コピーだけなので最速。BTreeも配列生成コストにiterateするだけなので速い。

一方で、EasyListはソートする時間がかかるのでかなり遅い。ただし、値追加+ソートされた配列生成の一連の動作としてみれば、逆にSortedListよりもEasyListの方が多少速くなる。

iterate:ループで全要素の参照

同じ配列のループということで、SortedListとEasyListはほぼ同じ。

BTreeも同じオーダーなのでループについてはBTreeは配列と同じ速度だとみなしても問題ないと言える。

remove:値の削除

BTreeが他を引き離して最速。続いてSortedList。かなり遅いのがEasyList。

BTreeが他の2つよりも速いのは、他の2つがspliceによる値コピーが発生していることで遅くなっているから。また、SortedListとEasyListの違いは、二分木探索と線形探索の速度の違い。

IEでの結果について

(2007/10/15:バグ修正により大幅に書き換え)

順位については変化はない。基本的にIEの方が数倍から10倍ほど遅い。

SortedListのaddとSortedListとEasyListのremoveはIEFirefoxの遅さの差が小さい。要するにArray.spliceのような重い処理が速度を決めているらしい。よって、IEJavaScriptの実行ステップ数が多くなればなるほどFirefoxとの差が開いていく。このことから、IEで速度を上げるにはメモリを多く使ってでもJavaScriptの実行ステップ数を減らす方法が有効なのかなと思った。

とりあえず自分的にはBTreeの速度がIEでもそれなりに良かったので安心した。

結論

  • b-treeはスペック通りの性能を示した。
  • JavaScriptはArrayといっても中身はハッシュ表によるオブジェクト。削除以外はかなり速い。
  • IEJavaScript関数を多用するととにかく遅い。

追記(2007/10/15)

BTreeを使ってプログラムを作っていたら値削除部分にバグを発見した。あと、EasyList.head,tailもミスがあったので訂正した。ベンチを取り直したら、順位や傾向は変わらないもののBTreeが圧勝というわけではなくなったので、そのあたりの表現も多少訂正した。また、IEでの速度についても特徴が分かりにくくなったので、もう「遅い」というだけにした。

*1:Rails以外なら何でも良かった。今は反省している

*2:EasyListを改良して最大、最小値を自前で持っておけばSortedListと同じ速度でhead,tailを探してくることはできるが、今回はそれは目的ではない。