読者です 読者をやめる 読者になる 読者になる

しらいとブログ

ネットで検索してもなかなか出てこないIT情報を独自にまとめています

C++11のmemory_orderの使い分け (2)

C++11のmemory_orderの使い分け (2)

2014/10/23 12:20 一部用語を修正しました。*1*2

前回はメモリバリアで保証できる範囲について説明しました。
今回はメモリバリアの使い方を説明します。

release/acquireバリア

release と acquire はセットで使います。release は store、acquire は load で使います。あるスレッド A が release で書き込んだ値 M を別のスレッド B が load で読み取れたときに、スレッド A の M より前の全ての書き込みがスレッド B で読み取れることを保証します。このとき、M 以外の値にはバリアは不要です。

// 初期値
int data;
std::atomic_int x(0);

// スレッド 1
data = 100;
x.store(10, std::memory_order_release);

// スレッド 2
int r = x.load(std::memory_order_acquire);
if (r == 10) {
	data;	// 100が保証される
}

x はアトミック変数なので中途半端な値で読み取られないこと、いつか読み取れるようになることが保証されています。そして、メモリバリアは x 以外の読み書きに影響を与えます。スレッド 2 の load でスレッド 1 が書き込んだ値 (10) を読み取れれば、スレッド1のそれ以前の書き込みが全て読み取れることが保証されます。つまり、data の値 (100) が読み取れることが保証されます。 store と load のどちらか片方でも relaxed にすれば data の値を読み取れる保証が無くなります。

また、バリアはループの中でも使えます。

// 初期値
int data;
std::atomic_int x(0);

// スレッド 1
data = 100;
x.store(10, std::memory_order_release);

// スレッド 2
int r;
do {
	r = x.load(std::memory_order_acquire);
} while (r != 10);
data;	// 100が保証される

ちなみに、このように他のスレッドの処理が終わるのを待つループをビジーウェイトと呼びます。長時間待つと CPU を無駄に使ってしまうというデメリットがありますが、数十回程度のループで終わるのであればスレッドを待機、再開させるよりもトータル負荷が小さくなるというメリットがあります。Java排他制御もビジーウェイトを使ったロック(スピンロック)と通常のロックを組み合わせてうまくやっています。実際に使うときはループ回数に制限を入れてください。

さて、ここからが重要なのですが、release / acquire バリアを一番使うのはポインタを渡す時です。

// 構造体の定義
struct Data {
	int x, y, z;
	Data() : x(10) {
		y = 20;
	}
};

// 初期値
std::atomic<Data*> data(nullptr);

// スレッド 1
Data* myData = new Data();
myData->z = 30;
data.store(myData, std::memory_order_release);

// スレッド 2
Data* r = data.load(std::memory_order_acquire);
if (r != nullptr) {
	r->x;	// 10が保証される
	r->y;	// 20が保証される
	r->z;	// 30が保証される
}

スレッド 2 の load でスレッド 1 の myData が読み取れれば、スレッド 1 の store 以前の書き込みが全て読み取れることが保証されるので、myData の x, y, z への書き込みが読み取れることが保証されます。store と load のどちらか片方でも relaxed にすれば x, y, z の全てで読み取れる保証が無くなります。コンストラクタの初期化や書き込みもメモリバリアが無ければ他のスレッドで読み取れない可能性があることに注意してください。

consumeバリア

consume は条件付きで acquire と同じ効果が得られるバリアです。一部の CPU で acquire よりも高速です。acquire が release 前の書き込みを全て読み取れるのに対して、consume は release 前の書き込みのうち、load で得られた値をアドレス計算に用いてアクセスした値だけ読み取れることが保証されます。

アドレス計算とはポインタや配列インデックスの計算のことだと思って構いません。

先ほどの release / acquire バリアの説明で出てきたポインタ渡しの例では load でポインタを読み取り、そのポインタから x, y, z を読み取っていたので acquire を consume にそのまま置き換えられます。

// 構造体の定義
struct Data {
	int x, y, z;
	Data() : x(10) {
		y = 20;
	}
};

