CPU がプログラムを実行していくとき、計算処理だけでなく、メモリに対する読み書きも行う。
メモリからの読み出しやメモリへの書き込みをこの記事では「メモリアクセス」と呼ぶことにするが、 CPU は、常にプログラムに書かれた通りの順序でメモリアクセスを行うわけではない。順序を入れ替えることがある。
プログラムによっては、順序の入れ替えによって動作が変わってしまい、不具合が起きることもある。
順序の入れ替えを防ぐための手段も用意されているが、それを行うとプログラムの動作速度が下がる可能性がある。
この記事では、メモリアクセス順序の入れ替えが発生すること、そしてそれによってプログラムの挙動が変わるケースがあることを、実際のコードで示す。その後、 CPU によるメモリアクセス順序の入れ替えを禁止する方法と、それがプログラムの動作速度に与える影響について見ていく。
なお、コンパイラもメモリアクセス順序の入れ替えを行うことがある。ソースコードに書かれている順序とは異なる順序でバイナリファイルなどを出力することがある。
本記事では CPU による順序入れ替えを扱い、コンパイラによる入れ替えは扱わない。
この記事の内容は以下の環境で動作確認した。
$ lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 24.04.4 LTS Release: 24.04 Codename: noble $ uname -m x86_64 $ nproc --all 8 $ rustc --version rustc 1.99.1 (58cf8f9c3 2026-10-13)
そもそもなぜメモリアクセス順序を入れ替えるのか
CPU がメモリアクセスの順序を入れ替えるのは、処理の高速化が目的である。
メモリアクセス A のあとにメモリアクセス B を行う、というプログラムがあるときに、メモリアクセス A よりも先にメモリアクセス B を行ったほうが全体として処理が速くなる、というときに入れ替えることがある。
もちろん速度のみを基準にして自由に入れ替えていたらプログラムはまともに動かなくなるので、入れ替えは、一定の規則の範囲内で行われる。
何をどのように入れ替えるのかは、命令セットアーキテクチャによって異なる。例えば、x64はArmなどと比べて入れ替えに慎重であり、入れ替えが発生するケースは相対的に少ない。
一定の規則があるとは言え、それは、プログラムが壊れないことを保証するものではない。
メモリアクセス順序の入れ替えによってプログラムの挙動が変わってしまうことはあり、それが不具合につながることもある。特にマルチスレッドプログラミングで問題が起きやすい。
順序の入れ替えによってプログラムの挙動が変わってしまうケース
順序の入れ替えが発生するかどうかで結果が変わるプログラムordering_unexpected.rsを用意した。
まずは全文を示す。
use std::hint::spin_loop; use std::sync::atomic::{compiler_fence, AtomicBool, AtomicUsize, Ordering}; use std::thread; const MAX_TRIALS: usize = 5_000_000; const STOP_SIGNAL: usize = usize::MAX; static FLAG_SET_BY_SUBJECT: AtomicBool = AtomicBool::new(false); static FLAG_SET_BY_OBSERVER: AtomicBool = AtomicBool::new(false); static FLAG_SEEN_BY_SUBJECT: AtomicBool = AtomicBool::new(false); static STARTED_TRIAL_NUMBER: AtomicUsize = AtomicUsize::new(0); static SUBJECT_FINISHED_TRIAL_NUMBER: AtomicUsize = AtomicUsize::new(0); fn run_subject() { for trial in 1..=MAX_TRIALS { loop { let started = STARTED_TRIAL_NUMBER.load(Ordering::SeqCst); if started == STOP_SIGNAL { return; } if started == trial { break; } spin_loop(); } FLAG_SET_BY_SUBJECT.store(true, Ordering::Relaxed); compiler_fence(Ordering::SeqCst); let observer_flag = FLAG_SET_BY_OBSERVER.load(Ordering::Relaxed); FLAG_SEEN_BY_SUBJECT.store(observer_flag, Ordering::Relaxed); SUBJECT_FINISHED_TRIAL_NUMBER.store(trial, Ordering::SeqCst); } } fn run_observer() { for trial in 1..=MAX_TRIALS { FLAG_SET_BY_SUBJECT.store(false, Ordering::Relaxed); FLAG_SET_BY_OBSERVER.store(false, Ordering::Relaxed); STARTED_TRIAL_NUMBER.store(trial, Ordering::SeqCst); FLAG_SET_BY_OBSERVER.store(true, Ordering::Relaxed); compiler_fence(Ordering::SeqCst); let subject_flag = FLAG_SET_BY_SUBJECT.load(Ordering::Relaxed); while SUBJECT_FINISHED_TRIAL_NUMBER.load(Ordering::SeqCst) != trial { spin_loop(); } let observer_flag_seen_by_subject = FLAG_SEEN_BY_SUBJECT.load(Ordering::Relaxed); if !subject_flag && !observer_flag_seen_by_subject { println!("memory access reordering observed; trial = {trial}"); STARTED_TRIAL_NUMBER.store(STOP_SIGNAL, Ordering::SeqCst); return; } } println!("no reordering observed in {MAX_TRIALS} trials"); } fn main() { let subject = thread::spawn(run_subject); let observer = thread::spawn(run_observer); subject.join().unwrap(); observer.join().unwrap(); }
全てを理解する必要はない。本記事の文脈における要点は以下。
- 2 つスレッドを作成し、それぞれ
run_subject()という関数とrun_observer()という関数を実行している - どちらの関数も 500 万回ループを回している
- ループの 1 周のことを、本記事では「試行」と呼ぶことにする
- 2 つのスレッドは、試行毎にタイミングを合わせて 2 つのフラグに対する読み書きを行っており、この操作に対して順序の入れ替えが行われているかを毎回チェックしている
- これについては後述する
- 順序の入れ替えを検知した場合、何回目の試行で検知したのかを標準出力した上でプログラムは終了する
- 一度も検知されなかったときのみ、 500 万回のループを完走できる
何をどのように検知しているのか
以下の操作によるメモリアクセスが、チェックの対象。
compiler_fence(Ordering::SeqCst);については後述するので、今は無視してよい。
// run_subject() FLAG_SET_BY_SUBJECT.store(true, Ordering::Relaxed); // FLAG_SET_BY_SUBJECT に true を書き込む compiler_fence(Ordering::SeqCst); let observer_flag = FLAG_SET_BY_OBSERVER.load(Ordering::Relaxed); // FLAG_SET_BY_OBSERVER の値を読み出す // run_observer() FLAG_SET_BY_OBSERVER.store(true, Ordering::Relaxed); // FLAG_SET_BY_OBSERVER に true を書き込む compiler_fence(Ordering::SeqCst); let subject_flag = FLAG_SET_BY_SUBJECT.load(Ordering::Relaxed); // FLAG_SET_BY_SUBJECT の値を読み出す
これらの処理を開始する時点で、どちらのフラグの値もfalseになっている。
なのでそれぞれ、自身のフラグの値をfalseからtrueに変えたあと、相手のフラグを読む、ということをしている。
そして、読み出した結果をチェックし、両方ともfalseだった場合、メモリアクセス順序の入れ替えが発生したと見做すようにしている。
なぜなら、順序入れ替えが発生しない限り、両方がfalseになることはないため。
順序入れ替えが発生しない場合、 4 つのメモリアクセスのうち最後に行われるのは必ずどちらかのload()（読み出し）になり、そのload()は必ずtrueを読み出す。
例えば、最後に行われるのがFLAG_SET_BY_SUBJECTに対するload()である場合、FLAG_SET_BY_SUBJECTへのtrueの書き込みは既に終わっているはずである。
このプログラムはあくまでも「メモリアクセス順序の入れ替えが発生していないと起こり得ない事象」を観測しているだけであり、その事象が起きなかったからと言ってメモリアクセス順序入れ替えが発生していないとは言えない。
しかし今回は入れ替えを全て検知したいわけではなく、入れ替えが実際に発生することを実証できればよいので、このプログラムで十分である。
コンパイラによる入れ替えが行われていないことを確認する
冒頭で触れたが、 CPU だけでなくコンパイラも、メモリアクセスの順序を入れ替えることがある。
今回検知したいのは CPU による入れ替えなので、コンパイラによる入れ替えは発生しないようにする必要がある。
そのために使うのがcompiler_fence()。この関数を書いた箇所を境界線とし、メモリアクセスが境界線を越える形で入れ替えられないようにする。
どのような形での入れ替えを禁止するのかを引数で指定するが、それについての解説は割愛する。
以下のコマンドを実行すると、ordering_unexpected.rsの内容に基づいてordering_unexpected.sというアセンブリが出力されるので、その内容を見てみる。
$ rustc -O --emit asm ordering_unexpected.rs
以下が、run_subject()側のメモリアクセスに相当する部分。
movbはstore()に、movzblはload()に相当するので、store()、コメント、load()という順番になっている。入れ替えは発生していない。
$ sed -n '1355,1358p' ordering_unexpected.s .LBB15_5: movb $1, _RNvCs6MavofoSZ4y_19ordering_unexpected19FLAG_SET_BY_SUBJECT.0(%rip) #MEMBARRIER movzbl _RNvCs6MavofoSZ4y_19ordering_unexpected20FLAG_SET_BY_OBSERVER.0(%rip), %edx
run_observer()側も同様。
$ sed -n '1389,1391p' ordering_unexpected.s movb $1, _RNvCs6MavofoSZ4y_19ordering_unexpected20FLAG_SET_BY_OBSERVER.0(%rip) #MEMBARRIER movzbl _RNvCs6MavofoSZ4y_19ordering_unexpected19FLAG_SET_BY_SUBJECT.0(%rip), %ecx
実行してみる
以下のコマンドでバイナリファイルを作成できるので、それを実行してみる。
$ rustc -O ordering_unexpected.rs
そうすると、 500 万回の試行を完走することはできず、途中でメモリアクセス順序の入れ替えを検知するはずである。
$ ./ordering_unexpected memory access reordering observed; trial = 5
上記の場合、5回目の試行で検知された。
つまりこのプログラムではメモリアクセス順序の入れ替えが発生し、それが実行結果に影響を与えるのである。
メモリオーダリング命令を使ってメモリアクセス順序入れ替えを防ぐ
メモリアクセスの順序関係を強制する命令である「メモリオーダリング命令」を使うことで、順序入れ替えを防ぐことができる。
先程見たcompiler_fence()はコンパイラによる入れ替えだけを禁止するものであり、メモリオーダリング命令は出力しない。compiler_fence()ではなくfence()を使うことで、コンパイラによる入れ替えを禁止するのに加えて、メモリオーダリング命令の出力も行われる。
先程のordering_unexpected.rsのcompiler_fenceをfenceにリプレイスしただけのordering_force.rsを用意したので、それを使って検証してみる。
use std::hint::spin_loop; -use std::sync::atomic::{compiler_fence, AtomicBool, AtomicUsize, Ordering}; +use std::sync::atomic::{fence, AtomicBool, AtomicUsize, Ordering}; use std::thread; const MAX_TRIALS: usize = 5_000_000; @@ -25,7 +25,7 @@ } FLAG_SET_BY_SUBJECT.store(true, Ordering::Relaxed); - compiler_fence(Ordering::SeqCst); + fence(Ordering::SeqCst); let observer_flag = FLAG_SET_BY_OBSERVER.load(Ordering::Relaxed); FLAG_SEEN_BY_SUBJECT.store(observer_flag, Ordering::Relaxed); @@ -40,7 +40,7 @@ STARTED_TRIAL_NUMBER.store(trial, Ordering::SeqCst); FLAG_SET_BY_OBSERVER.store(true, Ordering::Relaxed); - compiler_fence(Ordering::SeqCst); + fence(Ordering::SeqCst); let subject_flag = FLAG_SET_BY_SUBJECT.load(Ordering::Relaxed); while SUBJECT_FINISHED_TRIAL_NUMBER.load(Ordering::SeqCst) != trial {
先程と同様にアセンブリを出力し、その内容を見てみる。
$ sed -n '1355,1358p' ordering_force.s .LBB15_5: movb $1, _RNvCs7Q0h0GauMI1_14ordering_force19FLAG_SET_BY_SUBJECT.0(%rip) lock orl $0, -64(%rsp) movzbl _RNvCs7Q0h0GauMI1_14ordering_force20FLAG_SET_BY_OBSERVER.0(%rip), %edx
$ sed -n '1389,1391p' ordering_force.s movb $1, _RNvCs7Q0h0GauMI1_14ordering_force20FLAG_SET_BY_OBSERVER.0(%rip) lock orl $0, -64(%rsp) movzbl _RNvCs7Q0h0GauMI1_14ordering_force19FLAG_SET_BY_SUBJECT.0(%rip), %ecx
先程は#MEMBARRIERだった箇所がlock orl $0, -64(%rsp)に変わっている。
lock付き命令は、先行するメモリアクセスが全て完了してから実行される。そして、後続のメモリアクセスは、lock付き命令が完了するまで実行されない。
なぜそれによってメモリアクセス順序の入れ替えを防止できるのかを理解するためには、ordering_unexpected.rsで発生している事象を把握する必要がある。
順序が入れ替わってしまうのはあくまでもメモリアクセス、つまりメモリへの書き込みと読み出しであり、命令を開始する順序は入れ替わってはいないのである。つまり先にstore()を実行し、そのあとでload()を実行する。この順序は変わらない。しかし、store()によって行われるメモリ書き込みは、時間が掛かる。そのため CPU は、それを待たずにload()を実行して読み出しを行うのである。そのため、まず読み出しが行われてから書き込みが完了することになる。これが、ordering_unexpected.rsで起きていたことである。
既述の通りlock付き命令は先行するメモリアクセスの完了を待つので、store()とload()の間にlock付き命令を配置することで、メモリアクセスの順序が入れ替わってしまうことを防げるのである。なお、それはあくまでもこのケースでの話であり、別のケースにおいては他の命令によって順序入れ替えを防止することもある。
$ rustc -O ordering_force.rsでバイナリファイルを出力しそれを実行して、確認してみる。
$ ./ordering_force no reordering observed in 5000000 trials
500 万回試行しても順序入れ替えは検知されない。
メモリオーダリング命令を使うと処理が遅くなる
既に述べた通り、 CPU がメモリアクセスの順序を入れ替えるのは、高速化のためである。それはつまり、メモリオーダリング命令によって順序入れ替えを禁止すれば、その分だけ処理が遅くなる可能性があるということである。
そのことを実際に確かめるために用意したのが、以下の内容のfence_cost.rsというプログラム。
use std::hint::black_box; use std::sync::atomic::{compiler_fence, fence, AtomicBool, Ordering}; use std::time::Instant; const ITERATIONS: usize = 50_000_000; static FLAG_A: AtomicBool = AtomicBool::new(false); static FLAG_B: AtomicBool = AtomicBool::new(false); #[inline(never)] fn run(barrier: impl Fn()) -> usize { let a = black_box(&FLAG_A); let b = black_box(&FLAG_B); let mut seen = 0usize; for i in 0..ITERATIONS { a.store(i & 1 == 0, Ordering::Relaxed); barrier(); seen += b.load(Ordering::Relaxed) as usize; } seen } fn main() { let mode = std::env::args().nth(1).unwrap_or_default(); let start = Instant::now(); let seen = match mode.as_str() { "none" => run(|| {}), "compiler_fence" => run(|| compiler_fence(Ordering::SeqCst)), "fence" => run(|| fence(Ordering::SeqCst)), _ => { eprintln!("usage: fence_cost <none|compiler_fence|fence>"); std::process::exit(2); } }; let elapsed = start.elapsed(); let ns_per_iter = elapsed.as_nanos() as f64 / ITERATIONS as f64; black_box(seen); println!("{mode} {ns_per_iter:.3}"); }
このプログラムは、以下の処理を行うループを 5000 万回繰り返す。
- フラグ A に対する
store() barrier()- フラグ B に対する
load()
そしてループを抜けるまでに掛かった時間を 5000 万で割ることで、 1 回のループに掛かる平均時間を算出している。
barrier()の内容は、コマンドライン引数によって変わる。
none- 何もしない
compiler_fencecompiler_fence(Ordering::SeqCst)
fencefence(Ordering::SeqCst)
こうすることで、compiler_fence(Ordering::SeqCst)やfence(Ordering::SeqCst)によってパフォーマンスがどう変化するかを測定できる。処理内容の差分はそれだけなのだから、パフォーマンスに変化が生まれれば、それはcompiler_fence(Ordering::SeqCst)やfence(Ordering::SeqCst)に起因するものであると見做せる。
先程までと同じ方法でアセンブリを見てみたが、barrier()の部分は以下のように出力されていた。
none- 何も出力されない
compiler_fence#MEMBARRIERが出力される
fencelock orl $0, -64(%rsp)が出力される
それぞれ実行してみると、fenceだけが 10 倍以上遅いことがわかる。
$ ./fence_cost none none 0.399 $ ./fence_cost compiler_fence compiler_fence 0.415 $ ./fence_cost fence fence 4.884
それぞれ 100 回ずつ実行し最小値、最大値、平均値、中央値を出すシェルスクリプトを用意し計測してみたが、同様の結果になった。
#!/usr/bin/env bash set -euo pipefail cd "$(dirname "$0")" RUNS="${RUNS:-100}" BIN=./fence_cost MODES=(none compiler_fence fence) [[ -x "$BIN" ]] || { echo "not executable: $BIN" >&2; exit 1; } printf '%-16s %6s %10s %10s %10s %10s\n' mode runs 'min[ns]' 'max[ns]' 'avg[ns]' 'median[ns]' for mode in "${MODES[@]}"; do values=() for ((i = 1; i <= RUNS; i++)); do out="$("$BIN" "$mode")" values+=("${out##* }") done stats="$(printf '%s\n' "${values[@]}" | sort -g | awk ' { v[NR] = $1; sum += $1 } END { if (NR % 2 == 1) median = v[(NR + 1) / 2] else median = (v[NR / 2] + v[NR / 2 + 1]) / 2 printf "%.3f %.3f %.3f %.3f", v[1], v[NR], sum / NR, median }')" read -r min max avg median <<<"$stats" printf '%-16s %6d %10s %10s %10s %10s\n' "$mode" "$RUNS" "$min" "$max" "$avg" "$median" done
$ ./bench_fence_cost.sh mode runs min[ns] max[ns] avg[ns] median[ns] none 100 0.365 1.084 0.378 0.370 compiler_fence 100 0.362 0.394 0.371 0.370 fence 100 4.815 7.316 5.414 5.431 $ ./bench_fence_cost.sh mode runs min[ns] max[ns] avg[ns] median[ns] none 100 0.364 0.431 0.373 0.372 compiler_fence 100 0.364 1.099 0.392 0.370 fence 100 4.806 4.879 4.828 4.827 $ ./bench_fence_cost.sh mode runs min[ns] max[ns] avg[ns] median[ns] none 100 0.364 0.417 0.373 0.372 compiler_fence 100 0.365 0.385 0.371 0.370 fence 100 4.805 6.556 4.845 4.826
compiler_fenceはただコメントを出力するだけなので、noneとほぼ同じ結果になる。
fenceだけが 10 倍以上遅くなっている。つまり、lock付き命令はそれだけ速度を遅くするということになる。
もちろんこれは、あくまでもこのプログラム、この環境における結果である。compiler_fence(Ordering::SeqCst)やfence(Ordering::SeqCst)がどのような機械語に出力されるか自体が、状況によって異なる。
