2026-11-14
prefix_sums.rs
fn prefix_sums(mut v: [u32; 4]) -> [u32; 4] {
for d in [1, 2] {
for i in d..4 {
v[i] += v[i - d];
}
}
v
}
fn main() {
println!("{:?}", prefix_sums([1, 2, 3, 4]));
}
prefix_sums は、4つの値の先頭からの累積和を、SIMD のレジスタで行う手順をまねて求めるつもりの関数です。レジスタの値を d 個ずらしたものを元の値に足す操作を、d が1と2のときに1回ずつ行います。prefix_sums([1, 2, 3, 4]) は本来 [1, 3, 6, 10] を返すはずが、いまは [1, 3, 7, 13] を返します。
Answer
Wrong
for d in [1, 2] {
for i in d..4 {
v[i] += v[i - d];
}
}
SIMD の命令は、4本のレーンを同時に計算します。d 個ずらして足す1回の操作では、どのレーンも、操作の前の値を読んで足します。d が1の操作で各レーンは「自分と1つ前」の和になり、d が2の操作でそこに「2つ前と3つ前」の和が加わって、ちょうど先頭からの和になります。この手順が正しいのは、各操作の中ですべてのレーンが操作の前の値を読むときだけです。
内側の for は i を小さい順に回し、v[i] をその場で書き換えます。そのため v[i - d] は、同じ操作の中ですでに書き換えた値になることがあります。d が1の操作では、v[2] に足す v[1] がもう 1 + 2 になっていて、この1回で [1, 3, 6, 10] まで進んでしまいます。続く d が2の操作でさらに v[0] と v[1] が足され、[1, 3, 7, 13] になります。
Right
for d in [1, 2] {
let prev = v;
for i in d..4 {
v[i] += prev[i - d];
}
}
操作の前の値を prev に写しておき、足す側はいつも prev から読みます。[u32; 4] は Copy なので、let prev = v; で配列が丸ごと複製され、v を書き換えても prev は変わりません。これで1回の操作の中のどの足し算も、レジスタと同じく操作の前の値を使い、[1, 3, 6, 10] が返ります。i を大きい順に回しても、読む v[i - d] がまだ書き換えていない位置になるので、同じように直ります。