特定のケースでは、int の増分は事実上アトミックですか? 質問する

Question

これはまさに、あるコンパイラがたまたまあるターゲットマシンで期待どおりの動作をするコードを生成したとしても、未定義の動作を引き起こすデータ競合として C++ で定義されているものです。std::atomic信頼性の高い結果を得るにはを使用する必要がありますが、この操作の順序を気にしない場合は、このスレッドの他の変数に対する他の操作と関連付けてを使用することができますmemory_order_relaxed。を使用したサンプルコードと asm 出力については、以下を参照してくださいfetch_add。

非変数のデータ競合が UB であるという事実atomicにより、C++ コンパイラは依然としてint積極的に最適化し、共有されていない変数 (およびシングルスレッドプログラム) に対して高速なコードを作成できます。

しかし、まず、質問のアセンブリ言語の部分です。

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

メモリ宛先命令（純粋なストア以外）は、複数の内部ステップで実行される読み取り、変更、書き込み操作です。アーキテクチャレジスタは変更されないが、CPUはデータを内部的に保持しながら、アルミニウム実際のレジスタファイルは、最も単純な CPU であっても内部のデータストレージのほんの一部に過ぎず、ラッチが 1 つのステージの出力を別のステージの入力として保持するなど、さまざまな機能を備えています。

