HOME IP Messenger FastCopy Tech-memo Diary Twitter [English]

xxHashメモ(VC++用Tips、MT実験)

白水啓章
作成 2018/07/09

概要

xxHashのVC++用推奨オプションと、マルチスレッド実験測定データの記録です。

VC++利用時のお勧めコンパイルオプション

xxHash64を VS2017(C++)で「速度優先最適化」でビルドするだけでは、i5-8600K(3.6GHz)で 3.7GB/s程度の速度しか出ません。(またxxhash.hに記載してある XXH_INLINE_ALLを定義しても、何故か効果がありません)

いくつか試行錯誤したところ、xxHash自体のプロジェクトで、C/C++ → 最適化 → インライン関数の展開で「拡張可能否関数全て(/Ob2)」を適用すると、一気に 13.3GB/s と約3.6倍に高速化しました。
類似の状況でお困りの時はお試しください。

マルチスレッド化実験

xxHash64のマルチスレッド実験も行ってみました。

ハッシュ関数は、入力時に前回までの内部ステートを必要とするため、並列化できません。
その解決に使える方法として、「ハッシュ木」という固定ブロック毎にハッシュ値を算出し二分木を作る方法があり、局所的な書き換えによるハッシュ値の再計算(&ブロック毎の改竄検出)が容易という特徴から、ZFSやbtrfsで使われているようです。

今回、FastCopyでの高速なファイル用ベリファイ目的だったため、並列処理は行いたい一方でハッシュ木作成までは不要でした。
そこで、データをストライピングする形(8ストライプの場合、スレッド1は0,8,16...ブロックを処理、スレッド2は1,9,17ブロックを処理、…というイメージ)のマルチスレッド版を作成し、その速度を計測してみました。

結果、スレッド版は 16ストライプ、16KBブロック、i5-8600K(3.6GHz)という条件で、下記のように 2~4倍の高速化となりました。

処理領域サイズ 6スレッド版 オリジナル
6MB 60GB/s 14GB/s
1024MB 27GB/s 13GB/s

6コアCPUで6スレッドで実験していますが、実際は3スレッドの時点で性能上限に達しています(6MB & 1024MBともに)。
6MB処理=3次キャッシュのアクセス速度、1024MB処理=メインメモリのアクセス速度が律速要因になっている様子ですね。
(備考:スレッド版は、処理領域サイズ毎にスレッド同期が走るというオーバーヘッドも存在)