ARM64でのatomic実装

はじめに

こちらは　NEC デジタルテクノロジー開発研究所 Advent Calendar 2023　17日目の記事です。

はじめまして。記事公開時点では自然言語処理の応用研究をしている藤井です。記事の内容は「なんでもいいよ〜」とのことなので、本記事では、組み込みソフトの業務をしていた頃を思い出しつつ、ARM64におけるatomic実装とその影響と対策について書いていきたいと思います。
　言語はC++で、(gccの固有拡張など使用せずに)C++11から導入された、std::atomicを使用します。動作環境は、RaspberryPi Model B(8GByte)¹を使用しております。行ったり来たりも面倒なので、ラズパイ上でVisualStudioCodeを動かして、Markdown原稿を直接書いていたりします・・・。

atomicって？

至るところで解説がありますので、googleで検索してください・・・というのはひどいので、まずは記事の導入として、atomicな処理がなぜ必要となるのか例示したいと思います。

例における想定としては、なにかメッセージを受け取って、マルチコアの恩恵を受けるべく、マルチスレッドで並列分散させ、処理した合計数を管理したい・・・そんな感じです。以下のように、マルチスレッドでグローバル変数gCounterをインクリメントするだけの単純な処理を使って説明していきます。10M回インクリメントする処理をマルチスレッドで10個並列に動作させます。

#include <iostream>
#include <thread>
#include <vector>

volatile unsigned long gCounter;

int main(void)
{
	
	std::vector<std::thread> worker_threads;

	for (unsigned int i =0 ; i< 10; i++){
		worker_threads.push_back(std::thread([]()
			{
				for(unsigned int j=0; j<10000000; j++){ 
					gCounter++;
				}
			}));
	}
	for (auto& e : worker_threads){
		e.join();
	}

	std::cout << gCounter << std::endl;
	
	return 0;
	
}

さて、実行するとgCounterはおいくつになるでしょうか？ソースの見た目上は、

10Mx10スレッド=100M（1億）

となりそうですが、実際に実行してみるとはそうはなりません。手元の環境では300万回弱の値を示すことが多いです。随分少ないです。

user@raspberrypi:~ $ g++ -O2 -g thread.cpp
user@raspberrypi:~ $ ./a.out 
29580994
user@raspberrypi:~ $ ./a.out 
28668077
user@raspberrypi:~ $ ./a.out 
29168923
user@raspberrypi:~ $ 

