CompareAndSwapでロックフリーな並列処理を試してみた

こんにちは！　情熱開発部・プログラム課の日高です。

梅雨も明けて暑さが厳しくなる中、皆さんいかがお過ごしでしょうか？
涼しい場所でリラックスしながら、このブログを読んでいただければ幸いです。

今回はマルチスレッドプログラムで使用されるCompareAndSwapについて紹介しようと思います。
使い方の説明をした後に、Lockと比較して最適化の検証を行っていきます。

CompareAndSwap（CAS）について

CASは指定したメモリの値の比較と代入を排他的に行う機能です。

本来なら複数のスレッドから同じメモリの値を編集するには、Lockを使用する必要があります。
CASを使えばLock無しでこれを実現できます。

また、ロックを使わない事をロックフリーと呼びます。

CASを使用する目的

CASを使えばロックフリーなプログラムを書く事が出来ます。
その目的として以下のような例が挙げられます。

• Lockを使用したコードの最適化
• デッドロック等、ロックに起因するバグの対策

身近な所では、UE5でもカウンターやフラグの更新等に使用されています。

CASの動作

まずはCASの基本的な動作について確認していきましょう。

使用する言語等の環境によって名前や動作に違いはありますが、基本的な動作は以下のようになっています。

bool CompareAndSwap(int* ptr, int* compare, int exchange)

1. ptr と compare を比較
2. • 成功時：
     ptr に exchange を代入し、true を返す。
   • 失敗時：
     compare に ptr を代入し、falseを返す。

コードにするとこんな感じ。

ptr : 変更したい変数
compare : ptrと比較する値
exchange : ptrに代入したい値

bool CompareAndSwap(int* ptr, int* compare, int exchange)
{
    if (*ptr == *compare)
    {
        *ptr = exchange;
        return true;
    }
    *compare = *ptr;
    return false;
}

これら一連の動作は他のスレッドから干渉される事無く実行されます。

CASとLockの比較

CASが実際にLockより高速に実行できるのか確認する為に、簡単なコードを書いて検証してみました。

今回はc++11で使用できる、std::atomic::compare_exchange_weakと言う関数を使用しています。
https://cpprefjp.github.io/reference/atomic/atomic/compare_exchange_weak.html
引数が2つしかありませんが、atomicとして宣言された変数自体が、先に上げた例の第一引数「ptr」に当たります。

CASを使用した例

以下のコードでは、2つのスレッドでgValueを1秒間インクリメントし続け、最終的に何度インクリメントされたかを結果として出力します。

#include <atomic>
#include <thread>
#include <iostream>

// compare_exchange_weak を使うためにatomicとして宣言
std::atomic<int> gValue = 0;

void Increment()
{
	// スレッドの動作開始タイミングを合わせる
	while (!gActive){}

	while (gActive)
	{
		int oldValue = 0;
		do
		{
			// インクリメント前の値をキープしておく
			oldValue = gValue.load();
		}
		// gValue == oldValueならgValueを+1
		// 違ったらやり直す
		while(!gValue.compare_exchange_weak(oldValue, oldValue + 1));
	}
}

void Main()
{
	// スレッドを生成
	std::thread thread1(Increment);
	std::thread thread2(Increment);

	// インクリメント開始
	gActive = true;

	// 1秒後にスレッドを終了
	Sleep(1000);
	gActive = false;
	thread1.join();
	thread2.join();

	// 1秒間でインクリメントされた回数を表示
	std::cout << gValue << std::endl;
}

CASを使用している箇所の解説

CASで比較に失敗すると（つまり、19～22行目の間に別のスレッドからgValueを変更された場合）、インクリメントの計算を最初からやり直します。
CASで比較が成功し、値が更新されるまでこのループを繰り返します。

Lockを使用した例

こちらは、mutex::Lockを使用した例です。
スレッドの生成部分等はCASのコードと同じなので省いています。

#include <mutex>

std::mutex gMutex;

// ～～～

	while (gActive)
	{
		gMutex.lock();
		gValue++;
		gMutex.unlock();
	}

// ～～～

計測結果

LockとCASで5回ずつ計測した結果は、このようになりました。

・・・・・・Lockの方が速い！？

CASの方が速くなる事を期待していたのですが、このコードでは2つのスレッドが常にgValueを変更しようとしているため、CASの比較が頻繁に失敗してパフォーマンスが落ちてしまったようです。

再検証

今度はgValueへアクセスするタイミングをずらし、CASの比較が失敗しにくい状況で試してみました。
Sleepを挟むことでインクリメントのタイミングをずらしています。

CAS

		while (gActive)
		{
			Sleep(0);

			do
			{
				oldValue = gValue.load();
			}
			while(!gValue.compare_exchange_weak(oldValue, oldValue + 1));
		}

Lock

		while (gActive)
		{
			Sleep(0);

			gMutex.lock();
			gValue++;
			gMutex.unlock();
		}

計測結果

全体でのインクリメントされる回数は減りましたが、CASがLockを使用したコードより早くなりました！
CASの値の比較の段階で失敗する事が少なければ、CASの方が速くなる事を確認できました。

最初のコードは、CASにとってかなり悪い状況になっていたようです。
実際には一つの変数にここまで頻繁にアクセスするような状況は珍しいと思うので、多くの場合にCASを使うことで最適化ができそうです。

まとめ

今回はCASの紹介と実行速度の検証を紹介させていただきました。

CAS使えば最適化が期待できますが、必ずしもLockより高いパフォーマンスを維持できるわけではありません。
最適化目的で使用する場合は計測もしておきましょう。

また、CASを利用する際にはABA問題（https://ja.wikipedia.org/wiki/ABA%E5%95%8F%E9%A1%8C）の対応が必要な場合もあり、実装も複雑になりやすいので気を付けないといけません。

CASについてはABA問題への対処や、ロックフリーキュー等色々な情報が出ているので、興味の湧いた方はぜひ調べてみてください。

今回の検証は以下の環境で行いました。
・Visualstudio2022（v143）
・Windows SDK 10.0.22621.0
・ISO C++ 14 Standard

【免責事項】

本サイトでの情報を利用することによる損害等に対し、
株式会社ロジカルビートは一切の責任を負いません。