メモリの使い方を工夫しただけで、ハッシュデータベースのスループットが28%向上し、B+木データベースのメモリ使用量が14%または35%減ったという話。
前回の記事で、メモリアロケータ毎のデータベースの性能を測定した。私にとっては不思議なことに、込み入ったキャッシュ機構を前提としないHashDBMにおいて、アロケータ毎の性能の差が見られた。それは、mallocやfreeを呼ぶ回数が多いということ示している。そこでvalgrindで調べたところ、1クエリあたり6回ずつもmallocとfreeを呼んでいた。できるだけスタック上の固定長バッファを利用してレコードの読み書きを行うように実装していたつもりなのに、おかしい。
改めてコードを精査したところ、メモリマップI/Oを司るMemoryMapParallelFileクラスに非効率があった。そこでは、ゾーンI/OというAPIで、任意の領域の読み書きをアトミックにできる仕組みを実現している。そのゾーンの実装をカプセル化するためにPimplイディオムを使っていたのだが、それが多層化していたためにnewが2回も呼ばれていた。そのゾーンI/Oが1クエリあたり3回行われるので、合計6回のmalloc/freeが呼ばれていたというわけだ。
そのあたりを全て改善したところ、1度もmallocを呼ばずにクエリの実行ができるようになった。メモリマップI/Oは一切システムコールを呼ばずにファイルの読み書きができるので、さらにmallocも削れると、完全にシステムコールフリーになり、ユーザ空間だけの処理で決着が付くようになる。HashDBMに関しては、メモリアロケータの選定すらどうでもよくなる。これが理想の姿だ。いや、もともとそういう設計だったんだけども、実装時になぜかPimplイディオムを導入してそのことを忘れていた。
この改善により、HashDBMの性能がかなり向上した。シーケンシャルなキーの100万レコードを処理した場合のスループットは以下のようになる。
| Set | Get | Remove | |
| OLD 1-thread | 1,705,655 | 2,041,946 | 1,440,465 |
| NEW 1-thread | 2,194,855 | 2,544,004 | 1,918,255 |
| OLD 10-thread | 2,022,081 | 4,494,886 | 2,563,196 |
| NEW 10-thread | 2,235,611 | 4,751,245 | 2,690,573 |
すなわち、HashDBMの1スレッドのSetで28%、Getで24%、Removeで32%もスループットが向上する。10スレッドの向上率はそれよりは小さいが、それぞれ10%程度は向上する。
TkrzwのオンメモリデータベースであるTinyDBMとBabyDBMは、並列処理できることと、メモリ使用量が少ないことがセールスポイントだ。ハッシュ表と連結リストを使ったTinyDBMよりも、B+木を使ったBabyDBMの方がより省メモリになる設計だ。しかし、これまた前回の調査で、BabyDBMのメモリ使用量がTinyDBMのメモリ使用量よりも多いという、私にとっては不思議な現象が見られた。
この機会に、BabyDBMのメモリフォーマットを精査した。まず、以下のような構造体がある。それぞれ4バイトの整数でキーの長さと値の長さを持つ。sizeof(BabyRecord)は8バイトになる。
struct BabyRecord final {
int32_t key_size;
int32_t value_size;
};この構造体はキーと値を格納するデータ領域を持たないので、その直後にデータ領域を確保する関数を使う。
BabyRecord* CreateBabyRecord(std::string_view key, std::string_view value) {
BabyRecord* rec =
static_cast<BabyRecord*>(xmalloc(sizeof(BabyRecord) + key.size() + value.size()));
rec->key_size = key.size();
rec->value_size = value.size();
char* wp = reinterpret_cast<char*>(rec) + sizeof(*rec);
std::memcpy(wp, key.data(), key.size());
std::memcpy(wp + key.size(), value.data(), value.size());
return rec;
}xmallocはエラーチェック付きのmallocのラッパーとして私が定義したものだ。さて、mallocは、全ての組み込み型のアラインメントを遵守するアドレスを返すので、その先頭を構造体として利用した場合でも、当然各メンバのアラインメントは保証される。また、重要なのは、1つのレコードの全てのデータは1つの連続したメモリ領域に詰め込まれることである。これによって、mallocを呼ぶ回数は1回で済むし、関節参照のポインタのためのオーバーヘッドも必要なくなる。
キーと値のサイズを可変長データとして保持すれば、典型的には1バイトずつの合計2バイトでサイズ用のメタデータを管理できそうだ。しかし、B+木では比較関数で何度もレコードが評価されるので、空間効率よりも時間効率を優先したい。アラインメントされた1命令で評価できる固定長の方が時間効率が良いのだ。ちなみにTinyDBMは可変長でレコード毎メタデータを持つが、それは各クエリでレコードが1つか2つくらいしか評価されないからだ。
B+木のレコードはページ毎に管理されるのだが、それはポインタのベクタである。つまり、もし全てのレコードが単一ページに所属すると仮定すると、レコード毎のフットプリントは、参照用のポインタ1個8バイトと、メタデータの構造体8バイトと、そしてmallocによるオーバーヘッドを足したものになる。mallocのオーバーヘッドを16バイトと仮定すると、各レコード毎に合計32バイトのフットプリントを持つことになる。一方で、TinyDBMは、ハッシュ表のサイズがレコード数と同じと仮定すると、バケットのポインタ8バイト、連結リストのポインタ8バイト、キーと値の可変長データ2バイト、mallocのオーバーヘッド16バイトで、合計34バイトということになる。
アラインメントのためのパディング等も加味すると、32バイトと34バイトの差なんて誤差の範囲だ。とはいえ、BabyDBMのメモリ使用量は、TinyDBMとほぼ同じかちょっと少ないというくらいになるはずだ。しかし、前回の記事のテストでは、なぜかBabyDBMのメモリ使用量の方が顕著に多かった。
よって、コードを調査した。その結論としては、レコードのポインタのベクタのキャパシティの管理に非効率があったということだ。B+木のページのサイズが閾値に達した場合、そのページは分割される。その際には、既存のページのレコードの半分を新しいページに移動させるのだが、その際にキャパシティの明示的な調整をちゃんとしていなかった。古いページのレコードのポインタのベクタは、shurink_to_fitメソッドでキャパシティを減らして、使っていない領域をアロケータに返却すべきである。また、新しいページのレコードのポインタのベクタは、入れる予定の要素数の分だけreserveメソッドでキャパシティを設定して、無駄なコピーや不要な領域の確保を抑止すべきである。同じ理屈が内部ノードのリンクの配列にも当てはまる。
それらを全て実装したら、空間効率は改善した。100万レコードシーケンシャルアクセスと1億レコードランダムアクセスのテストのメモリ使用量は以下のようになる。
| 1 million | 100 million | |
| TinyDBM | 52.8 MB | 3573.5 MB |
| OLD BabyDBM | 63.5 MB | 2951.4 MB |
| NEW BabyDBM | 40.9 MB | 2605.4 MB |
BabyDBMの古いバージョンでも、ランダムアクセスの場合にはTinyDBMよりも元々空間効率が高かった。ランダムアクセスの場合、ページ分割した後にもキャパシティの余剰部分にレコードが入れられるので、無駄が少ないからだ。とはいえ、ランダムアクセスの場合でも、キャパシティの設定をきちんとするだけで、メモリ使用量が88%ほどに減少する。シーケンシャルアクセスの場合にはさらに効果てきめんで、メモリ使用量が63%にまで減少する。
つか、そもそもTinyDBMとBabyDBMのレコード毎のフットプリントの差は2バイトしかないはずなのに、こんなに差が付くのこそ気持ち悪いと思うかもしれない。おそらくそれはアラインメントのせいだ。このテストケースではキーと値が各8バイトなので、BabyDBMのレコード毎のアロケーションはmalloc(24)とキリがいいが、TinyDBMのレコード毎のアロケーションはmalloc(26)になるわけで、なんか効率悪そうだろう。アロケータによってはこの差はむしろ吸収されてしまうかもしれない。
まとめ。ベンチマークテストの結果を反省に活かして、Tkrzwのハッシュデータベースの時間効率とオンメモリB+木データベースの空間効率を改善した。メモリアロケーションの回数を減らしたり、ベクタのキャパシティの設定をするだけで、目に見える改善が見られた。性能分析って大事ね。
