热点资讯彩娱乐合作加盟飞机号@yy12395 摈斥低效代码, 每个圭表员都该了解的硬件学问
在追求高效代码的路上，咱们不可幸免地会遭受代码的性能瓶颈。为显著解、讲解一段代码为什么低效，并尝试改革低效的代码，咱们老是要了解硬件的使命旨趣。于是，咱们可能会尝试搜索关联某个架构的先容、一些优化指南或者阅读一些联想机科学的教科书（如：联想机构成旨趣）。但以上的内容可能都太过繁琐、细节太多彩娱乐合作加盟飞机号@yy12395，在阅读的进程中，咱们可能会迷失在纷纭的细节中，没法很好地将学问掌握到履行中。
本文旨在通过多个可启动的 benchmark 先容常见的优化细节以及与之关联的硬件学问，为读者开导一个简便、灵验的硬件心智模子。
Cache
领先要先容的等于缓存 cache 。咱们先来看一个引自 CSAPP 的经典例子：
pub fn row_major_traversal(arr: &mut Vec>) { let n = arr.len; for i in 0..n { assert!(arr[i].len == n); for j in 0..n { arr[i][j] += j; } }}pub fn column_major_traversal(arr: &mut Vec>) { let n = arr.len; for i in 0..n { assert!(arr[i].len == n); for j in 0..n { arr[j][i] += j; } }}
在上头两个例子中，分手按行、按列迭代一样大小的二维数组。
咱们对这两个函数进行 benchmark：
在上图中，纵轴是平均耗时，横轴是数组大小（如：2000.0 示意数组大小为：2000 x 2000）。咱们看到按行迭代数组比按列迭代的效力高约 10 倍。
在当代的存储架构中，cpu 和主存之间是 cache 。cpu 中的寄存器、高速缓存、内存三者的数据读写速率越来越慢。
而当 cpu 读取一个数据的时候，会先尝试从 cache 中读取。要是发生 cache miss 的时候，才会将数据从主存中加载到 cache 中再读取。而值得谨防的是，cpu 每一次的读取都是以 cache line 为单元的。也等于说，cpu 在读取一个数据的时候，也会将该数据相邻的、一个 cache line 内的数据也加载到 cache 中。而二维数组在内存中是按行排布的，换句话说，数组中相邻的两行是首尾相接陈列的。是以在读取 arr[i] 的时候，arr[i + 1] 、arr[i + 2] 等相邻的数组元素也会被加载到 cache 中，而当下一次迭代中，需要读取数组元素 arr[i + 1] 时，就能获胜从 cache 中取出，速率卓著快。而因为以列读取数组时，arr[i][j] 和 arr[i + 1][j] 在内存中的位置就不再是详细相接，而是相距一个数组行大小。这也导致了在读取 arr[i][j] 时，arr[i + 1][j] 并莫得被加载到 cache 中。不才一次迭代时就会发生 cache miss 也就导致读取速率大幅下落。
prefetcher
要是咱们不再是按某种规定，而是立时地遍历数组，适度又会如何呢？
pub fn row_major_traversal(arr: &mut Vec>) { let n = arr.len; for i in 0..n { assert!(arr[i].len == n); let ri: usize = rand::random; std::intrinsics::black_box(ri); for j in 0..n { arr[i][j] += j; } }}pub fn column_major_traversal(arr: &mut Vec>) { let n = arr.len; for i in 0..n { assert!(arr[i].len == n); let ri: usize = rand::random; std::intrinsics::black_box(ri); for j in 0..n { arr[j][i] += j; } }}pub fn random_access(arr: &mut Vec>) { let n = arr.len; for i in 0..n { assert!(arr[i].len == n); for j in 0..n { let ri: usize = rand::random; arr[j][ri % n] += j; } }}
表面上来说，立时遍历和按列遍历都会导致频繁地 cache miss ，是以两者的效力应该是周边的。接下来，咱们进行 benchmark：
不错看到，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
要是咱们按照不同的步长迭代一个数组会怎样样呢？
pub fn iter_with_step(arr: &mut Vec, step: usize) { let n = arr.len; let mut i = 0; for _ in 0..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 。
在 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 中。
咱们再次进行 benchmark，这一次 benchmark 的适度就得当咱们的权衡了：
不错看见 non_share 比拟前两者，擢升了近乎两倍的效力。
pipeline
咱们再看一个 benchmark：
pub trait Get { fn get(&self) -> i32;}struct Foo { /* ... */ }struct Bar { /* ... */ }impl Get for Foo { /* ... */ }impl Get for Bar { /* ... */ }let mut arr: Vec> = vec![];for _ in 0..10000 { arr.push(Box::new(Foo::new));}for _ in 0..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 。临了，提醒经过多个步调被实施。
在测试代码中，咱们打乱数组后，就会导致分支权衡频繁失败，最终导致了实施效力的下落。
数据依赖
咱们再来看一段代码：
pub fn dependent(a: &mut Vec, b: &mut Vec, c: &Vec) { assert!(a.len == 100000); assert!(b.len == 100000); assert!(c.len == 100000); for i in 0..=99998 { a[i] += b[i]; b[i + 1] += c[i]; } a[9999] += b[9999];}pub fn independent(a: &mut Vec, b: &mut Vec, c: &Vec) { assert!(a.len == 100000); assert!(b.len == 100000); assert!(c.len == 100000); a[0] += b[0]; for i in 0..=99998 { b[i + 1] += c[i]; a[i + 1] += b[i + 1]; }}
在这段代码中，咱们通过两种不同的形状迭代数组，并最终结束一致的后果。咱们画出，数据流图如下图：
在上图中，咱们用箭头示意依赖关系（a[0] -> b[0] 示意 a[0] 的适度依赖于 b[0] ），用玄色箭头示意在轮回外进行的操作，用不同的颜料，示意不同迭代中的操作。咱们不错看到，在 dependent 中，不同颜料的箭头会出当今解除个数据流中，如：（a[1]->b[1]->c[0] 中就出现了红色和蓝色箭头），这就意味着第 n + 1 次迭代会依赖于第 n 次迭代的适度，而 independent 中则莫得这种情况。
这会产生什么影响呢？咱们来进行测试：
本次大会以“科技赋能 育见未来”为主题，邀请教育部原副部长张天保，上海财经大学商学院党委书记魏航，全国政协委员、中国教育国际交流协会副会长、原秘书长王永利，北京金融科技学院副校长蒲嘉陵等多位重磅嘉宾，围绕“教育创新”“教育改革”以及“科技赋能教育”等热点议题，共同探索构建面向未来的全新教育生态与发展路径，为教育发展注入新的活力。
不错看到，出现了近 3 倍的效力差距。这有两方面原因。
一是数据依赖会导致 pipeline 效力以及 cpu 提醒级并行的效力变低。
二是这种迭代之间的依赖会装扮编译器的向量化优化。咱们不雅察等价的 cpp 代码（rust 1.71 的优化身手并不及以将 independet 向量化，我略感追悼）。
#include using i32 = int;templateusing Vec = std::vector;void dependent(Vec &a, Vec &b, Vec &c) { for (int i = 0; i &a, Vec &b, Vec &c) { a[0] += b[0]; for (int i = 0; i
张望汇编：
dependent(...): mov rax, rdx mov rdx, QWORD PTR [rsi] mov rcx, QWORD PTR [rdi] mov rdi, QWORD PTR [rax] xor eax, eax.L2: mov esi, DWORD PTR [rdx+rax] add DWORD PTR [rcx+rax], esi mov esi, DWORD PTR [rdi+rax] add DWORD PTR [rdx+4+rax], esi add rax, 4 cmp rax, 39996 jne .L2 mov eax, DWORD PTR [rdx+39996] add DWORD PTR [rcx+39996], eax retindependent(...): mov rax, QWORD PTR [rdi] mov rcx, rdx mov rdx, QWORD PTR [rsi] lea rdi, [rax+4] mov esi, DWORD PTR [rdx] add DWORD PTR [rax], esi lea r8, [rdx+4] mov rsi, QWORD PTR [rcx] lea rcx, [rdx+20] cmp rdi, rcx lea rdi, [rax+20] setnb cl cmp r8, rdi setnb dil or ecx, edi mov rdi, rdx sub rdi, rsi cmp rdi, 8 seta dil test cl, dil je .L9 mov rcx, rax sub rcx, rsi cmp rcx, 8 jbe .L9 mov ecx, 4.L7: movdqu xmm0, XMMWORD PTR [rsi-4+rcx] movdqu xmm2, XMMWORD PTR [rdx+rcx] paddd xmm0, xmm2 movups XMMWORD PTR [rdx+rcx], xmm0 movdqu xmm3, XMMWORD PTR [rax+rcx] paddd xmm0, xmm3 movups XMMWORD PTR [rax+rcx], xmm0 add rcx, 16 cmp rcx, 39988 jne .L7 movq xmm0, QWORD PTR [rsi+39984] movq xmm1, QWORD PTR [rdx+39988] paddd xmm0, xmm1 movq QWORD PTR [rdx+39988], xmm0 movq xmm1, QWORD PTR [rax+39988] paddd xmm1, xmm0 movq QWORD PTR [rax+39988], xmm1 mov ecx, DWORD PTR [rdx+39996] add ecx, DWORD PTR [rsi+39992] mov DWORD PTR [rdx+39996], ecx add DWORD PTR [rax+39996], ecx ret.L9: mov ecx, 4.L6: mov edi, DWORD PTR [rdx+rcx] add edi, DWORD PTR [rsi-4+rcx] mov DWORD PTR [rdx+rcx], edi add DWORD PTR [rax+rcx], edi add rcx, 4 cmp rcx, 40000 jne .L6 retAI助手
不错看到，independent 函数被告捷向量化。
作家丨shizhaoyang彩娱乐合作加盟飞机号@yy12395