錆から現実まで：Fetch_maxの隠された旅

QuestDBは、トレーディングフロアからミッションコントロールまで、ウルトラ低下のレイテンシ、高い摂取スループット、およびマルチ層ストレージエンジンを提供する、要求の厳しいワークロードのためのオープンソースのタイムシリーズデータベースです。 ParquetとSQLのネイティブサポートは、ベンダーのロックインはありません。

私は時折、エンジニアリングの役割の候補者にインタビューします。同時プログラミングを理解している人が必要です。私たちのお気に入りの質問の1つは、複数のプロデューサースレッドにわたって最大値を追跡することです。これは、多くの実際のシステムに表示される古典的なパターンです。

候補者は、任意の言語を使用できます。 Java（私が最もよく知っている言語）で、あなたは書くかもしれません CASループ、または機能的だと感じている場合は、使用してください updateAndGet() ラムダで：

AtomicLong highScore = new AtomicLong(100);
[...]
highScore.updateAndGet(current -> Math.max(current, newScore));

しかし、そのラムダは仕事をしている – それはまだフードの下でループしており、別の糸が干渉した場合に再試行している。ループをすぐに見ることができます Atomiclongのソースコード。

その後、1人の候補者が錆を選択しました。

彼がタイピングを始めたとき、私は続いていました。しかし、代わりに、彼はちょうど書いた：

high_score.fetch_max(new_score, Ordering::Relaxed);

「RustはFetch_Maxが組み込まれています」 彼はさりげなく説明し、問題の次の部分に進みました。

持続する。これはループパターンの周りのラッパーではありませんでした – これは一流の原子操作であり、隣に座っています fetch_add そして fetch_or。 Javaにはこれがありません。 C ++にはこれがありません。どうすれば錆びたのでしょうか…これを持っていますか？

インタビューの後、好奇心は私を良くしました。錆が提供される理由
fetch_max 内蔵の本質として？通常、固有のハードウェア命令を活用するために、内因性が存在します。しかし、x86-64にはありません atomic max
命令。そのため、パイプラインのどこかにCASループが必要でした。たぶん…いくつかのアーキテクチャがない限り する この指示はネイティブにありますか？もしそうなら、同じ錆コードは両方でどのように機能しますか？

私は見つけなければなりませんでした。ループはRustの標準ライブラリにありましたか？ LLVMでしたか？ x86-64のコード生成中に生成されましたか？

だから私は掘り始めました。私が見つけたのは、5つの異なるレイヤーのコンパイラ変換を通る魅力的な旅でした。それぞれが、そのループが正確に具体化された場所を見つけるまで、別のレベルの抽象化を剥がしました。私が発見したことを共有させてください。

その候補者が書いたものから始めましょう – 複数のスレッドから安全に更新できる単純なハイスコアトラッカー：

use std::sync::atomic::{AtomicU64, Ordering};
fn main() {
    let high_score = AtomicU64::new(100);
    // [...]
    // Another thread reports a new score of 200
    let _old_score = high_score.fetch_max(200, Ordering::Relaxed);
    // [...]
}
// Save this snippet as `main.rs` we are going to use it later.

このシングルラインは、それが約束することを正確に行います。原子的に現在の値を取得し、新しい値と比較し、新しい値が大きい場合に更新し、古い値を返します。安全で、簡潔で、台無しにすることは不可能です。明示的なループも、どこにも表示されないロジックを再試行しません。しかし、それは実際にフードの下でどのように機能しますか？

私たちの前に fetch_max コールは、マシンコード生成に近い場所に到達します。職場では別の抽象化の層があります。 fetch_max メソッドは、原子タイプごとに手書きではありません – 錆びたマクロによって生成されます atomic_int!。

Rustの標準的なライブラリソースコードを覗いてみると、 AtomicU64
そして、そのすべての方法は実際に作成されます
このマクロ：

atomic_int! {
    cfg(target_has_atomic = "64"),
    // ... various configuration attributes ...
    atomic_umin, atomic_umax,  // The intrinsics to use
    8,                          // Alignment
    u64 AtomicU64              // The type to generate
}

