可以看到，random_access 比 column_major 的效率还要低了 2 倍。原因是，在 cache 和 cpu 间还有 prefetcher

我们可以参考维基百科上的资料：

Cache prefetching can be accomplished either by hardware or by software.

• Hardware based prefetching
  is typically accomplished by having a dedicated hardware mechanism in
  the processor that watches the stream of instructions or data being
  requested by the executing program, recognizes the next few elements
  that the program might need based on this stream and prefetches into the
  processor's cache.
• Software based prefetching
  is typically accomplished by having the compiler analyze the code and
  insert additional "prefetch" instructions in the program during
  compilation itself.
  

而 random_access 会让 prefetching 的机制失效，使得运行效率进一步下降。

cache associativity

如果我们按照不同的步长迭代一个数组会怎么样呢？

pubfniter_with_step(arr: &mutVec<usize>, step: usize) {

let n = arr.len();

letmut i = 0;

for _ in0..1000000 {

unsafe { arr.get_unchecked_mut(i).add_assign(1); }

        i = (i + step) % n;

    }

}

steps 为：

let steps = [

1, 

2, 

4, 

7, 8, 9,

15, 16, 17,

31, 32, 33,

61, 64, 67,

125, 128, 131,

253, 256, 259, 

509, 512, 515, 

1019, 1024, 1031

];

我们进行测试：

可以看见当 step 为 2 的幂次时，都会有一个运行时间的突起，一个性能的毛刺。这是为什么呢？要回答这个问题，我们需要温习一些计组知识。

cache 的大小是要远小于主存的。这就意味着我们需要通过某种方式将主存的不同位置映射到缓存中。一般来说，共有 3 种不同的映射方式。

全相联映射

全相联映射允许主存中的行可以映射到缓存中的任意一行。这种映射方式灵活性很高，但会使得缓存的查找速度下降。

直接映射

直接映射则规定主存中的某一行只能映射到缓存中的特定行。这种映射方式查找速度高，但灵活性很低，会经常导致缓存冲突，从而导致频繁 cache miss 。

组相联映射

组相联映射则尝试吸收前两者的优点，将缓存中的缓存行分组，主存中某一行只能映射到特定的一组，在组内则采取全相联的映射方式。如果一组之内有 n 个缓存行，我们就称这种映射方式为 n 路组相联（n-way set associative）。

回到真实的 cpu 中，如：AMD Ryzen 7 4700u 。

我们可以看到，L1 cache 大小为 4 x 32 KB (128KB) ，采取 8 路组相联，缓存行大小为 64 bytes 。也就是说，该缓存共有 4x32x1024 byte/64 byte = 2048 行，共分为 2048/8 = 256 组。也就是说，当迭代数组的步长为 时，数据更可能会被分到同一个组内，导致 cache miss 更加频繁，从而导致效率下降。

（注：我的 cpu 是 intel i7-10750H ，算得的 L1 cache 的组数为 384 ，并不能很好地用理论解释。）

false share

我们再来观察一组 benchmark 。

use std::sync::atomic::{AtomicUsize, Ordering};

use std::thread;



fnincrease(v: &AtomicUsize) {

for _ in0..10000 {

        v.fetch_add(1, Ordering::Relaxed);

    }

}



pubfnshare() {

let v = AtomicUsize::new(0);

    thread::scope(|s| {

let ta = s.spawn(|| increase(&v));

let tb = s.spawn(|| increase(&v));

let tc = s.spawn(|| increase(&v));

let td = s.spawn(|| increase(&v));



        ta.join().unwrap();

        tb.join().unwrap();

        tc.join().unwrap();

        td.join().unwrap();

    });

}



pubfnfalse_share() {

let a = AtomicUsize::new(0);

let b = AtomicUsize::new(0);

let c = AtomicUsize::new(0);

let d = AtomicUsize::new(0);



    thread::scope(|s| {

let ta = s.spawn(|| increase(&a));

let tb = s.spawn(|| increase(&b));

let tc = s.spawn(|| increase(&c));

let td = s.spawn(|| increase(&d));



        ta.join().unwrap();

        tb.join().unwrap();

        tc.join().unwrap();

        td.join().unwrap();

    });

}

在 share 函数中，四个线程同时竞争原子变量 v 。而在 false_share 函数中，四个线程分别操作不同的原子变量，理论上线程之间不会产生数据竞争，所以 false_share 的执行效率应该比 share 要高。但 benchmark 的结果却出乎意料：

可以看到 false_share 比 share 的执行效率还要低。

