C++11 std::atomicの速度調査

C++11から、C++は言語仕様としてマルチスレッドプログラミングをサポートするようになりました。
C++を使うからには、スレッド間の通信も高速化したいものです。
というわけで、スレッド間通信の速度(レイテンシ)を測ってみます。

想定しているのは、仕事の完了を通知したいなどの状況で、以下の条件を満たす場合です。

• 通信のレイテンシを隠蔽する仕事が残っていない。
• 一つのスレッドが書き込み、他のスレッドは読み込むだけである(※)。
• スレッド数の管理は他で行っているため、スピンロックを行っても安全である(スピード狂)。

(※)このような場合でも、C++では同じ変数を同時に読み書きした場合は未定義動作であるので、正しくプログラムを書く必要があります。

環境

• Intel Core i7-4771 @ 3.5GHz
• bash on Windows
• g++-7 (Ubuntu 7.2.0-1ubuntu1~16.04) 7.2.0
• コンパイル方法：g++-7 -pthread -O2

使用したコード

# include <iostream>
# include <vector>
# include <memory>
# include <thread>
# include <chrono>

# ifdef USE_CV
# include <mutex>
# include <condition_variable>
class cond_mutex {
        std::mutex mtx;
        bool ready;
        std::condition_variable cv;
public:
        cond_mutex() : ready(false) {}

        void wait_for_read() {
                std::unique_lock<std::mutex> lk(mtx);
                cv.wait( lk, [this]{ return ready; } );
        }

        void wait_for_write() {
                std::unique_lock<std::mutex> lk(mtx);
                cv.wait( lk, [this]{ return !ready; } );
        }

        void notify_end_read() {
                {
                        std::unique_lock<std::mutex> lk(mtx);
                        ready = false;
                }
                cv.notify_all();
        }

        void notify_end_write() {
                {
                        std::unique_lock<std::mutex> lk(mtx);
                        ready = true;
                }
                cv.notify_all();
        }
};
# else
# include <atomic>
class cond_mutex {
        std::atomic<bool> ready;
public:
        cond_mutex() : ready(false) {}

        void wait_for_read() { while( !ready.load() ); }
        void wait_for_write() { while( ready.load() ); }
        void notify_end_read() { ready.store(false); }
        void notify_end_write() { ready.store(true); }
};
# endif

void job( int id, int N, int loop, std::vector<cond_mutex>& vec ) {
	auto& ipr = vec[id];
	auto& opr = vec[(id+1)%N];
	for( int i = 0; i < loop; ++i ) {
		ipr.wait_for_read();
		opr.wait_for_write();
		opr.notify_end_write();
		ipr.notify_end_read();
	}
}

int main( int argc, char* argv[] ) {
	const int N_threads = std::stoi( argv[1] );
	const int N_loops = std::stoi( argv[2] );
	std::vector<cond_mutex> vec(N_threads);
	std::vector<std::unique_ptr<std::thread>> th(N_threads);
	for( int i = 0; i < N_threads; ++i ) {
		th[i] = std::make_unique<std::thread>( &job, i, N_threads, N_loops, std::ref(vec) );
	}
	const auto start = std::chrono::system_clock::now();
	vec[0].notify_end_write();
	for( int i = 0; i < N_threads; ++i ) {
		th[i]->join();
	}
	const auto end = std::chrono::system_clock::now();

	std::cout << std::chrono::duration<double, std::ratio<1, 1>>(end - start).count() << std::endl;
}

Nスレッドが輪番で仕事をやっていくという、プログラム(トークンリングのイメージ)です。

自明に遅いもの

条件変数(std::condition_variable)

スピンロックが使えない場合はこれを使うべきですが、OSが介在するためとても遅くなります。

速いもの

アトミック変数(std::atomic)

今回の用途では、アトミック変数を使うのがよさそうです。
アトミック変数を普通に使うと、不可分にアクセスするだけでなく、暗黙に逐次一貫性を満たしたアクセスが保証されます。
最適化によってメモリアクセスの順番が勝手に変わってしまったりしない、という意味です。

さらに進んで：弱いメモリバリア(std::memory_order_release)

今回のケースでは、書き込み時にstd::memory_order_releaseを用いても問題ありません。
弱いメモリバリアを使うときは、メモリ一貫性モデルについてよく理解したうえで細心の注意が必要です。
ただし、x86に限っては、ハードウェアレベルでそれなりに強いメモリ一貫性モデルを持っているため、プログラマができる最適化は、書き込み時にstd::memory_order_releaseを指定する以外に意味のあることをほとんどできません（loadの方はどのような場合でもMOV命令になり、storeの方はstd::memory_order_releaseかそれより弱ければMOV命令、std::memory_order_seq_cst(デフォルト)であればXCHG命令(orMOV命令+メモリフェンス命令)になります)。
その命令より後方に存在するロード・ストア命令が先行して実行されても問題ない場合は、これを指定するとよいでしょう。