// 初期値
std::atomic<Data*> data(nullptr);

// スレッド 1
Data* myData = new Data();
myData->z = 30;
data.store(myData, std::memory_order_release);

// スレッド 2
Data* r = data.load(std::memory_order_consume);
if (r != nullptr) {
	r->x;	// 10が保証される
	r->y;	// 20が保証される
	r->z;	// 30が保証される
}

配列のインデックスでも効果があります。

// 初期値
int data[10];
std::atomic_int index(-1);

// スレッド 1
data[5] = 100;
index.store(5, std::memory_order_release);

// スレッド 2
int r = index.load(std::memory_order_consume);
if (r > 0) {
	data[r];	// data[5] == 100 が保証される
}

data[r] は *(data + r) と同じになるので、load された r がアドレス計算に使われたことになり、store 以前の data[r] への書き込みを読み取れることが保証されます。

数値計算をしたり、ローカル変数に入れたりすることも可能です。

// 初期値
int data[10];
std::atomic_int index(-1);

// スレッド 1
data[5] = 100;
index.store(3, std::memory_order_release);

// スレッド 2
int r = index.load(std::memory_order_consume);
if (r > 0) {
	int i = r + 2;	// i == 5
	data[i];		// data[5] == 100 が保証される
}

アドレス計算によって保証された値をさらにアドレス計算に使った場合、consume は連鎖します。

// 初期値
int data[10];
std::atomic_int index(-1);

// スレッド 1
data[3] = 8;
data[8] = 100;
index.store(3, std::memory_order_release);

// スレッド 2
int r = index.load(std::memory_order_consume);
if (r > 0) {
	int i = data[r];	// i = data[3] == 8が保証される
	data[i];			// data[8] = 100 が保証される
}

load で読み取った値 r を data[r] でアドレス計算に使い、読み取れた値 i をdata[i] でアドレス計算に使っているため、data[r] と data[i] を読み取れることが保証されます。

load した値をアドレス計算に使わなければ consume の代わりに relaxed を指定した時と同じになります。

// 初期値
int data;
std::atomic_int x(0);

// スレッド 1
data = 100;
x.store(10, std::memory_order_release);

// スレッド 2
int r;
do {
	r = x.load(std::memory_order_consume);
} while (r != 10);
data;	// 100とは限らない

しかし、次のように無理やりにでもアドレス計算に含めれば効果があります。

// 初期値
int data;
std::atomic_int x(0);

// スレッド1
data = 100;
x.store(10, std::memory_order_release);

// スレッド2
int r;
do {
	r = x.load(std::memory_order_consume);
} while (r != 10);
*(&data + (r & 0));	// 100が保証される

r & 0 は必ず 0 になるので *(&data + (r & 0)) は *&data と同じで data になります。通常は r & 0 のような計算はコンパイル時の最適化で取り除かれるのですが、consume で load された値を用いた計算は最適化されて取り除かれることがありません。

注意点として、三項演算子 (?:) の条件や &&、||、,(コンマ) で使われた場合は計算ではなく分岐に使われたことになり効果がありません。

// 初期値
int data[10];
std::atomic_int index(-1);

// スレッド 1
data[5] = 100;
index.store(10, std::memory_order_release);

// スレッド 2
int r = index.load(std::memory_order_consume);
if (r > 0) {
	data[r == 10 ? 5 : 0];	// 100とは限らない
}

data[r == 10 ? 5 : 0] は r == 10 ? data[5] : data[0] と同じだと思って構いません。途中の計算結果を変数に入れても分岐とみなされます。

なお、無駄な計算をやりすぎると acquire バリアを使った時よりも遅くなるかもしれないので注意してください。

一応 consume の効果を途中で切る方法と、別の関数の中にも効果を継続させる方法が用意されています。

// 初期値
int data[10];
std::atomic_int x(0);

// 関数定義
[[carries_dependency]] int loadX()
{
	while (true) {
		int r = x.load(std::memory_order_consume);
		if (r != 0) return r;
	}
}

[[carries_dependency]] int increment(int n [[carries_dependency]])
{
	return n + 1;
}