在前文中提到，cpu 在读取数据时，是以一个 cache line 大小为单位将数据从主存中加载到 cache 中的。在前文中提到，笔者机器的 cache line 大小为：64 bytes 。而 false_share 函数中，四个原子变量在栈中的排布可能是：

a, b, c, d 四个原子变量在同一个 cache line 中，也就是说实际上四个线程实际上还是发生了竞争，产生了 false share 的现象。

那要如何解决这个问题呢？我们可以采用 #[repr(align(64))] （在不同的编程语言中又不同的写法），告知编译器将原子变量的内存地址以一个 cache line 大小对齐，从而避免四个原子变量位于同一个 cache line 中。

fnincrease_2(v: &AlignAtomicUsize) {

for _ in0..10000 {

        v.v.fetch_add(1, Ordering::Relaxed);

    }

}



#[repr(align(64))]

structAlignAtomicUsize {

    v: AtomicUsize,

}



impl AlignAtomicUsize {

pubfnnew(val: usize) -> Self {

Self { v: AtomicUsize::new(val) }

    }

}



pubfnnon_share() {

let a = AlignAtomicUsize::new(0);

let b = AlignAtomicUsize::new(0);

let c = AlignAtomicUsize::new(0);

let d = AlignAtomicUsize::new(0);



    thread::scope(|s| {

let ta = s.spawn(|| increase_2(&a));

let tb = s.spawn(|| increase_2(&b));

let tc = s.spawn(|| increase_2(&c));

let td = s.spawn(|| increase_2(&d));



        ta.join().unwrap();

        tb.join().unwrap();

        tc.join().unwrap();

        td.join().unwrap();

    });

}

我们再次进行 benchmark，这一次 benchmark 的结果就符合我们的预测了：

可以看见 non_share 相比前两者，提升了近乎两倍的效率。

pipeline

我们再看一个 benchmark：

pubtraitGet {

fnget(&self) -> i32;

}



structFoo { /* ... */ }

structBar { /* ... */ }



impl Get for Foo { /* ... */ }

impl Get for Bar { /* ... */ }



letmut arr: Vec<Box<dyn Get>> = vec![];

for _ in0..10000 {

    arr.push(Box::new(Foo::new()));

}

for _ in0..10000 {

    arr.push(Box::new(Bar::new()));

}



// 此时数组中元素的排列时有序的

arr.iter().filter(|v| v.get() > 0).count()



// 将数组打乱

arr.shuffle(&mut rand::thread_rng());



// 再次测试

arr.iter().filter(|v| v.get() > 0).count()

测试结果为：

可以看见，sorted 和 unsorted 之间效率差约 2.67 倍。这是因为频繁的分支预测失败导致的。

在CPU 中，每一条指令的执行都会分为多个步骤，而现代计算机架构中存在一个结构 pipeline 可以同时执行处于不同执行阶段的指令。

而 pipeline 要高效地工作，需要在执行指令 A 时就将接下来要执行的指令 B, C, D 等提前读入。在一般的代码中，pipeline 可以有效地工作，但遇到分支的时候，我们就遇到难题了：

如图，pipeline 应该读入 Code A 还是 Code B 呢？在执行分支语句前，谁也不知道，CPU 也是。如果我们还想要 pipeline 高效工作的话，我们就只剩下一条路：猜。只要猜得足够准，我们的效率就能够接近没有分支的情况。“猜”这一步也有一个专业名词——**流水线冒险**。而现代计算机在编译器配合以及一些算法的帮助下，某些分支（如下图所示）的预测成功率可以高达 99% 。

分支预测失败的代价是要付出代价的。首先，我们要清除 pipeline 中的指令，因为它们不是接下来要执行的指令。其次，我们要将接下来要执行的指令一一加载进 pipeline 。最后，指令经过多个步骤被执行。

在测试代码中，我们打乱数组后，就会导致分支预测频繁失败，最终导致了执行效率的下降。

数据依赖

我们再来看一段代码：

pubfndependent(a: &mutVec<i32>, b: &mutVec<i32>, c: &Vec<i32>) {

assert!(a.len() == 100000);

assert!(b.len() == 100000);

assert!(c.len() == 100000);



for i in0..=99998 {

        a += b;

        b[i + 1] += c;

    }

    a[9999] += b[9999];

}



pubfnindependent(a: &mutVec<i32>, b: &mutVec<i32>, c: &Vec<i32>) {

assert!(a.len() == 100000);

assert!(b.len() == 100000);

assert!(c.len() == 100000);



    a[0] += b[0];

for i in0..=99998 {

        b[i + 1] += c;

        a[i + 1] += b[i + 1];

    }

}

在这段代码中，我们通过两种不同的方式迭代数组，并最终达成一致的效果。我们画出，数据流图如下图：