このマクロの内部、 fetch_max aとして定義されます
テンプレート
これは、あらゆる整数タイプで機能します。

pub fn fetch_max(&self, val: $int_type, order: Ordering) -> $int_type {
    // SAFETY: data races are prevented by atomic intrinsics.
    unsafe { $max_fn(self.v.get(), val, order) }
}

$max_fn プレースホルダーは交換されます atomic_umax 署名されていないタイプの場合 atomic_max 署名型タイプ用。この単一のマクロ定義は生成されます
fetch_max の方法 AtomicI8、 AtomicU8、 AtomicI16、 AtomicU16、など – ずっと AtomicU128。

だから私たちのシンプル fetch_max 呼び出しは実際に生成されたコードを呼び出しています。しかし、何をしますか atomic_umax 機能は実際に行いますか？それに答えるには、Rustコンパイラが次に生成するものを確認する必要があります。

今、私たちが知っている fetch_max マクロ生成コード呼び出しです atomic_umax、Rustコンパイラがそれを処理したときに何が起こるか見てみましょう。コンパイラはまっすぐにアセンブリに行きません。まず、コードを中間表現に変換します。 RustはLLVMコンパイラプロジェクトを使用するため、生成します LLVM中間表現（IR）。

LLVM IRを覗いてください fetch_max 電話、私たちはこのようなものを見ます：

; Before the transformation
bb7:
  %0 = atomicrmw umax ptr %self, i64 %val monotonic, align 8
  ...

これは、次のように言うLLVMの言語です 「Atomic Read-Modify-Write操作が必要です。実行したい変更は、署名のない最大値です。」

これは、コンパイラ自体内での強力で高レベルの命令です。しかし、それは批判的な質問を提起します：CPUには実際に呼ばれる単一の命令がありますか umax？ほとんどのアーキテクチャについては、答えはノーです。それで どうやって コンパイラはこのギャップを橋渡ししますか？

私の目標は、何が起こっているのかを説明するだけでなく、自分でそれを見るためのツールを提供することです。この変換は、自分のマシンで段階的に段階的にトレースできます。

まず、LLVM IRを生成した後にRustコンパイラに停止するように伝えます。

rustc --emit=llvm-ir main.rs

これはaを作成します main.ll ファイル。このファイルには、私たちを含む錆コードのLLVM IR表現が含まれています atomicrmw umax 命令。ファイルを保持します。次のステップで使用します。

重要なものがありません。錆はどのように機能しますか atomic_umax
実際にLLVM命令になります atomicrmw umax？これは、コンパイラの内因性が作用する場所です。

Rustのソースコードを掘り下げると、 atomic_umax は
このように定義されています：

/// Updates `*dst` to the max value of `val` and the old value (unsigned comparison)
#[inline]
#[cfg(target_has_atomic)]
#[cfg_attr(miri, track_caller)] // even without panics, this helps for Miri backtraces
unsafe fn atomic_umax(dst: *mut T, val: T, order: Ordering) -> T {
    // SAFETY: the caller must uphold the safety contract for `atomic_umax`
    unsafe {
        match order {
            Relaxed => intrinsics::atomic_umax::(dst, val),
            Acquire => intrinsics::atomic_umax::(dst, val),
            Release => intrinsics::atomic_umax::(dst, val),
            AcqRel => intrinsics::atomic_umax::(dst, val),
            SeqCst => intrinsics::atomic_umax::(dst, val),
        }
    }
}

しかし、これは何ですか intrinsics::atomic_umax 関数？あなたが その定義を見てください、あなたは少し珍しいものを見つけます：

/// Maximum with the current value using an unsigned comparison.
/// `T` must be an unsigned integer type.
///
/// The stabilized version of this intrinsic is available on the
/// [`atomic`] unsigned integer types via the `fetch_max` method. For example, [`AtomicU32::fetch_max`].
#[rustc_intrinsic]
#[rustc_nounwind]
pub unsafe fn atomic_umax(dst: *mut T, src: T) -> T;