// スレッド 1
data[1] = 100;
data[2] = 200;
data[3] = 300;
x.store(1, std::memory_order_release);

// スレッド 2
int r1 = loadX();						// r1 = 1
int r2 = increment(r1);					// r2 = 2
int r3 = std::kill_dependency(r1 + 2);	// r3 = 3
data[r1];	// 100が保証される
data[r2];	// 200が保証される
data[r3];	// 300とは限らない

[[carries_dependency]] をつけると consume の効果が継続されます。
loadX では戻り値で、increment では戻り値と引数 n で継続されています。

std::kill_dependency は consume の効果のある値を渡すと効果の無い値になって戻ってきます。

これらはコードが読みづらくなるので普通は使いません。そして、多くのコンパイラ[[carries_dependency]] は(まだ)実装されていません。

ところで、一般的な CPU では consume バリアは acquire バリアになります。なので、基本的に consume を使うことはありません。スマホのCPUでよく使われている ARM では consume の効果があるので使えるかもしれません。

seq_cstバリア

seq_cst バリアは release / acquire バリアの効果に加えて、複数のスレッドによる複数の変数の書き換え順序に一貫性を持たせる効果があります。言い換えると、release / acquire バリアだけでは複数のスレッドが複数の変数を書き換える時に順序に矛盾が出る可能性があります。例えば、あるスレッドが変数 A の値を 0 から 1 に書き換え、別のスレッドがほぼ同時に変数 B の値を 0 から 1 に書き換えたとします。release / acquire バリアだけでは、あるスレッドからは A == 0, B == 1 の瞬間が見え、別のスレッドからは A == 1, B == 0 の瞬間が見える可能性があります。seq_cst バリアがあれば A == 0, B == 1 か A == 1, B == 0 のどちらかに統一されます。

seq_cst バリア はメモリバリアの中で一番効果が大きく、一番負荷が大きいです。なので、なるべく使わないようにしたいところです。しかし、seq_cst バリアでなければまずいケースはよくあります。

例えば処理 A と処理 B を並行して実行し、両方の処理が終わったら処理 C を実行するケースです。

// 初期値
std::atomic_bool flagA(false);
std::atomic_bool flagB(false);

// プロトタイプ宣言
void executeA();
void executeB();
void executeC();

// スレッド 1
executeA();
flagA.store(true, std::memory_order_seq_cst);
if (flagB.load(std::memory_order_seq_cst)) {
	executeC();
}

// スレッド 2
executeB();
flagB.store(true, std::memory_order_seq_cst);
if (flagA.load(std::memory_order_seq_cst)) {
	executeC();
}

上記のコードは処理 A と処理 B の終わるのが遅かった方が処理 C を実行します。処理 A と処理 B が同時に終わったら両方同時に処理 C を実行することになります。また、seq_cst バリアは release / acquire バリアの効果もあるので、どちらが処理 C を実行しても、処理 A と処理 B で書き込まれた値を処理 C で読み取ることができます。

以下のコードのように release / acquire バリアを指定すると、どちらのスレッドも処理 C を実行しない可能性があるので注意してください。

// 初期値
std::atomic_bool flagA(false);
std::atomic_bool flagB(false);

// プロトタイプ宣言
void executeA();
void executeB();
void executeC();

// スレッド 1
executeA();
flagA.store(true, std::memory_order_release);
if (flagB.load(std::memory_order_acquire)) {
	executeC();
}

// スレッド 2
executeB();
flagB.store(true, std::memory_order_release);
if (flagA.load(std::memory_order_acquire)) {
	executeC();
}

処理 C を1回だけ実行したい場合は read-modify-write 命令を使う必要があります。

// 初期値
std::atomic_bool flagA(false);
std::atomic_bool flagB(false);
std::atomic_bool flagC(false);

// プロトタイプ宣言
void executeA();
void executeB();
void executeC();

// スレッド 1
executeA();
flagA.store(true, std::memory_order_seq_cst);
if (flagB.load(std::memory_order_seq_cst)) {
	if (!flagC.exchange(true, std::memory_order_relaxed)) {
		executeC();
	}
}

