錆から現実へ：fetch_maxの隠れた旅

244日前原文(questdb.com)

概要

Rustの fetch_max は、他言語にはない 組み込み原子操作 として提供
実際には CASループ （比較して交換）で実装される
Rustコード→マクロ展開→コンパイラインストリンスィック→LLVM IR→CPU命令へと変換
LLVMが ターゲットアーキテクチャ に応じて最適な実装を自動選択
コード変換の 各レイヤー を追跡することで、Rustの抽象度と最適化の仕組みを理解

Rustのfetch_maxが実現する“組み込み原子操作”の裏側

QuestDB は高性能な時系列DB、 低レイテンシ・高スループット ・Parquet/SQL対応
並行プログラミング の面接課題で「最大値を複数スレッドから管理」問題を出題
Javaでは CASループ や updateAndGet （ラムダ式）で明示的に再試行処理
Rustでは fetch_max という一行で、原子的な最大値更新を実現
JavaやC++ には存在しない、Rust独自の first-class atomic operation
Rustの fetch_max は、実際にはハードウェア依存の命令ではなく、 CASループ で実装されるケースが多い

Rustのfetch_maxの実装構造

Rustの fetch_max は、 atomic_int! マクロによって各整数型ごとに自動生成
- AtomicU64, AtomicI32 など、全ての整数型に対応
- マクロ内部で atomic_umax/atomic_max 関数を呼び出し
atomic_umax は、 コンパイラインストリンスィック として宣言のみ（実装なし）
- #[rustc_intrinsic] 属性付きで、Rustコンパイラが直接LLVM命令に変換
Rustコンパイラはこの関数呼び出しを LLVM IR の atomicrmw umax 命令に変換
- atomicrmw umax は「原子的な最大値更新」命令を意味

LLVMによる最適化と変換

LLVMは AtomicExpandPass で、命令をターゲットCPUに最適化
- x86-64 など大半のCPUには atomic max命令 が存在しない
- LLVMは CASループ に自動展開
  - メモリから値を読み出し、比較、必要なら値を更新、CAS失敗なら再試行
この一連の処理は LLVM IR の変換過程で観察可能
- rustc --emit=llvm-ir でIRを出力
- llc -print-before=atomic-expand で展開前、 -print-after=atomic-expand で展開後を確認可能

実際のCASループ展開例（LLVM IR抜粋）

atomicrmw umax 命令が、 CASループ （compare-and-swapループ）に展開
- 値の読み出し→比較→最大値選択→CAS命令で書き換え→失敗時は再試行
これにより、Rustの fetch_max はシンプルなAPIでありながら、 安全かつ効率的 な並行最大値更新を保証

まとめ

Rustの fetch_max は、 抽象度の高いAPI でありつつ、 実行時には最適な低レイヤ実装 に変換
マクロ・インストリンスィック・LLVM IR・バックエンド最適化 の多層構造
ユーザーは 単一のAPI でプラットフォーム非依存の高性能原子操作を実現可能
他言語との違い や、 Rustコンパイラ/LLVMの最適化プロセス を理解することで、より安全・効率的な並行プログラミング設計が可能

Hackerたちの意見

それ、いい発見だね。LLVMが手書きのCASループをパターンマッチして、ネイティブのARM64命令に変換する逆の操作もやってるのかな。

└

それはとても良い質問だね。ちゃんとしたコンパイラエンジニアなら知ってるだろうけど、私も何か見つけて報告するように頑張るよ。編集: CASループを置き換えるためのパターンマッチングを持つパスは見つけられなかったよ。見つけた中で一番近いのはこれだね: https://github.com/llvm/llvm-project/blob/06fb26c3a4ede66755... CASのイディオムを認識するための似たようなパスを書くことはできると思うけど、その有用性は限られていて、努力やリスクに見合わないかも。

└

Godboltで確認したけど、ARMの代わりにRISC-V使ったら、そうは見えなかったよ。 https://gcc.godbolt.org/z/b5s4WjnTG （amomaxはアトミックfetch-max命令。lrとscはロードリザーブとストアコンディショナル命令で、scは通常のストアと似てるけど、前のlrでアクセスした時からアドレスが変更されていなければ成功する。つまり、アセンブリはCソースとほぼ一対一だよ。）

└

この技術の専門用語は「イディオム認識」で、かなり古いもので、APLコンパイラは50年以上前にイディオム認識を持ってたんだ。例えば、現代のCコンパイラで見ることができるのは、intのビット数を数えるための明らかなループを書くと、新しいCPUでは実際の機械コードが単一のポピュレーションカウント命令になること。CはRustのようなインストリンジックも、専用の「ポップカウント」機能も提供してないから、これを書くことはできないけど、明らかにそれが欲しいものなんだ。で、最適化されたCコンパイラはそれをやってくれるよ。ただ、LLVMは他のコンパイラの人たちが生成したIRを扱ってるから、イディオム認識の必要性は少ないと思う。Clangは認識を行い、Rustがそのインストリンジックのポピュレーションカウント core::intrinsics::ctpop のために行うのと同じLLVM IRに下ろすから、LLVMバックエンドはこれを見つける必要がないんだ。間違ってるかもしれないけど、そんな感じだと思う。