なぜ、こういうことが起きるのか、実際にコンパイルされたアセンブラを見て、原因を探っていきましょう。以下は実際にobjdumpコマンドを使用して表示したものです。

                                        gCounter++;
    1270:       f9406440        ldr     x0, [x2, #200]
                                for(unsigned int j=10000000; j>0; j--){ 
    1274:       71000421        subs    w1, w1, #0x1
                                        gCounter++;
    1278:       91000400        add     x0, x0, #0x1
    127c:       f9006440        str     x0, [x2, #200]
                                for(unsigned int j=10000000; j>0; j--){ 
    1280:       54ffff81        b.ne    1270 

for文のカウンタと最適化により入れ子になっていて見にくいですね²。そもそもアセンブラなんて見たこともない人も多数いるかと思います。アセンブラを初めて見る人向けに、説明に必要な３つのニーモニックを以下に説明します。

• ldr LoadRegisterの略。指定されたメモリ番地の値をレジスタに読み込みます。
• str StoreRegisterも略。レジスタの値を指定されたメモリ番地へ書き込みます。
• add 単語の意味そのまま、加算です。指定された値をレジスタに足します。

　３つなら、初めてでも大丈夫ですよね！。そこで、肝心なところ、gCounter++だけに注目して整頓したのが下記です。ここで、&gCounterは、変数gCounterのアドレスを示しているとお考えください。

	1270: ldr     x0, [&gCounter]	# gCounterをメモリから読み込んで、レジスタx0に代入
	1278: add     x0, x0, #0x1		# レジスタx0の値をインクリメント
	127c: str     x0, [&gCounter]	# レジスタx0の値をメモリに書き戻す
	

　つまり、C++の演算子"++"は、ARMのアセンブラでは、「メモリからのレジスタへの読み込み」「レジスタに１を足す」「レジスタからメモリに書き込む（更新する）」の３つの命令に分かれていたわけです。さぁ、ここでマルチスレッドだと、以下の様な不運が起こります。ここで、gCounterの値は100だったして時系列に書いてみます。

スレッド1										スレッド２
ldr     x0, [&gCounter]	#x0は100
add     x0, x0, #0x1	#x0は101
#ここで運悪くスレッド切り替え発生。
#インクリメントした結果はまだ書いていない！
												ldr     x0, [&gCounter]	#x0は再び100。
												add     x0, x0, #0x1	#x0は101
												str     x0, [&gCounter]	#メモリ上の値を101で更新
#ここで再びスレッド切り替え発生。
#メモリ上はスレッド２によってgCounterは101となっているが・・・
str     x0, [&gCounter]	#メモリ上の値を再び101で更新

スレッド１とスレッド２で、gCounter++を都合２回実施したのですが、102にならずに、101となってしまいます。ここで、"++"演算子は、他のスレッドに邪魔されずに、読み込み、加算、書き込みを一気通貫してやってほしいと思うのではないでしょうか？そう、それこそが、本記事のトピックであるatomic、すなわち、他から邪魔されることなく「不可分」にやってほしいということです。

C++11で導入されたstd:atomicとそのARM実装

　上記のコードを正しく意図したとおりに動かすだけなら、話は簡単です。includeを一つ足して、gCounterの宣言を以下の通りに変更するだけです。

#include <atomic>　// includeを追加
volatile std::atomic_ulong gCounter; // 宣言を変更

　コンパイルして、objdumpコマンドでダンプすると、gCounter++のfor文の該当するところは以下のアセンブラとなっています（わかりやすいように並べ替えをしています）。アセンブラの意味も補足しておきます。ここまでアセンブラを理解するとfor文のコンパイル結果がわかるようになりますね。

• bl:blanch 分岐命令です。ここでは、1500番地に飛びます
• mov:move レジスタ間で値を代入します
• subs: 引き算命令です。ここでは、x0レジスタから1を引きます(最後のsの意味は割愛)
• b.ne: 分岐命令です。subsの結果が0でなければ、分岐します。

#w19には、for文のカウンタ変数であるjが入っています。

    1350:       aa1403e1        mov     x1, x20 	// #x20はgCounterのアドレス
    1354:       d2800020        mov     x0, #0x1    // #1
    1358:       9400006a        bl      1500 <__aarch64_ldadd8_acq_rel>
    135c:       71000673        subs    w19, w19, #0x1
    1360:       54ffff81        b.ne    1350 

先程の、読み込み、加算、書き込みではなく、分岐命令になっています。雰囲気、C/C++言語風に書くと以下の感じです。つまり、関数として実装されています。

 __aarch64_ldadd8_acq_rel(1/*加算する数*/,&gCounter/*アドレス*/)

では、その先がどうなっているか、関係するところだけ抜粋したのが以下です。

    1518:       aa0003f0        mov     x16, x0			#加算する数をx16レジスタに退避
    151c:       c85ffc20        ldaxr   x0, [x1]		#gCounterの値をメモリから読み出し
    1520:       8b100011        add     x17, x0, x16	#1を加えて、レジスタx17へ
    1524:       c80ffc31        stlxr   w15, x17, [x1]	#x17の値をgCounterのメモリへ。w15？
    1528:       35ffffaf        cbnz    w15, 151c 		#w15の値が0でなければ、もう一度やり直し

ここで、今までのldr/strと似て異なる、ldaxr/srlxrが今回の肝となります。

• ldaxr: Load-Acquire Exclusive Register

  • 指定されたアドレスから値を読み込むのと同時に、「このアドレスは排他でアクセスするよ」というフラグのようなものを、特別な場所³にセットする
  • ベースとなる基本命令は、ldrexで、メモリバリア云々で、a(Acquire)が入っています。詳細は割愛します。

• stlxr: Store-Release Exclusive Register

  • 指定されたアドレスに書き込みを試みる。上記のフラグを活用し、もし、排他的にアクセスできていれば0、そうでなければ（他のCPUに割り込まれた等で、同じ場所にアクセスがあった場合）1を返す
  • ベースとなる基本命令は、strexで、メモリバリア云々で、l(reLease)が入っています。同じく詳細は割愛します。

• cbnz: Compare and Branch on Nonzero

  • 指定されたレジスタが０でなければ、指定された番地に飛びます

　では、再びスレッドが２つあって、競合した場合にどのような動作になるか、時系列に書いてみましょう。

		スレッド1								スレッド２
		ldaxr	x0, [&gCounter]	#x0は100
		add     x17, x0, x16	#x16は1
		#ここで運悪くスレッド切り替え発生。
		#インクリメントした結果はまだ書いていない！
												ldaxr	x0, [&gCounter]	#x0は100
												add     x17, x0, x16	#x16は1
												stlxr   w15, x17, [x1] 	#メモリ更新に挑戦
												#割り込みはなかったので、メモリを更新。w15は0
												cbnz    w15, 151c
												#ジャンプせず、次の命令へ
		#ここで再びスレッド切り替え発生。
		#メモリ上はスレッド２によってgCounterは101となっている
		stlxr   w15, x17, [x1] 	#gCounterのメモリ更新に挑戦
		#スレッド２に割り込まれたので、書き込みは失敗。w15には1が設定されている
		cbnz    w15, 151c
		＃最初に戻ってやり直し
		ldaxr	x0, [&gCounter]	#x0は101
		add     x17, x0, x16	#x16は1。x17は、102に
		stlxr   w15, x17, [x1] 	#メモリ更新に挑戦
		#割り込みはなかったので、102という値でメモリを更新。w15は0
		cbnz    w15, 151c
		#ジャンプせず、次の命令へ

　以上のようになり、意図したとおりに動作します。はい、これで不具合は解決しました！・・・とは終わらせないのが本記事です。

atomicの性能への影響と対策

　少し考えていただくと、これって、「失敗したら、うまく行くまで何度でも再挑戦します！」という動作です。今回、あえて単純な処理をスレッド１０個もならべて競合が起きるようにしているという背景もありますが、実際、すごく遅いです。timeコマンドで手元の環境で計測すると以下のようになります。ラズパイといえど、マルチコア環境。realの数字は一旦無視して、実際複数のCPUが動いた時間を見てみると、atomicがついていない環境では、400msec程度だったものが、25秒もかかっています。60倍位遅いという結果になっています。

atomicがついている場合

real	0m6.379s
user	0m25.116s
sys		0m0.020s

atomicがついていない場合

real	0m0.118s
user	0m0.408s
sys		0m0.000s

　こんなに性能が落ちるなら、排他制御ができてないから、排他制御をちゃんとしよう！というコインの裏表的な対策ではなく、そもそも排他制御が不要な処理にできないか？ということを考えてみる価値もありますね⁴。

　たとえば、下記のように各スレッドの作業領域を確保して、お互いに関わり合いの無いようにするだけで、実は期待どおりに動きますし、性能も確保できます。

#include <iostream>
#include <thread>
#include <vector>

#define MY_MAX_THREADS (10)

volatile unsigned long gCounter[MY_MAX_THREADS];

int main()
{
	unsigned int all=0;
	std::vector<std::thread> worker_threads;

	for (unsigned int i =MY_MAX_THREADS ; i> 0; i--){
		worker_threads.push_back(std::thread([i]()
			{
				for(unsigned int j=10000000; j>0; j--){ 
					gCounter[i-1]++;
				}
			}));
	}
	for (auto& e : worker_threads){
		e.join();
	}

	for(unsigned int i=0;i<MY_MAX_THREADS;i++){
		all+=gCounter[i];
	}
	std::cout << all << std::endl;
	
	return 0;
	
}

　下記の様に正しく、結果は1億、実行速度も速いままです。

atomic無しでもメモリを分けた場合

user @raspberrypi:~ $ time ./a.out
100000000

real 0m0.117s
user 0m0.414s
sys 0m0.000s

作業領域の確保の仕方は、この界隈の話題で出てくるTLS(Thread Local Storage)などいくつかあるかと思いますが、本記事では説明を割愛させていただきます。

さいごに

本記事では、 以下の内容について説明しました。

1. 最初にマルチスレッド環境下においては、単純なグローバル変数のインクリメントでさえ正しく動かないこと⁵を例示
2. 対策としてアトミック処理をC++11で実装されたstd::atomicを適用して実現することで動作することを説明
3. ARM64環境におけるアトミック処理のコンパイル結果を見ながら、実際の動作と性能への影響を説明
4. データの持ち方によっては、アトミック処理を適用しなくても、正しく動作させることが可能なことを例示

　マルチスレッド環境では、データの持ち方一つでデータ破壊の不具合の可能性や、たとえ、ただしく保護したとしても性能へのインパクトがあること、逆にデータの持ち方一つでデータ破壊を回避し性能は維持できる可能性をうまく表現できていたら幸いです。テストで見つけるのも難しいケースもあるかと思いますので、ソースコードレビューを頑張りましょう！

1. uname -aの結果：Linux raspberrypi 6.1.0-rpi7-rpi-v8 #1 SMP PREEMPT Debian 1:6.1.63-1+rpt1 (2023-11-24) aarch64 GNU/Linux ↩

2. 実際には最適化をかけないほうがもっと複雑です・・・。 ↩

3. (Global) Exclusive Monitorという ↩

4. スレッドで行う処理が十分に重ければ、atomic指定による性能劣化はもちろん無視できます。ほとんどの場合、そういうケースかも。その場合は、読みやすさ、理解しやすさを重視する選択もありえます。 ↩

5. スレッドセーフではないとも ↩