1. ホーム
  2. c++

[解決済み] num++は'int num'のアトミックになり得るか?

2022-04-24 12:10:42

質問

一般に int num , num++ (または ++num ) の場合、読み取り・変更・書き込み操作としては アトミックでない . しかし、例えばコンパイラでよく見かけるのが GCC は、それに対して次のようなコードを生成します ( ここで試す ):

void f()
{
  int num = 0;
  num++;
}

f():
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], 0
        add     DWORD PTR [rbp-4], 1
        nop
        pop     rbp
        ret

に相当する5行目から num++ が1つの命令であると判断してよいでしょうか。 num++ は原子 この場合は?

もしそうなら というのは、そうして生成された num++ は、データ競合の危険性なしに並行 (マルチスレッド) シナリオで使用することができます。 (つまり、作る必要がないのです、例えば。 std::atomic<int> どうせアトミックなのだからと、関連するコストを課すのでしょうか?)

アップデイト

この質問は、次のことに注意してください。 ではない インクリメント atomicです(そうではなく、それが質問の冒頭部分です)。それは、それが できる つまり、1命令という性質を利用することで lock という接頭辞があります。また、受理した回答では、ユニプロセッサ・マシンの項で触れているように 本解答 と、そのコメント欄の会話などで説明されています。 できる (CやC++ではありませんが)。

どのように解決するのですか?

これは、C++が定義するところのデータレースであり、たとえあるコンパイラが、あるターゲットマシン上で期待通りのコードを生成したとしても、未定義の振る舞いを引き起こすものであることは間違いありません。そのため std::atomic を使用すると、信頼性の高い結果を得ることができます。 memory_order_relaxed のように、並べ替えにこだわらないのであれば。 を使ったコードとasmの出力の例を以下に示します。 fetch_add .


その前に、アセンブリ言語の部分の質問です。

num++は1命令なので( add dword [num], 1 )、この場合、num++はアトミックであると結論づけることができるでしょうか?

メモリデスティネーション命令(ピュアストアを除く)は、複数の内部ステップで起こる読み取り-変更-書き込み操作 . アーキテクチャのレジスタは変更されませんが、CPUはデータを内部で保持する必要があります。 ALU . 実際のレジスタファイルは、あるステージの出力を別のステージの入力として保持するラッチなど、最も単純なCPU内部のデータストレージのごく一部に過ぎません。

他のCPUからのメモリ操作は、ロードとストアの間でグローバルに見えるようになることがあります。つまり、2つのスレッドが add dword [num], 1 をループさせると、互いのストアを踏んでしまう。(参照 マーガレットの回答 をご覧ください)。2つのスレッドからそれぞれ40kインクリメントした後、実際のマルチコアx86ハードウェアでは、カウンタは(80kではなく)〜60kだけ上がったかもしれません。


アトミック(Atomic)とは、ギリシャ語で「分割できない」という意味です。 見る を別々の手順で行う。 すべてのビットを同時に物理的/電気的に瞬時に処理することは、ロード/ストアを実現する一つの方法ですが、ALUの演算ではそれすら不可能なのです。 ピュアロードとピュアストアについては、以下の回答で詳しく説明しています。 x86の原子性 一方、この回答は、read-modify-writeに焦点を当てたものです。

その lock プレフィックス は、システム内のすべての可能なオブザーバ(他のコアやDMAデバイス、CPUピンに接続されたオシロスコープではない)に対して操作全体をアトミックにするために、多くの読み取り-変更-書き込み(メモリ宛先)命令に適用することができます。そのために存在するのです。 (以下も参照 このQ&A ).

だから lock add dword [num], 1 アトミック . この命令を実行するCPUコアは、ロードがキャッシュからデータを読み込んでからストアがその結果をキャッシュにコミットするまで、キャッシュラインをそのプライベートL1キャッシュにModified状態で固定する。 これにより、システム内の他のキャッシュは、ロードからストアに至るどの時点でも、キャッシュラインのコピーを持つことができなくなります。 MESIキャッシュコヒーレンシープロトコル (または、AMD/IntelのマルチコアCPUで使用されているMOESI/MESIFバージョン)。 このため、他のコアによる操作は、処理中ではなく、その前後で行われるようです。