こんにちは、作者です。私の特技は、実用的な目的もなく、無駄に時間をかけて調査することです。たまにそのことについてブログを書いて、他の人への警告にしています。

└

こういう投稿が一番好きだから、シェアしてくれてありがとう！

└

「…実用的な目的がない」なんてことないよ、今日はコンパイルについて何か学んだし。シェアしてくれてありがとう。

└

記事、面白かったよ。PSでc++26の作業草案に追加したって見たけど、OpenMPの5.0の一部にもなったと思う。時々ARMみたいにハードウェアのアトミックが使われるけど、問題なのはx86やLL-SCアーキテクチャでも最適化されてない実装が一般的だってことだね。よく使われるのは汎用のCASループで、君のラムダの例みたいに、早期にカットアウトすることができない。オペレーションの反対側にある入力値を無視するために安価なアトミックリードを使ったり、最初のCASが失敗したらループから出ることもできる。ppc64のようなアーキテクチャでは、デフォルトとは少し異なるメモリオーダーを使うことで恩恵を受けることもある。こういうサポートは意外と役立つよ。もしこういうのが興味あるなら、これらの非リーディングバリアントにも興味があるかも。主にaddやmaxなどのためだけど、最近のアーキテクチャではリードバックをスキップするための代替操作を提供しているものもあるよ。論文では「アトミックリダクション操作」と呼ばれてるね。 https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p31...

└

いい記事だね！結局、その候補者を雇ったの？

└

部屋を見回して、みんな頷いてる。ああ、マジシャンだ。ようこそ。

└

共有してくれてありがとう、記事が大好きだったよ！

このブログを読んでたら、またメモリモデルの迷宮にハマっちゃった。毎回、やっと理解し始めたかなって思うけど、6行のリトマステストで4つのロードと2つのストアがあって、また落ち込んじゃう。CPUのメモリモデルの歴史について読むと、ちょっと気が楽になるよ。もしこれがIntelにとっても直感的じゃなかったなら、私も混乱してる仲間がいるってことだね。 https://research.swtch.com/hwmm#path_to_x86-tso 実は、対応する命令（risc-v amomax）を「実装」したときにfetch_maxについて知ってたけど、私のソフトCPUはまだシングルコアだから、楽しい部分にはまだ手を付けてないんだ。

Aarch64にはちゃんとしたアトミックmaxがあるけど、x86-64でも整数が64までならウェイトフリーのアトミックmaxができるよ。その場合、最大値を1 << iでロックオアを使えばいい。複数のレジスタを使うことで、例えばu8の最大値のために4つの64ビットレジスタを使うこともできる。ほとんどの場合、スレッドごとに最大値を別々に保存して、必要なときに全スレッドを一度ループさせて現在の最大値を計算する方がいいこともあるよ。

└

それ、面白いトリックだね。ただ、適用範囲が狭いからあんまり使えないかも。シェアしてくれてありがとう！

彼、仕事決まったの？

└

文化に合わなかったんだよね。

これ、O0でコンパイルしたの？生成されたコード、無駄に長い気がするんだけど。せめて、マッチジャンプテーブルはリラックス実装だけに絞ってほしかったな。

└

「rustcにコードの最適化をお願いしていないことに注意してください。もしお願いしていたら、コンパイラはもっと効率的なアセンブリを生成していました。スタックへのスピルもなく、ジャンプも少なく、メモリ順序のディスパッチもなし、などです。でも、元のIRにできるだけ近い出力を保ちたかったので、追いやすくするためです。RTFA」

読んでるとき、各スレッドがスレッドローカルの最大値を持ってて、定期的にグローバルなアトミックに同期することでパフォーマンスが向上するって言及されると思ってた。

└

候補者には似たような最適化を提案してほしいけど、この記事自体には必要ないと感じたな。

関連情報：fetch_maxは、以下のSPAA 2013の論文で言うところのアトミック「プライオリティアップデート」またはアトミック「最大値書き込み」の一例だね。このタイプのアトミック操作は、アトミックインクリメントのような他のものよりもはるかに低い競合を持つことができる。 https://doi.org/10.1145/2486159.2486189 https://jshun.csail.mit.edu/contention.pdf

└

実際にとても重要な論文の一つだね。もっと知られてほしいけど、幸運なことに「正しい」人たちは知ってると思う。

ちょっと待って。このコードはループパターンのラッパーじゃなくて、fetch_addやfetch_orのすぐ隣にある一級の原子操作なんだ。Javaにはこれがないし、C++にもない。どうしてRustだけが…これを持ってるの？C++26（進行中の作業）にはstd::atomic::fetch_maxがあるけど、まだどのツールチェーンにも実装されてないよ。 https://en.cppreference.com/w/cpp/atomic/atomic/fetch_max https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p04...

└

その情報は記事の後半に含まれてるよ: > PS: この旅を経て、C++26もfetch_maxを追加することを知ったよ！

面白い読書だった！これを読んで、もう一回「Java Concurrency in Practice」を読み直さなきゃなって思ったよ。

ハクソク