// スレッド 2
executeB();
flagB.store(true, std::memory_order_seq_cst);
if (flagA.load(std::memory_order_seq_cst)) {
	if (!flagC.exchange(true, std::memory_order_relaxed)) {
		executeC();
	}
}

exchange は値を書き込むと同時に書き込む直前の値をアトミックに返します。アトミック性によって、flagC が exchange で同時に書き換えられそうになっても、何らかの方法で順序付けがなされ、同時ではなかったように見えます。

上記のコードでは exchange にメモリバリアは不要です。処理 A と処理 B で書き込まれた値を処理 C で読み取れることは既に seq_cst バリアで保証されていますし、flagC 単体の読み書き順序はメモリバリアが無くても exchange のアトミック性で保証されています。他のスレッドが flagC に書き込んだ値が読み取れたときに flagC 以外で読み取る必要のある値は無いのでメモリバリアは不要です。

acq_relバリア

acq_rel バリアは read-modify-write 命令で使います。release / acquire バリアと同じで、あるスレッド A が書き込んだ値 M を別のスレッド B が読み取れたときに、スレッド A の M より前の全ての書き込みがスレッドBで読み取れることを保証します。

seq_cst バリアの説明で用いた、処理 A と処理 B を並行して実行し、両方の処理が終わったら処理 C を1回だけ実行するケースを別のやり方でやってみます。

// 初期値
std::atomic_int count(0);

// プロトタイプ宣言
void executeA();
void executeB();
void executeC();

// スレッド 1
executeA();
if (count.fetch_add(1, std::memory_order_acq_rel) == 1) {
	executeC();
}

// スレッド 2
executeB();
if (count.fetch_add(1, std::memory_order_acq_rel) == 1) {
	executeC();
}

fetch_add は指定した値を足した後、足す直前の値をアトミックに返します。アトミック性によって、count が fetch_add で同時に書き換えられそうになっても、何らかの方法で順序付けがなされ、同時ではなかったように見えます。

メモリバリアには acq_rel を指定します。acq_rel によって、一方のスレッドが足した値をもう一方のスレッドが読み取れたときに、先に足したスレッドのそれより前の書き込みが全て読み取れるので、どちらのスレッドが後でも処理Aと処理Bで書き込まれた値を処理Cで読み取れることが保証されます。そして、fetch_add のアトミック性による順序付けのおかげで、どちらか片方のスレッドが必ずもう片方のスレッドが足した値を読み取れます。

seq_cst バリアの説明で出てきた exchange を使った例と比べると弱いメモリバリアで同じ結果が保証されています。これは、seq_cst の複数の変数に対する順序の一貫性が、read-modify-write 命令のアトミック性によって保証される、同一の変数に対する順序の一貫性に置き換えられるからです。

read-modify-write 命令は非常に強力なので負荷が大きいです。その分上記のケースのようにメモリバリアを減らせる可能性があります。

なお、read-modify-write 命令には cst_seq も使えます。複数のアトミック変数を read-modify-write 命令で書き換え、それらの順序に一貫性が必要な場合に使います。

負荷について

メモリバリアと read-modify-write 命令の負荷の大きさは基本的に以下のような関係になります。

relaxed < release / consume < release / acquire < seq_cst < read-modify-write (relaxed)

read-modify-write 命令自体もメモリバリアを指定できるので、さらにメモリバリアの負荷が加わります。

read-modify-write 命令は強力なので、もし read-modify-write 命令を使うのであれば、他のメモリバリアを減らす方法が無いか確認してみましょう。もしかすると、read-modify-write 命令を使った方が速くなるケースもあるかもしれません。

次回に続く

今回はアトミック変数の使い方を説明しました。次回はフェンスの使い方を紹介します。

C++11のmemory_orderの使い分け (3)

C++11のmemory_orderの使い分け (4)

*1:read-modify-write アルゴリズム → read-modify-write 命令

*2:読み込み → 読み取り

広告を非表示にする