2026-10-25
versioned_cell.rs
use std::sync::atomic::{AtomicU64, Ordering};
fn update(cell: &AtomicU64, f: impl Fn(u32) -> u32) -> u32 {
}
cell の64ビットのうち、上位32ビットは版番号、下位32ビットは値です。いまの値に f を適用した結果を新しい値とし、版番号を1つ進めて cell に書き込む update を書き、進めたあとの版番号を返してください。版番号が u32::MAX のときは 0 に戻ります。読んでから書くまでの間にほかのスレッドが cell を書き換えていたら、その新しい内容から計算をやり直します。複数のスレッドが同時に update を呼んでも、更新が1つも失われてはいけません。
入力例 1
let cell = AtomicU64::new(5 << 32 | 10);
update(&cell, |v| v + 1)
出力例 1
6
cell の中身は 6 << 32 | 11
入力例 2
let cell = AtomicU64::new((u32::MAX as u64) << 32 | 7);
update(&cell, |v| v * 2)
出力例 2
0
cell の中身は 0 << 32 | 14
入力例 3
let cell = AtomicU64::new(0);
8スレッドがそれぞれ1000回 update(&cell, |v| v + 1)
出力例 3
cell の中身は 8000 << 32 | 8000
Reference
fn update(cell: &AtomicU64, f: impl Fn(u32) -> u32) -> u32 {
let mut cur = cell.load(Ordering::Acquire);
loop {
let version = ((cur >> 32) as u32).wrapping_add(1);
let next = (version as u64) << 32 | f(cur as u32) as u64;
match cell.compare_exchange_weak(cur, next, Ordering::AcqRel, Ordering::Acquire) {
Ok(_) => return version,
Err(actual) => cur = actual,
}
}
}
版番号と値を1つの AtomicU64 に詰めているので、両方を一度の不可分な操作で読み書きできます。compare_exchange_weak(cur, next, ..) は、cell の中身がまだ cur と等しいときだけ next を書き込んで Ok を返し、等しくなければ書き込まずに、そのときの中身を Err(actual) で返します。読んでから書くまでの間に誰かが更新していれば版番号が違うので、この比較で衝突が見つかります。値だけを比べると、ほかのスレッドが値を変えて元に戻した場合に、更新があったことを見逃します(ABA問題と呼ばれる取り違えです)。
衝突したら、actual を新しい cur として計算し直します。Err がいまの中身を返してくれるので、load し直す必要はありません。_weak 版は、中身が等しくても失敗を返すことがあります。どうせループで再試行するので、その場合も同じ道をもう一度通るだけです。再試行のたびに f を呼ぶので、引数の型は一度しか呼べない FnOnce ではなく Fn にしてあります。f に副作用があると、それが何回起きるかは衝突の回数で変わります。
取り出しと詰め直しはキャストで書けます。cur as u32 は上位を切り捨てて下位32ビットの値を、(cur >> 32) as u32 は版番号を取り出します。版番号の足し算に + 1 を使うと、u32::MAX のときにデバッグビルドでは panic し、リリースビルドでは黙って 0 に戻ります。wrapping_add なら、どちらのビルドでも 0 に戻ります。<< は | より先に結合するので、next の式に括弧は要りません。掲載したのは参考実装で、唯一の正解ではありません。AtomicU64::fetch_update を使うと、同じ再試行のループを標準ライブラリに任せられます。