体はありません。これは宣言であり、定義ではありません。
#[rustc_intrinsic] 属性は、この関数がコンパイラ自体が理解した低レベルの操作に直接マッピングすることをRustコンパイラに伝えます。 Rustコンパイラが電話をかけると intrinsics::atomic_umax、それは知っています
交換してください
対応するもので
LLVM固有関数。

だから私たちの旅は実際にはこのように見えます：

1. fetch_max メソッド（ユーザー面API）
2. マクロは拡張して呼び出します atomic_umax 関数
3. atomic_umax 本質的なコンパイラです
4. Rustcは、本質をLLVMに置き換えます atomicrmw umax ← 私たちはここにいます
5. LLVMはこの指示を処理します…

LLVMは、コードを分析および変換する一連の「パス」を実行します。私たちが興味を持っているものは呼ばれます
AtomicExpandPass。

その仕事は、 atomicrmw umax ターゲットアーキテクチャに尋ね、 「これをネイティブに行うことができますか？」

いつ x86-64 バックエンドは言います 「いいえ、できません」 このパスは、単一の命令をCPUよりも基本的なもののシーケンスに拡張します します
理解する。結果はaです
比較とスワップ（CAS）ループ。

このパスの前後にLLVMに中間表現を放出するように依頼することにより、この変換の変換を見ることができます。 IRを見るために 前に
AtomicExpandPass、 走る：

llc -print-before=atomic-expand main.ll -o /dev/null

ヒント：持っていない場合 llc インストールして、尋ねることができます rustc 直接パスを実行します。
rustc -C llvm-args="-print-before=atomic-expand -print-after=atomic-expand" main.rs

コードは端末に印刷されます。アトミックマックスを含む関数は次のようになります：

*** IR Dump Before Expand Atomic instructions (atomic-expand) ***
; Function Attrs: inlinehint nonlazybind uwtable
define internal i64 @_ZN4core4sync6atomic9AtomicU649fetch_max17h6c42d6f2fc1a6124E(ptr align 8 %self, i64 %val, i8 %0) unnamed_addr #1 {
start:
  %_0 = alloca [8 x i8], align 8
  %order = alloca [1 x i8], align 1
  store i8 %0, ptr %order, align 1
  %1 = load i8, ptr %order, align 1
  %_7 = zext i8 %1 to i64
  switch i64 %_7, label %bb2 [
    i64 0, label %bb7
    i64 1, label %bb5
    i64 2, label %bb6
    i64 3, label %bb4
    i64 4, label %bb3
  ]
bb2:                                              ; preds = %start
  unreachable
bb7:                                              ; preds = %start



  %2 = atomicrmw umax ptr %self, i64 %val monotonic, align 8
  store i64 %2, ptr %_0, align 8
  br label %bb1
bb5:                                              ; preds = %start
  %3 = atomicrmw umax ptr %self, i64 %val release, align 8
  store i64 %3, ptr %_0, align 8
  br label %bb1
bb6:                                              ; preds = %start
  %4 = atomicrmw umax ptr %self, i64 %val acquire, align 8
  store i64 %4, ptr %_0, align 8
  br label %bb1
bb4:                                              ; preds = %start
  %5 = atomicrmw umax ptr %self, i64 %val acq_rel, align 8
  store i64 %5, ptr %_0, align 8
  br label %bb1
bb3:                                              ; preds = %start
  %6 = atomicrmw umax ptr %self, i64 %val seq_cst, align 8
  store i64 %6, ptr %_0, align 8
  br label %bb1
bb1:                                              ; preds = %bb3, %bb4, %bb6, %bb5, %bb7
  %7 = load i64, ptr %_0, align 8
  ret i64 %7
}

あなたは見ることができます atomicrmw umax 指定されたメモリ順序に応じて、複数の場所での命令。これは、コンパイラバックエンドが理解している高レベルの原子操作ですが、CPUは理解していません。

llc -print-after=atomic-expand main.ll -o /dev/null

これは出力の関連部分です。