がない場合は lock プレフィックスを使用すると、他のコアがキャッシュ行の所有権を取得し、ロード後ストア前にそれを変更することができます。 他のいくつかの回答では、この点を誤解しており lock を使用すると、同じキャッシュ行のコピーが競合してしまいます。 コヒーレントキャッシュを持つシステムでは、このようなことは決して起こりえません。

(もし lock ed 命令は 2 つのキャッシュラインにまたがるメモリ上で動作しますが、オブジェクトの両方の部分への変更がすべてのオブザーバに伝搬する際にアトミックであることを確認するために多くの作業が必要になり、どのオブザーバもティアリングを見ることができません。 CPU はデータがメモリに到達するまで、メモリバス全体をロックしなけ ればならないかもしれません。 アトミック変数の配置を間違えないようにしましょう!)

なお lock プレフィックスは、命令をフルメモリバリアにすることもできます(たとえば MFENCE ) 、すべての実行時再順序付けを停止し、その結果、順次一貫性を与える。 (参照 Jeff Preshing氏の素晴らしいブログ記事 . 彼の他の記事もどれも素晴らしく、 ロット について、いいことづくめ。 ロックフリープログラミング x86やその他のハードウェアの詳細からC++のルールまで)。


ユニプロセッサーのマシン、またはシングルスレッド・プロセスの場合 は、1つの RMW インストラクション がないとアトミックにならない。 lock という接頭辞があります。他のコードが共有変数にアクセスする唯一の方法は、CPUがコンテキストスイッチを行うことですが、これは命令の途中では起こりえません。そのため dec dword [num] は、シングルスレッド・プログラムとそのシグナル・ハンドラ、あるいはシングルコア・マシン上で動作するマルチスレッド・プログラムの間で同期をとることができます。参照 別の質問に対する私の回答の後半 とその下のコメントで、より詳しく説明しています。


C++に戻る。

を使うのは全くもってインチキです。 num++ コンパイラに、単一の read-modify-write 実装にコンパイルする必要があることを伝えずに。

;; Valid compiler output for num++
mov   eax, [num]
inc   eax
mov   [num], eax

の値を使用すると、この可能性が非常に高くなります。 num コンパイラは、インクリメントの後、それをレジスタに保持します。 そのため、たとえ num++ は単体でコンパイルされるため、周囲のコードを変更すると影響を受ける可能性があります。

(その値が後で必要とされない場合。 inc dword [num] 最近の x86 CPU は、メモリ宛先の RMW 命令を、少なくとも 3 つの別々の命令を使用するのと同程度の効率で実行します。 面白い事実です。 gcc -O3 -m32 -mtune=i586 は、実際にはこのように表示されます。 Pentium)P5のスーパースカラ・パイプラインは、P6以降のマイクロアーキテクチャのように、複雑な命令を複数の単純なマイクロ操作にデコードしなかったからです。 次の図をご覧ください。 Agner Fogの命令表/マイクロアーキテクチャガイド をご覧ください。 x86 タグの wiki に多くの有用なリンクがあります (Intel の x86 ISA マニュアルを含む。PDF で自由に入手できます))。


ターゲット・メモリ・モデル(x86)とC++メモリ・モデルを混同しないこと

コンパイル時の並べ替え が許可されている . std::atomicで得られるもののもう1つは、コンパイル時の並べ替えを制御することであり、あなたの num++ がグローバルに見えるようになるのは、他の何らかの操作の後です。

典型的な例です。あるデータをバッファに格納して、別のスレッドで見ることができるようにし、フラグを設定する。x86 はロード/リリースのストアを無料で取得しますが、それでも、コンパイラに再注文しないように flag.store(1, std::memory_order_release); .

このコードは他のスレッドと同期することを期待しているかもしれません。

// int flag;  is just a plain global, not std::atomic<int>.
flag--;           // Pretend this is supposed to be some kind of locking attempt
modify_a_data_structure(&foo);    // doesn't look at flag, and the compiler knows this.  (Assume it can see the function def).  Otherwise the usual don't-break-single-threaded-code rules come into play!
flag++;

