循环内索引优化：预取后性能未达预期的问题排查

问题背景 #

我正在优化一段对超长数组进行索引计数的代码，原始代码如下：

for i in 0..len {
    slots[values[i].slot].count += 1;
}

注：两个列表长度相同且都极长

已做的优化及效果 #

我通过缓存预取优化将代码提速了2.5倍，优化后的代码：

const PREFETCH_DISTANCE: usize = 32;
for i in (0..len).rev() {
    if i >= PREFETCH_DISTANCE {
        let pfs = values[i - PREFETCH_DISTANCE].slot;
        let fetch = &slots[pfs] as *const Slot as *const i8;
        unsafe { _mm_prefetch(fetch, _MM_HINT_T0) }
    }
    slots[values[i].slot].count += 1;
}

性能对比与疑问 #

但优化后的性能仍未达预期，相同数据量下，一段无随机索引操作的代码速度比它快两倍以上：

for val in &*arr {
    let ptr = val as *const T;
    let val = unsafe { ptr.read() };
    let dif = integrated_expected_distribution(&val) - start_val;
    debug_assert!(dif >= 0.);
    let slot = (dif * end_mult) as usize;
    debug_assert!(slot < len);
    values.push(Slottable { value: val, slot });
}

我想知道是否遗漏了其他预加载的内容，或是存在其他未发现的性能瓶颈？

可复现示例 #

let amount = 100_000_000;
let highest_possible_num = 1_000_000_000;
let seed = 44;

let mut rng = rand::rngs::StdRng::seed_from_u64(seed);

let mut vec2: Vec<usize> = (0..amount)
    .map(|_| rng.gen_range(0..=highest_possible_num))
    .collect();
let vec1: Vec<usize> = (0..amount).map(|_| rng.gen_range(0..amount)).collect();
let len = amount;
const PREFETCH_DISTANCE: usize = 32;
let loop_ = Instant::now();
for i in (0..len).rev() {
    if i >= PREFETCH_DISTANCE {
        let pfs = vec1[i - PREFETCH_DISTANCE];
        let fetch = &vec2[pfs] as *const usize as *const i8;
        unsafe { _mm_prefetch(fetch, _MM_HINT_T0) }
    }
    vec2[vec1[i]] += 1;
}
let loop_duration = loop_.elapsed();
println!("Loop time: {:?}", loop_duration);

注：原始代码中的count和slot都是8字节数据结构的成员，对示例逻辑无影响

补充编辑 #

1. 我曾猜测循环无法进行指令级并行导致变慢，但后续测试推翻了这个结论。
2. 以下仅做简单累加的代码，速度比我做了预取的计数代码快得多：

let mut test = 0;
for i in (0..len).rev() {
    test += values[i].slot;
}
println!("test: {}", test);

分析与优化建议 #

核心瓶颈：随机内存访问的缓存命中率 #

你的计数循环本质是随机写入操作：vec2[vec1[i]] += 1中，vec1[i]是随机生成的索引，意味着每次写入的内存地址几乎无规律，会频繁触发缓存失效（缓存未命中）。预取策略只对可预测的内存访问模式有效，随机访问场景下预取的命中率极低，很难覆盖所有零散的访问地址。

对比之下，你提到的“无索引操作”代码是顺序写入（values.push），补充测试的累加代码是顺序读取，这两种场景的缓存命中率接近100%，自然速度远快于随机写入的计数循环。

具体优化方向 #

1. 分桶局部累加 + 全局合并
   先对vec1中的索引做分组，用多个局部计数器数组做累加，最后合并到全局数组，利用缓存局部性减少冲突：

   // 根据CPU核心数设置分桶数量，比如16
   let bucket_count = 16;
   let mut local_counts = vec![vec![0usize; amount]; bucket_count];
   
   // 局部累加，每个桶的访问缓存命中率更高
   for (idx, &slot) in vec1.iter().enumerate() {
       let bucket = idx % bucket_count;
       local_counts[bucket][slot] += 1;
   }
   
   // 合并局部计数到全局vec2
   for local in local_counts {
       for (i, cnt) in local.into_iter().enumerate() {
           vec2[i] += cnt;
       }
   }
   

2. 调整内存布局
   如果原始的Slot结构体包含其他字段，建议将count单独抽成一个独立的数组（拆分结构体数组），减少每次访问的缓存行占用，提升缓存利用率。

3. 优化预取策略（效果有限）
   若坚持使用预取，可尝试增大预取距离（比如64或128），或者使用_MM_HINT_T1/_MM_HINT_T2这类针对不同缓存层级的预取提示，但随机访问场景下提升空间不大。

4. 工具验证
   使用perf工具直接分析缓存命中情况，确认瓶颈来源：

   perf stat -e cache-misses,cache-references ./your_binary
   

   通过对比不同版本代码的缓存未命中次数，能直观验证优化效果。

内容的提问来源于stack exchange，提问作者Per