速度調査

論理コア数は8なので、8スレッドを上限に測定しました。
100回実行し、その平均から一回当たりのレイテンシを推測しました。プログラムの実行にかかる時間には、スレッドを生成するなどの他の仕事や、OSが割り込んできた時間なども計上されますが、その割合は微々たるものです。
条件変数を使ったコードの場合は10万ループ、アトミック変数を使ったコードの場合は500万ループで計測しました(実行時間が0.5秒～5秒程度となるように調整しました)。

　実行時間

	条件変数	atomic	release
2スレッド	0.82±0.25(s)	0.59±0.06(s)	0.46±0.04(s)
3スレッド	1.05±0.14(s)	0.99±0.02(s)	0.79±0.01(s)
4スレッド	1.21±0.01(s)	1.37±0.03(s)	1.09±0.01(s)
5スレッド	1.58±0.01(s)	1.80±0.03(s)	1.41±0.01(s)
6スレッド	1.86±0.01(s)	2.25±0.03(s)	1.74±0.01(s)
7スレッド	2.25±0.14(s)	2.69±0.03(s)	2.06±0.02(s)
8スレッド	4.06±0.63(s)	3.28±0.60(s)	2.39±0.06(s)

なんだか条件変数を使った方はスレッド数を変えたときのばらつきが大きいですね……。
8スレッドフル稼働の場合は、他のプロセスに邪魔されるので、まともな測定結果とはいえなくなっています。

一通信当たりのレイテンシ(平均)

	条件変数	atomic	release
2スレッド	4080ns	59.3ns	45.6ns
3スレッド	3490ns	66.2ns	52.6ns
4スレッド	3040ns	68.7ns	54.4ns
5スレッド	3150ns	71.9ns	56.3ns
6スレッド	3110ns	75.0ns	57.8ns
7スレッド	3220ns	76.9ns	58.8ns
8スレッド	5080ns	81.9ns	59.8ns

先の結果から平均的なレイテンシを出すとこのようになります。
std::memory_order_releaseを使うだけで、35%程レイテンシが改善することがわかります。
ばらつき具合についてはこれだけではわかりません。

レイテンシのばらつき・待ち時間の計測

アトミック変数を使ったバージョンを使います。50nsという短い時間をタイマーで計測するのは、タイマーを読む時間がかかるせいでうまくいきません。そこで、どのくらいの計算が実行可能かで調べます。
while(...);となっていたところを、while(...)tmp += 1.0;に置き換えてみます。
この部分は、addsd xmm0, xmm1のようなアセンブリコードにコンパイルされます。
このwhileループを抜けてきたときにtmpがいくつになっているかを確認することで、何cycleくらい立ち止まっていたかを計測します。

	atomic	release
2スレッド	32.1± 3.5	92.1± 7.7
3スレッド	65.6±24.6	151.7± 9.4
4スレッド	99.2±36.7	201.9±22.4
5スレッド	124.5±47.0	236.2±28.4
6スレッド	174.7±53.9	286.1±34.4
7スレッド	207.0±59.3	317.4±36.9
8スレッド	240.5±44.2	347.6±33.2

std::atomicを普通に使った場合、待っている間に実行可能なaddsd命令の数は、大体33個くらいだということがわかりました。
addsd命令のレイテンシは5cycleで、このCPUは3.5GHzで動いているので、これにかかる時間は50nsくらいであり、おおむね合っていることがわかります。
std::memory_order_releaseを使った場合、実行速度は速くなっているのに、addsd命令をより多く実行できているという、一見不思議な現象が起こっています。これは、同期待ち(ストアが完了するのを待つこと)をしないため、ロード命令を先に発行できることによるものと考えられます。

余談

2スレッドの時、レイテンシが70cycleほどになる実行と、レイテンシが150cycleほどになる実行に分かれることがわかります。これは、おそらく両スレッドが同一コアで実行されていることによるものだと推測できます。

まとめ

• 条件変数を使うと、3～4マイクロ秒のレイテンシがある。
• std::atomicを普通に使うと、同一コア内なら20ns、別コアのスレッドなら40nsほどのレイテンシがある。
• std::memory_order_releaseを使えるときは使うと、そのレイテンシを35%ほど改善できる上、同期待ちに無駄な時間を費やさなくて済む。