しかし、そうはならない。コンパイラは自由に flag++ は、関数呼び出しの向こう側にある (関数をインライン化したり、関数が flag ). そうすると、その修正を完全に最適化することができます。 flagvolatile .

(そして、C++はありません volatile std::atomicはコンパイラにメモリ上の値が非同期に変更されることを仮定させます。 volatile しかし、それ以上に重要なことがあります。 (実際には volatile int と std::atomic の mo_relaxed による類似性 は、ピュアロードとピュアストアの操作に使用されますが、RMWには使用されません)。 また volatile std::atomic<int> foo とは必ずしも同じではありません。 std::atomic<int> foo ただし、現在のコンパイラはアトミック(例えば同じ値を2回続けて保存する)を最適化しないので、volatile atomicでもコードジェネレーションは変わりません(笑)。

非アトミック変数のデータ競合を未定義動作と定義することで、コンパイラはループからロードやストアをシンクしたり、複数のスレッドが参照する可能性があるメモリに対して他の多くの最適化を行うことができます。 (参照 このLLVMブログ は、UBがどのようにコンパイラの最適化を可能にするかについての詳細です)。


先ほど述べたように x86 lock 接頭辞 はフルメモリバリアなので num.fetch_add(1, std::memory_order_relaxed); と同じコードを生成します。 num++ (デフォルトは逐次一貫性) ですが、他のアーキテクチャ (ARM など) ではもっと効率的です。 x86でもrelaxedを使えば、より多くのコンパイル時の並べ替えが可能になります。

これは、GCCがx86で実際に行っていることです。 std::atomic グローバル変数

ソース+アセンブリ言語のコードをきれいにフォーマットしたものを、以下のサイトでご覧ください。 ゴッドボルトコンパイラーエクスプローラー . ARM、MIPS、PowerPCなど、他のターゲットアーキテクチャを選択して、それらのターゲット用のアトミックからどのようなアセンブリ言語コードが得られるかを確認することができます。

#include <atomic>
std::atomic<int> num;
void inc_relaxed() {
  num.fetch_add(1, std::memory_order_relaxed);
}

int load_num() { return num; }            // Even seq_cst loads are free on x86
void store_num(int val){ num = val; }
void store_num_release(int val){
  num.store(val, std::memory_order_release);
}
// Can the compiler collapse multiple atomic operations into one? No, it can't.

# g++ 6.2 -O3, targeting x86-64 System V calling convention. (First argument in edi/rdi)
inc_relaxed():
    lock add        DWORD PTR num[rip], 1      #### Even relaxed RMWs need a lock. There's no way to request just a single-instruction RMW with no lock, for synchronizing between a program and signal handler for example. :/ There is atomic_signal_fence for ordering, but nothing for RMW.
    ret
inc_seq_cst():
    lock add        DWORD PTR num[rip], 1
    ret
load_num():
    mov     eax, DWORD PTR num[rip]
    ret
store_num(int):
    mov     DWORD PTR num[rip], edi
    mfence                          ##### seq_cst stores need an mfence
    ret
store_num_release(int):
    mov     DWORD PTR num[rip], edi
    ret                             ##### Release and weaker doesn't.
store_num_relaxed(int):
    mov     DWORD PTR num[rip], edi
    ret

x86は一般に強い順序ですが、StoreLoadの再順序付けは可能です。パイプラインで接続されたアウトオブオーダーCPUで良いパフォーマンスを得るには、ストアバッファを持つことが不可欠です。Jeff Preshingの メモリ再配列の摘発 の結果を示しています。 ない を使用し、実際のハードウェアで発生する並べ替えを実際のコードで表示します。


Re: @Richard Hodgesの回答に対するコメントで、次のような議論がありました。 コンパイラはstd::atomicをマージする num++; num-=2; 演算を1つの num--; インストラクション :

同内容のQ&Aを別途掲載しています。 なぜコンパイラは冗長な std::atomic 書き込みをマージしないのですか? ここで、私の答えは、以下に書いたことの多くを再述しています。

現在のコンパイラは、実際には(まだ)これを行いませんが、それは、行うことが許されていないからではありません。 C++ WG21/P0062R1: コンパイラはいつアトミックを最適化すべきですか? は、多くのプログラマがコンパイラが驚くような最適化を行わないという期待について、また、プログラマがコントロールできるようにするために標準に何ができるかを議論しています。 N4455 は、最適化できるものの例として、このようなものを多く取り上げています。 インライン化や定数展開によって、次のようなことが可能になることを指摘しています。 fetch_or(0) に変えることができるかもしれませんが、それは単なる load() (しかし、元のソースが明らかに冗長なアトミック操作を持っていなかったとしても、獲得と解放のセマンティクスは持っています)。

コンパイラが(まだ)それをやらない本当の理由とは (1) コンパイラが安全に(間違えずに)それを実行できるような複雑なコードを誰も書いていないこと。 最小驚嘆の原則 . ロックフリーのコードは、そもそも正しく書くのが難しいのです。 だから、原子兵器を気軽に使ってはいけない。原子兵器は安くないし、あまり最適化されない。 で冗長なアトミック操作を避けるのは、必ずしも簡単ではありません。 std::shared_ptr<T> とはいえ、これの非アトミックバージョンがないので(ただし ここでの答えの1つ を定義する簡単な方法があります。 shared_ptr_unsynchronized<T> gccの場合)。


に戻る。 num++; num-=2; であるかのようにコンパイルします。 num-- : コンパイラ は許可されています。 を実行する必要があります。 numvolatile std::atomic<int> . 並べ替えが可能な場合、as-ifルールによりコンパイラがコンパイル時に判断するのは 常に はそのようになります。 観察者が中間値を見ることができることを保証するものは何もありません ( num++ の結果)。

つまり、これらの操作の間に何もグローバルに可視化されない順序が、ソースの順序の要件と互換性がある場合 (ターゲットアーキテクチャではなく、抽象的なマシンの C++ ルールに従って)コンパイラは、単一の lock dec dword [num] の代わりに lock inc dword [num] / lock sub dword [num], 2 .

num++; num-- を見る他のスレッドとまだ Synchronizes With の関係を持っているため、消えることはできません。 num そして、それはアクワイアロードとリリースストアの両方であり、このスレッドでの他の操作の並べ替えを禁止しています。 x86 の場合、これは MFENCE にコンパイルできるかもしれません。 lock add dword [num], 0 (すなわち num += 0 ).

で説明したように PR0062 コンパイル時に隣接しないアトミックな操作をより積極的にマージすることは悪いことですが(例えば、進捗カウンターは反復毎に更新されるのではなく、最後に一度だけ更新される)、デメリットなしにパフォーマンスを向上させることもできます(例えば、"atomic" のコピーで ref counts の inc / dec がスキップされる)。 shared_ptr が生成され、破棄されることをコンパイラが証明できる場合、別の shared_ptr オブジェクトは、テンポラリの寿命の間、ずっと存在します)。

偶数 num++; num-- あるスレッドがロックを解除してすぐに再ロックした場合、マージはロック実装の公平性を損ねる可能性があります。 asm で実際にロックが解除されないと、ハードウェアの調停メカニズムでさえ、その時点で他のスレッドにロックを取得する機会を与えないでしょう。


現在のgcc6.2やclang3.9では、まだ別々の lock を使用しても memory_order_relaxed を、最も明らかに最適化可能なケースで ( ゴッドボルトコンパイラーエクスプローラー で、最新バージョンが違うかどうかを確認できます)。

void multiple_ops_relaxed(std::atomic<unsigned int>& num) {
  num.fetch_add( 1, std::memory_order_relaxed);
  num.fetch_add(-1, std::memory_order_relaxed);
  num.fetch_add( 6, std::memory_order_relaxed);
  num.fetch_add(-5, std::memory_order_relaxed);
  //num.fetch_add(-1, std::memory_order_relaxed);
}

multiple_ops_relaxed(std::atomic<unsigned int>&):
    lock add        DWORD PTR [rdi], 1
    lock sub        DWORD PTR [rdi], 1
    lock add        DWORD PTR [rdi], 6
    lock sub        DWORD PTR [rdi], 5
    ret