*** IR Dump After Expand Atomic instructions (atomic-expand) ***
; Function Attrs: inlinehint nonlazybind uwtable
define internal i64 @_ZN4core4sync6atomic9AtomicU649fetch_max17h6c42d6f2fc1a6124E(ptr align 8 %self, i64 %val, i8 %0) unnamed_addr #1 {
start:
  %_0 = alloca [8 x i8], align 8
  %order = alloca [1 x i8], align 1
  store i8 %0, ptr %order, align 1
  %1 = load i8, ptr %order, align 1
  %_7 = zext i8 %1 to i64
  switch i64 %_7, label %bb2 [
    i64 0, label %bb7
    i64 1, label %bb5
    i64 2, label %bb6
    i64 3, label %bb4
    i64 4, label %bb3
  ]
bb2:                                              ; preds = %start
  unreachable
bb7:                                              ; preds = %start
  %2 = load i64, ptr %self, align 8               ; seed expected value
  br label %atomicrmw.start                       ; enter CAS loop
atomicrmw.start:                                  ; preds = %atomicrmw.start, %bb7
  %loaded = phi i64 [ %2, %bb7 ], [ %newloaded, %atomicrmw.start ] ; on first iteration: use %2, on retries: use value observed by last cmpxchg
  %3 = icmp ugt i64 %loaded, %val                 ; unsigned compare (umax semantics)
  %new = select i1 %3, i64 %loaded, i64 %val      ; desired = max(loaded, val)
  %4 = cmpxchg ptr %self, i64 %loaded, i64 %new monotonic monotonic, align 8 ; CAS: if *self==loaded, store new
  %success = extractvalue { i64, i1 } %4, 1       ; boolean: whether the swap happened
  %newloaded = extractvalue { i64, i1 } %4, 0     ; value seen in memory before the CAS
  br i1 %success, label %atomicrmw.end, label %atomicrmw.start ; loop until CAS succeeds
atomicrmw.end:                                    ; preds = %atomicrmw.start
  store i64 %newloaded, ptr %_0, align 8
  br label %bb1
[... MORE OF THE SAME, JUST FOR DIFFERENT ORDERING..]
bb1:                                              ; preds = %bb3, %bb4, %bb6, %bb5, %bb7
  %7 = load i64, ptr %_0, align 8
  ret i64 %7
}

パスが最初の部分を変更しなかったことがわかります – メモリの順序に基づいてディスパッチするコードがまだあります。しかし、 bb7 ブロック、私たちは元々持っていた
atomicrmw umax LLVM命令では、完全な比較とスワップループが表示されます。コンパイラエンジニアはそれを言うでしょう atomicrmw umax 命令は、ハードウェアが実際に実行できるものに近い、より原始的な操作のシーケンスに「下げられ」られています。

これが簡素化されたロジックです：

1. 読む（シード）：現在の値をつかむ（expected）。
2. 計算： desired = umax(expected, val)。
3. 試み： observed, success = cmpxchg(ptr, expected, desired, [...])。
4. 成功した場合は、戻ります observed （古い値）。さもないと set expected = observed そしてループ。

このCASループは、ロックフリープログラミングの基本パターンです。コンパイラは、私たちのために自動的にそれを構築しました。

私たちは最後のステップにいます。最終的なマシンコードを表示するには、わかります rustc アセンブリを直接放出するには：

これはaを生成します main.s 最終アセンブリコードを含むファイル。内部では、次の結果が見つかります cmpxchg ループ：

.LBB8_2:
	movq  -32(%rsp), %rax       # rax = &self
	movq	(%rax), %rax        # rax = *self (seed 'expected')
	movq	%rax, -48(%rsp)     # spill expected to stack
.LBB8_3:                    # loop head
	movq	-48(%rsp), %rax     # rax = expected
	movq	-32(%rsp), %rcx     # rcx = &self
	movq	-40(%rsp), %rdx     # rdx = val
	movq	%rax, %rsi          # rsi = expected (scratch)
	subq	%rdx, %rsi          # set flags for unsigned compare: expected - val
	cmovaq	%rax, %rdx          # if (expected > val) rdx = expected; else rdx = val (compute max)
	lock cmpxchgq	%rdx, (%rcx)# CAS: if *rcx==rax then *rcx=rdx; rax 
	sete	%cl                 # cl = success
	movq	%rax, -56(%rsp)     # spill observed to stack
	testb	$1, %cl             # branch on success
	movq	%rax, -48(%rsp)     # expected = observed (for retry)
	jne	.LBB8_4             # success -> exit
	jmp	.LBB8_3             # failure → retry

