malloc,TCMalloc,mimallocによる性能比較（各種メモリアロケータによる性能評価）
■はじめに
高速化のアプローチとして複数スレッドによる並列化があるが、並列度が上がるほどに管理コストがかかるので単純に高速化へは繋がらない。
そんな中で、malloc（というかfree）が遅いという事に気が付いたので、その調査結果と考察を載せておく。
butterfly searchのアルゴリズムとの相性が良いかどうかそういう結果になると思う。
そんな中で、malloc（というかfree）が遅いという事に気が付いたので、その調査結果と考察を載せておく。
butterfly searchのアルゴリズムとの相性が良いかどうかそういう結果になると思う。
■メモリアロケータ 3種類
- malloc（標準）： 標準のmalloc。 Visual Studio 2022 C++に組み込まれているそのままのメモリアロケータ。
- TCMalloc：google作成。C/C++用メモリアロケータ。高速なマルチスレッド実装が特徴。
- mimalloc：パフォーマンス特性に重点を置きMicrosoftによって開発された、自由かつオープンソースのコンパクトな汎用メモリ・アロケータ。
※他にもメモリアロケータはあったがコンパイルが上手くいかないので断念
■テストの内容
butterfly searchでテキストデータをインデックス化する時間を測定する。処理は大きく２つに分かれている。
- STEP1：単語の抽出。指定したスレッド数でメモリの取得解放を繰り返す。
- STEP2：データのソート。単一スレッドでメモリの取得解放を繰り返す。（マルチスレッド化不可処理）
※各STEPの出力はファイル。なのでメモリは基本的にはSTEP毎に解放する作りになっている。
■評価環境
CPU：AMD Ryzen 9 3950X
メモリ：48GB
OS:Windows11
コンパイラ：Visual Studio 2022 C++
■結果
mimallocが一番早いという結果になった。
※値が少ないほど高速
※メモリの処理時間を抜粋したものではなくbutterfly searchでの開始･終了時間
※メモリの処理時間を抜粋したものではなくbutterfly searchでの開始･終了時間
※インデックス対象のテキストサイズは13Gバイト
- 詳細
※値が少ないほど高速 単位（秒）
※時間時にはメモリ確保以外の処理時間も含まれる
（参考）ピークワーキングセット（１Gテキストファイル処理）
■気付いた事
- 並列度32-malloc（標準）の組み合わせでは、CPUの負荷が非常に低くなる時にがあった。調べるとそれはメモリ開放のタイミングであり、つまりはメモリ開放中は他のスレッドはメモリの開放及びメモリの再割り当て（realloc）ができないようだ。結果として、malloc（標準）を使うと他のスレッドが止まる。
- この絵は負荷が低い時に強制ブレークしたときの各スレッドの停止位置。ほぼすべてのスレッドがfree_baseで止まっている。
停止位置（HeapFree）
C:\Program Files (x86)\Windows Kits\10\Source\10.0.22621.0\ucrt\heap\free_base.cpp
- STEP2の処理時間は、STEP1の並列度によっても変化する。これは過去のメモリ操作が、次のメモリ操作へ影響する事を示している。並列度が高い場合は同時に使用するメモリ量が増えるので、必然的にメモリ空間が広くなりデータが散らばる。のちにガーベージコレクションが必要な状態になりやすい為と思わる。 （物の量が一緒でも部屋が広いと整理が大変みたいな）
- STEP2ではmalloc（標準）が一番性能が高かった。これはキャッシュのヒット率が高くなるように散らかさないような、データがメモリの一カ所に集まるような配慮が入っているのかもしれない。もしかするとmalloc（標準）が一番ガーベージコレクション動作が少ないエコな動作かもしれない。非力なPC向けに作られていると思わる。
■評価ポイントと思われること
- 同時にアロケータを呼んだ時、同時に処理できるか。
- メモリの整理（ガーベージコレクション）が必要な状態でも性能が維持できるか。→単純にmallocを繰り返すテストでは実運用での性能は計れない。
■結論
- シングルスレッドのアプリであれば標準のmallocがベスト。
- マルチスレッドのアプリでは、mimallocに切り替えるだけで2倍速くなることがある。（処理によっては7倍速くなる）→ butterfly searchでは相性の良かったmimallocを採用する。
コメント
コメントを投稿