他のCPUからのメモリ操作は、ロードとストアの間でグローバルに可視化される可能性があります。つまり、add dword [num], 1ループ内で実行されている2つのスレッドは、お互いのストアを踏んでしまいます。(@マーガレットの回答(わかりやすい図にするために、ここに引用します)。2 つのスレッドのそれぞれから 40k ずつ増加した後、実際のマルチコア x86 ハードウェアでは、カウンターは 80k ではなく、約 60k しか増加しなかった可能性があります。

「原子」はギリシャ語で「分割できない」という意味で、観察者が見る操作を別々のステップとして実行します。すべてのビットに対して物理的/電気的に同時に瞬時に実行することは、ロードまたはストアでこれを実現する 1 つの方法にすぎませんが、ALU 操作ではそれは不可能です。私は、純粋なロードと純粋なストアについて、x86 でのロードとストアのアトミック性一方、この回答は読み取り、変更、書き込みに重点を置いています。

のlock接頭辞多くの読み取り-変更-書き込み（メモリ宛先）命令に適用して、システム内のすべての可能なオブザーバー（CPUピンに接続されたオシロスコープではなく、他のコアとDMAデバイス）に関して操作全体をアトミックにすることができます。それが存在する理由です。（このQ&A）。

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

プレフィックスがないとlock、別のコアがキャッシュラインの所有権を取得し、ロード後、ストア前にそれを変更できるため、ロードとストアの間に別のストアがグローバルに表示されるようになります。他のいくつかの回答ではこの点が間違っており、プレフィックスがないと、lock同じキャッシュラインの競合するコピーが作成されると主張しています。これは、コヒーレントキャッシュを備えたシステムでは決して発生しません。

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

lockプレフィックスは命令を完全なメモリバリアに変換することにも注意してください（例：フェンス）、実行時の並べ替えをすべて停止し、順序の一貫性を実現します。（ジェフ・プレシングの素晴らしいブログ記事彼の他の投稿もすべて素晴らしく、多く良いものについてロックフリープログラミング(x86 やその他のハードウェアの詳細から C++ のルールまで)

単一プロセッサマシンまたはシングルスレッドプロセスの場合、独身者RMW実際に指示はプレフィックスなしのアトミックlock。他のコードが共有変数にアクセスする唯一の方法は、CPUがコンテキストスイッチを行うことですが、これは命令の途中では起こりません。したがって、プレーンはdec dword [num]シングルスレッドプログラムとそのシグナルハンドラ、またはシングルコアマシンで実行されるマルチスレッドプログラム間で同期できます。別の質問に対する私の回答の後半部分、およびその下のコメントで、これについてさらに詳しく説明しています。

C++に戻る:

num++単一の読み取り、変更、書き込みの実装にコンパイルする必要があることをコンパイラに伝えずに使用するのはまったく不正確です。

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

laterの値を使用する場合、これが発生する可能性が非常に高くなりますnum。コンパイラは、増分後にその値をレジスタ内に保持します。そのため、それnum++自体でコンパイル方法をチェックしたとしても、周囲のコードを変更すると影響を受ける可能性があります。

(値が後で必要ない場合は、inc dword [num]が推奨されます。最新の x86 CPU は、メモリ宛先 RMW 命令を、3 つの個別の命令を使用するのと少なくとも同じくらい効率的に実行します。興味深い事実:gcc -O3 -m32 -mtune=i586実際にこれを放出するなぜなら、（Pentium）P5のスーパースケーラパイプラインは、P6以降のマイクロアーキテクチャのように複雑な命令を複数の単純なマイクロオペレーションにデコードしなかったからです。Agner Fog の命令表 / マイクロアーキテクチャガイド詳細は86 の多くの便利なリンクについては、タグ wiki を参照してください (PDF として無料で入手できる Intel の x86 ISA マニュアルを含む)。

ターゲットメモリモデル（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++はvolatilestd::atomicの便利な代替ではありません。std::atomicは、コンパイラーがメモリ内の値がと同様に非同期的に変更できることを前提としますvolatileが、それだけではありません。（実際には、volatile int と mo_relaxed を使用した std::atomic の類似点純粋なロード操作と純粋なストア操作ではですが、RMW ではではありません。また、volatile std::atomic<int> fooはと必ずしも同じではありませんstd::atomic<int> fooが、現在のコンパイラはアトミック (同じ値の 2 つの連続したストアなど) を最適化しないため、 volatile アトミックによってコード生成が変更されることはありません。

非アトミック変数のデータ競合を未定義の動作として定義することで、コンパイラはループ外へのロードとシンクストアの実行を継続でき、複数のスレッドが参照する可能性のあるメモリに対する他の多くの最適化が可能になります。(このLLVMブログUB がコンパイラの最適化を有効にする方法の詳細については、こちらをご覧ください。

先ほども述べたように、x86lockプレフィックスは完全なメモリバリアであるため、を使用するとnum.fetch_add(1, std::memory_order_relaxed);x86 上でと同じコードが生成されますnum++(デフォルトは順次一貫性)。ただし、他のアーキテクチャ (ARM など) でははるかに効率的です。x86 でも、relaxed を使用するとコンパイル時の並べ替えが可能になります。

これは、グローバル変数を操作するいくつかの関数に対して、GCC が x86 上で実際に行うことですstd::atomic。

ソース+アセンブリ言語コードがきれいにフォーマットされているのを確認してください。Godbolt コンパイラエクスプローラ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

シーケンシャル一貫性ストアの後にMFENCE（完全なバリア）が必要であることに注意してください。x86は一般的に強い順序付けですが、StoreLoadの再順序付けが許可されています。パイプライン化されたアウトオブオーダーCPUで良好なパフォーマンスを得るには、ストアバッファを持つことが不可欠です。Jeff Preshingのメモリの並べ替えを現場でキャッチの結果を示していますないMFENCE を使用し、実際のコードで実際のハードウェア上で並べ替えが行われる様子を示します。

@Richard Hodgesの回答に関するコメントでの議論についてstd::atomic操作を 1 つの命令num++; num-=2;に統合するコンパイラnum--;:

同じ主題に関する別の Q&A:コンパイラはなぜ冗長な std::atomic 書き込みをマージしないのでしょうか?ここでの私の回答は、以下に書いた内容の多くを繰り返し述べています。

現在のコンパイラは実際にはこれを（まだ）実行しませんが、それは実行が許可されていないからではありません。C++ WG21/P0062R1: コンパイラはいつアトミックを最適化する必要がありますか?多くのプログラマーが、コンパイラーは「驚くべき」最適化を行わないだろうと期待していること、そしてプログラマーに制御権を与えるために標準が何ができるかについて説明します。N4455この例を含め、最適化できる多くの例について説明しています。インライン化と定数伝播によって、元のソースに明らかに冗長なアトミック操作がない場合でも、 fetch_or(0)which が単なるに変換できる可能性があるload()(ただし、取得と解放のセマンティクスは保持される) などのものが導入される可能性があることを指摘しています。

コンパイラが（まだ）それをしない本当の理由は、（1）コンパイラがそれを安全に（決して間違えることなく）実行できる複雑なコードを誰も書いていないこと、（2）それが潜在的に驚き最小の原則ロックフリーのコードはそもそも正しく書くのが大変です。ですから、核兵器を軽々しく使用してはいけません。核兵器は安くないし、最適化もあまりできません。std::shared_ptr<T>ただし、非アトミックバージョンがないため、冗長なアトミック操作を回避するのは必ずしも簡単ではありません（ただし、ここでの答えの一つgcc 用のを定義する簡単な方法を提供しますshared_ptr_unsynchronized<T>。

num++; num-=2;コンパイルを元の状態に戻すnum--: コンパイラ許可されているnumがでない限り、これを行うことはできませんvolatile std::atomic<int>。並べ替えが可能な場合、as-ifルールにより、コンパイラはコンパイル時に、いつもそのように起こります。観察者が中間値（num++結果）を見ることができるという保証は何もありません。

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

num++; num--は消えることができません。なぜなら、を参照する他のスレッドとの Synchronizes With 関係がまだ存在しnum、は、このスレッド内の他の操作の順序変更を許可しない acquire-load と release-store の両方であるためです。x86 の場合、これはではなく MFENCE にコンパイルできる可能性がありますlock add dword [num], 0(つまりnum += 0)。

で議論したように0062 ...コンパイル時に隣接していないアトミック操作をより積極的にマージすることは悪い結果をもたらす可能性があります (たとえば、進行状況カウンターは反復ごとに更新されるのではなく、最後に 1 回だけ更新されます)。ただし、欠点なしにパフォーマンスを向上させることもできます (たとえば、shared_ptr別のオブジェクトが一時的なオブジェクトの存続期間全体にわたって存在することをコンパイラが証明できる場合は、コピーが作成および破棄されるときに参照カウントのアトミックな増分/減分をスキップしますshared_ptr)。

1 つのスレッドがロックを解除してすぐに再ロックする場合、マージによってもnum++; num--ロック実装の公平性が損なわれる可能性があります。アセンブリ内で実際にロックが解放されない場合、ハードウェア仲裁メカニズムでも、その時点で別のスレッドにロックを取得する機会は与えられません。

現在の gcc6.2 および clang3.9 では、最も明らかに最適化可能な場合lockでも、個別の ed 操作が実行されます。(memory_order_relaxedGodbolt コンパイラエクスプローラ最新バージョンが異なるかどうかを確認できます。

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

Answer 1