構文はあなたが慣れているものとは少し異なって見えるかもしれません。それは、AT＆T Syntaxにあるためです。 rustc。 Intelの構文を好む場合は、使用できます rustc --emit=asm main.rs -C "llvm-args=-x86-asm-syntax=intel" それを得るために。

私はアセンブリの専門家ではありませんが、ここでCASループの重要な部分を見ることができます。

• シードリード（最初の反復）： 負荷 *self 期待値を初期化するにつれて。
• 分岐せずにumaxを計算します：ペア sub + cmova 実装 desired = max_u(expected, val)。
• CAS操作：x86-64で、 cmpxchg 用途 RAX 期待された値として、観測された値をに返すように RAX; ZF
  成功をエンコードします。
• 再試行または仕上げ： もし ZF 明確で、私たちは失敗し、再試行する必要があります。そうでなければ、私たちは完了です。

尋ねなかったことに注意してください rustc コードを最適化します。そうした場合、コンパイラはより効率的なアセンブリを生成します。スタックへの流出はなく、ジャンプが少なく、メモリの順序付けへの派遣はありません。

そして、私たちはそれを持っています。私たちの旅は完了しています。私たちは安全で明確な錆の単一の線から始め、アセンブリ言語で書かれたCASループで終わりました。

さび fetch_max → マクロ生成 atomic_umax → LLVM
atomicrmw umax → LLVM cmpxchg ループ → 組み立て lock cmpxchg ループ

この旅は、現代のコンパイラの力の完璧な例です。安全性とロジックに焦点を当てて、高レベルの抽象化で作業しますが、コンパイラはハードウェアの正しい効率的なコードを生成する乱雑でエラーが発生し、非常に複雑なタスクを処理します。

そのため、次回アトミックを使用するときは、コードが取られようとしている信じられないほど隠された旅に少し時間をかけてください。

PS：この旅を行った後、私はそれを学びました
C ++ 26追加 fetch_max

あまりにも！

PPS：私たちはそうです 雇用！

好奇心から、私はこれがApple Silicon（Aarch64）でどのように見えるかをチェックしました。このアーキテクチャにはネイティブがあります atomic max 指示、だから
AtomicExpandPass CASループに下げる必要はありません。パスの前後のLLVMコードは同一であり、まだ atomicrmw umax 命令。

最終的なアセンブリには、のバリアントが含まれています LDUMAX 命令。これはアセンブリの関連部分です。

ldr    x8, [sp, #16]     # x8 = value to compare with
ldr    x9, [sp, #8]      # x9 = pointer to the atomic variable
ldumax x8, x8, [x9]      # atomic unsigned max (relaxed), [x9] = max(x8, [x9]), x8 = old value
str    x8, [sp, #40]     # Store old value
b      LBB8_11

Aarch64が使用することに注意してください 統一されたアセンブラー言語、上記のスニペットを読むとき、宛先レジスタが最初に来ることを覚えておくことが重要です。

そして、それは本当にそれです。マイクロアーキテクチャを掘り続け、ハードウェアレベルで命令がどのように実行されるかを確認することができます。 LOCK プレフィックス、メモリ順序などの違いに飛び込みますが、それを別の日に任せます。

アリス： 「ここから行くべきで、どちらに行くべきか教えてください。」
猫： 「それはあなたがどこに行きたいかにかなりの量に依存します。」
アリス： 「私はどこであまり気にしません。」
猫： 「それなら、どの方向に行くかはそれほど重要ではありません。」
アリス： 「…どこかに着く限り。」
猫： 「ああ、あなたは十分に長く歩くならば、あなたはそれを確実にするでしょう。」

– ルイス・キャロル、不思議の国のアリスの冒険