豪鬼メモ

一瞬千撃

各種メモリアロケータによる性能評価

C言語mallocC++言語のnewオペレータが呼ぶメモリアロケータをシステム標準の実装から変更した場合の、各種DBMクラスの動作速度とメモリ使用量を調べてみた。glibc標準のmalloc、jemalloc、tcmalloc、mimallocを比較した。
f:id:fridaynight:20210817194043p:plain


前回の記事でやったテストと同じく、以下のクラスを使って性能評価を行う。それぞれのクラスでメモリの使い方が全く異なるので、比較のしがいがある。

  • 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が良さそうだ。とはいえ、差が微妙なので、わざわざ非標準のアロケータを導入すべきかどうかは、ユースケース次第ということになるだろう。