C言語のmallocやC++言語のnewオペレータが呼ぶメモリアロケータをシステム標準の実装から変更した場合の、各種DBMクラスの動作速度とメモリ使用量を調べてみた。glibc標準のmalloc、jemalloc、tcmalloc、mimallocを比較した。
前回の記事でやったテストと同じく、以下のクラスを使って性能評価を行う。それぞれのクラスでメモリの使い方が全く異なるので、比較のしがいがある。
- HashDBM : ファイルのハッシュ表のデータベース。
- TreeDBM : ファイルのB+木のデータベース。
- SkipDBM : ファイルのスキップリストのデータベース。
- TinyDBM : オンメモリのハッシュ表のデータベース。
- BabyDBM : オンメモリのB+木のデータベース。
- CacheDBM : オンメモリのLRU自動削除機能付きハッシュ表のデータベース。
- StdHashDBM : オンメモリのstd::unorderd_mapのスレッドセーフなラッパー。
- StdTreeDBM : オンメモリのstd::mapのスレッドセーフなラッパー。
glibc標準のmallocはptmalloc(pthread malloc)を取り込んだものだが、それに比べて新しいアロケータ実装はマルチスレッドでの性能向上やフットプリントの削減などの工夫がなされているらしい。より優れたアロケータがあるならそれを標準に組み込めばいいじゃないか思ったりもするが、そんなに簡単な話じゃない。実際にはどのアロケータも一長一短なので、性能特性が大幅に変わる変更を標準に適用するのには慎重になるべきだ。
とても便利なことに、Linux上では、LD_PRELOADという環境変数を設定するだけで、ダイナミックリンクされた任意のシンボルの参照先を上書きすることができる。それを利用して、CやC++が使うmallocやfree等を置き換えてやれば、メモリアロケーションの仕組み全体を上書きできる。Ubuntu Linux上で、jemalloc、tcmalloc、minmallocを使って任意のコマンドを実行するには以下のようにする。
$ export LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libjemalloc.so $ tkrzw_dbm_perf sequence casket.tkh --dbm tiny --iter 1000000 $ export LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libtcmalloc_minimal.so.4 $ tkrzw_dbm_perf sequence casket.tkh --dbm tiny --iter 1000000 $ export LD_PRELOAD=/usr/local/lib/libmimalloc.so $ tkrzw_dbm_perf sequence casket.tkh --dbm tiny --iter 1000000
当然、独自アロケータのライブラリは事前にインストールしておく必要がある。Ubuntuでjemallocを使うには、aptでlibjemalloc-devをインストールしておく。Ubuntuでtcmallocを使うには、aptでlibtcmalloc-minimal4をインストールしておく。mimallocはまだUbuntuのパッケージになっていないので、githubのプロジェクトをcloneして、cmake、make、make installでインストールしておく。
さて、前回のテストコマンドでは、ライブラリの外側で各レコードのキーを作成するためにstd::stringを使っていたので、それをスタック上の固定長バッファに変更した。その上で、Set、Get、Removeを1000万回実行する処理のスループット(QPS)と使用メモリ(MB)を測定する。実行環境は私のノートPC(Dell XPS 13、Core i7 8550 1.8GHz、Ubuntu 20.10)である。まずは1スレッドで実行する。
$ tkrzw_dbm_perf sequence --dbm hash --path casket.tkh --iter 10000000 --buckets 20000000 $ tkrzw_dbm_perf sequence --dbm tree --path casket.tkt --iter 10000000 --buckets 500000 $ tkrzw_dbm_perf sequence --dbm skip --path casket.tks --iter 10000000 $ tkrzw_dbm_perf sequence --dbm tiny --iter 10000000 --buckets 10000000 $ tkrzw_dbm_perf sequence --dbm baby --iter 10000000 $ tkrzw_dbm_perf sequence --dbm cache --iter 10000000 --buckets 10000000 --cap_rec_num 11000000 $ tkrzw_dbm_perf sequence --dbm stdhash --iter 10000000 --buckets 10000000 $ tkrzw_dbm_perf sequence --dbm stdtree --iter 10000000
ptmallocの結果は以下である。
class | Set | Get | Remove | RAM Size |
HashDBM | 1,508,050 | 1,766,757 | 1,310,006 | 301.0 |
TreeDBM | 1,845,741 | 1,832,155 | 1,632,568 | 252.0 |
SkipDBM | 1,276,812 | 322,471 | 1,247,219 | 490.4 |
TinyDBM | 1,990,263 | 2,339,404 | 2205,398 | 524.1 |
BabyDBM | 2,538,813 | 2,727,522 | 2,394,496 | 524.3 |
CacheDBM | 2,069,940 | 2,413,604 | 2,347,044 | 696.8 |
StdHashDBM | 1,372,264 | 1,960,736 | 1,678,762 | 973.7 |
StdTreeDBM | 1,284,313 | 3,415,467 | 3,466,698 | 1045.9 |
jemallocの結果は以下である。
class | Set | Get | Remove | RAM Size |
HashDBM | 1,458,555 | 1,710,306 | 1,164,430 | 298.6 |
TreeDBM | 1,837,558 | 1,850,840 | 1,664,286 | 257.5 |
SkipDBM | 1,282,014 | 324,874 | 1,259,576 | 496.4 |
TinyDBM | 2,128,687 | 2,316,247 | 2,078,583 | 382.7 |
BabyDBM | 2,673,853 | 2,739,382 | 2,241,665 | 624.5 |
CacheDBM | 2,173,997 | 2,433,478 | 2,181,444 | 551.8 |
StdHashDBM | 1,460,878 | 1,926,894 | 1,644,095 | 828.7 |
StdTreeDBM | 1,560,228 | 3,750,296 | 3,543,499 | 905.4 |
tcmallocの結果は以下である。
class | Set | Get | Remove | RAM Size |
HashDBM | 1,542,681 | 1,811,943 | 1,326,561 | 299.4 |
TreeDBM | 1,932,377 | 1,917,843 | 1,729,262 | 255.9 |
SkipDBM | 1,394,514 | 349,292 | 1,314,656 | 1601.6 |
TinyDBM | 2,178,807 | 2,383,766 | 2,216,082 | 375.2 |
BabyDBM | 2,772,743 | 2,719,462 | 2,395,431 | 607.3 |
CacheDBM | 2,253,232 | 2,430,948 | 2,325,812 | 552.9 |
StdHashDBM | 1,470,630 | 1,938,507 | 1,659,231 | 832.8 |
StdTreeDBM | 1,878,209 | 4,017,116 | 3,924,973 | 905.2 |
mimallocの結果は以下である。
class | Set | Get | Remove | RAM Size |
HashDBM | 1,519,630 | 1,752,410 | 1,270,743 | 298.7 |
TreeDBM | 1,948,318 | 1,900,609 | 1,736,430 | 258.1 |
SkipDBM | 1,416,152 | 354,745 | 1,341,901 | 488.3 |
TinyDBM | 2,202,933 | 2,380,732 | 2,274,342 | 373.2 |
BabyDBM | 2,817,648 | 2,760,465 | 2,428,734 | 605.5 |
CacheDBM | 2,251,331 | 2,436,568 | 2,379,929 | 546.1 |
StdHashDBM | 1,490,603 | 1,983,881 | 1,722,699 | 823.5 |
StdTreeDBM | 1,900,565 | 4,177,729 | 4,100,049 | 896.1 |
シングルスレッドの場合、どれも大して変わらないというのが正直な感想だ。とはいえ、スループットの観点では、mimallocが最善で、tcmallocが次点だ。jemallocとptmallocの差は誤差の範囲と言っていいだろう。メモリ使用量の観点でもmimallocが最善っぽい。SkipDBMとtcmallocの組み合わせが1601MBも食うのが不思議だが、たまたまバルクで確保する閾値に到達したとかかな。
設計上、B+木のノードにデータを詰め込むBabyDBMの空間効率の方が連結リストでレコードを管理するTinyDBMよりも優れているはずなのだが、全てのアロケータの結果がその期待を裏切っている。この点については追って調査する。
マルチスレッドの性能も知りたいので、上述のテストケースを、4スレッドに割り振って行った。すなわち、各スレッドで250万回の操作を行う。
ptmallocの結果は以下である。
class | Set | Get | Remove | RAM Size |
HashDBM | 2,643,194 | 4,356,033 | 2,588,953 | 301.1 |
TreeDBM | 2,408,011 | 2,719,355 | 1,838,401 | 291.8 |
SkipDBM | 1,117,091 | 905,078 | 1,058,811 | 490.3 |
TinyDBM | 5,455,778 | 6,303,453 | 5,877,130 | 524.4 |
BabyDBM | 4,843,581 | 8,309,969 | 4,556,222 | 496.0 |
CacheDBM | 6,341,866 | 7,095,772 | 7,161,062 | 697.1 |
StdHashDBM | 1,498,996 | 6,764,005 | 1,877,066 | 973.9 |
StdTreeDBM | 1,507,654 | 11,431,082 | 2,927,514 | 1046.0 |
jemallocの結果は以下である。
class | Set | Get | Remove | RAM Size |
HashDBM | 2,733,122 | 4,647,909 | 2,665,435 | 298.9 |
TreeDBM | 2,368,122 | 3,309,385 | 2,352,603 | 282.4 |
SkipDBM | 1,119,892 | 889,502 | 1,036,205 | 472.2 |
TinyDBM | 5,456,939 | 6,470,301 | 5,703,449 | 383.0 |
BabyDBM | 5,187,206 | 8,528,203 | 4,662,478 | 507.9 |
CacheDBM | 7,161,404 | 7,570,785 | 6,977,306 | 552.0 |
StdHashDBM | 1,588,831 | 6,894,755 | 1,772,651 | 829.2 |
StdTreeDBM | 1,548,008 | 11,043,257 | 2,754,456 | 905.7 |
tcmallocの結果は以下である。
class | Set | Get | Remove | RAM Size |
HashDBM | 2,385,779 | 3,850,938 | 2,111,260 | 299.3 |
TreeDBM | 2,324,741 | 3,588,984 | 2,262,001 | 274.8 |
SkipDBM | 1,147,880 | 761,083 | 1,093,896 | 1601.4 |
TinyDBM | 5,572,654 | 6,498,672 | 4,646,193 | 375.2 |
BabyDBM | 5,195,974 | 7,948,482 | 4,430,870 | 494.6 |
CacheDBM | 7,376,519 | 7,408,686 | 4,981,618 | 553.0 |
StdHashDBM | 1,643,959 | 6,785,251 | 1,760,522 | 830.9 |
StdTreeDBM | 1,723,730 | 11,121,899 | 2,681,071 | 905.4 |
mimallocの結果は以下である。
class | Set | Get | Remove | RAM Size |
HashDBM | 2,722,551 | 4,573,680 | 2,737,330 | 298.7 |
TreeDBM | 2,564,950 | 3,653,247 | 2,407,662 | 286.9 |
SkipDBM | 1,203,908 | 999,628 | 1,146,788 | 488.4 |
TinyDBM | 5,401,855 | 6,589,596 | 5,920,478 | 373.3 |
BabyDBM | 5,510,589 | 8,513,050 | 4,775,588 | 491.4 |
CacheDBM | 7,323,357 | 7,629,429 | 7,417,484 | 546.3 |
StdHashDBM | 1,620,835 | 6,954,630 | 1,956,384 | 823.6 |
StdTreeDBM | 1,698,979 | 11,334,667 | 2,962,119 | 896.3 |
これも微妙な差だ。マルチスレッドでのスループットはjemallocとmimallocが他の2つよりも良いように見えるが、圧倒的にって感じではない。メモリ使用量はどれも誤差の範囲だろう。ここまでの結果だけから考えると、私ならmimallocを推すだろうけど、わざわざ標準たるptmallocからの乗り換えを広く推奨するほどでもないかな。しかし、特に副作用があるわけでもないので、とりあえずmimallocを使ってみるというのも悪くないとは思う。フラグメンテーションのしにくさなども含めて、実際のユースケースで試さないと、何が最適なのかはわからない。
そもそも、TkrzwのネイティブなAPIの中ではできるだけchar配列の固定長バッファやstring_viewを使って、stringをできるだけ使わないようにしている。stringは中でmalloc/freeを呼ぶからだ。とはいえ、HashDBMのSetの場合でも、1クエリあたり6回のmallocが呼ばれる。Getは7回だ。TreeDBMのSetでは、キャッシュがヒットした場合は1回しかmallocを呼ばない。Getは2回だ。オンメモリデータベースであるTinyDBMですら、SetでもGetでもはmallocを1回呼ぶだけだ。その他のクラスでも、1回のクエリで呼ばれるmallocの回数はそれほど多くないので、アロケータの影響が顕著というほどでもないという結果になったのだろう。
まとめ。Tkrzwの各種データベースクラスとメモリアロケータptmalloc、jemalloc、tcmalloc、およびmimallocを組み合わせた場合の性能を測定した。シングルスレッドだとmimallocとtcmallocの性能が良さげで、マルチスレッドだとmimallocとjemallocの性能が良さげだったので、総合的に見るとmimallocが良さそうだ。とはいえ、差が微妙なので、わざわざ非標準のアロケータを導入すべきかどうかは、ユースケース次第ということになるだろう。