07 | Cache与内存：程序放在哪儿？

程序代码优化 基于csapp做的整理 https://blog.csdn.net/u013570834/article/details/117635229?utm_source=app&app_version=4.9.2 1. gcc 编译器优化很蠢并不会猜测程序员编码的意图，只会做非常保守的优化 2.循环对于具有很好的时间局部性，所以我们尽量避免 goto 与非本地跳转 3. 数组在内存中行优先排列，所以数组的遍历方式对cache的命中率影响极大 4. 分支预测失败虽然会带来极大的惩罚，但这不是我们关注的重点，我们应该关注的如何能用条件传送的方式避免分支判断 5. 根据阿姆达尔定律，加速大的部分永远比加速小的要有效，所以我们可以根据对程序的分析来做具体的优化

如何写出让 CPU 跑得更快的代码？可以从以下几方面入手： 1、遵从80-20法则，程序80%的时间在运行20%或更少的代码，针对热代码进行优化，才容易产出效果； 2、遵从数据访问的局部性法则，按数据存放顺序访问内存效率远高于乱序访问内存效率，也就是尽量帮助CPU做好数据Cache的预测工作。同样根据Cache大小，做好数据结构的优化工作，进行数据压缩或数据填充，也是提升Cache效率的好方式； 3、遵从指令访问的局部性法则，减少跳转指令，同样是尽量帮助CPU做好数据Cache的预测工作；现代CPU都有一些预测功能【如分支预测】，利用好CPU的这些功能，也会提升Cache命中率； 4、避免计算线程在多个核心之间漂移，避免缓存重复加载，可以绑定核心【物理核即可，不用到逻辑核】，提高效率； 5、去除伪共享缓存：在多核环境下，减少多个核心对同一区域内存的读写并发操作，减少内存失效的情况的发生； ===开始跑题=== 6、合理提高进程优先级，减少进程间切换，可以变相提供Cache提速的效果 7、关闭Swap，可以变相提供内存提速、Cache提速的效果； 8、使用Intel自家的编译器，开启性能优化，很多时候可以提速运算效率； 9、使用C语言，而不是更高级的语言，很多时候可以提速运算效率； 10、直接使用昂贵的寄存器作为变量，可以变相提供加速效果；

我以前写过一篇关于缓存局部性原理的文章，有兴趣的同学可以看看： https://blog.csdn.net/zhanyd/article/details/102631248

在CSAPP第六章对存储器层次架构有详细的探讨，感兴趣的同学可以查阅一下，这里我简单总结一下当做思考题答案。 一个编写良好的计算机程序尝尝具有良好的局部性，这被称为局部性原理，对硬件和软件都有极大的影响。 局部性可分为两种，1.程序数据引用局部性;2.指令局部性。 CPU对数据和指令都存在高速缓存，当缓存中的数据大面积命中时，则该代码拥有良好的空间局部性;当缓存中的指令大面积命中时，也该代码拥有良好的时间局部性。 别忘了，CPU对于指令和数据的操作都需要花时间，那如果二者如果都大面积的缓存命中，可以减少非常多的内存访问操作，对于CPU来说，内存访问就是性能瓶颈所在。 因此编写高速缓存友好的代码是必要的，高手与小白往往只有一步之遥！ 基本方法大致如下: 1.让最常见的情况运行得快，核心函数中的核心部分，是影响性能的关键点，它们占据了程序的大部分运行时间，所以要把注意力放在它们身上。 2.尽量减少每个循环内部的缓存不命中数量，循环是缓存工作的重点，一个循环容易带来性能问题，而它恰好也容易被优化成空间、时间局部性良好的代码。 欢迎大家一起交流指正~

补充一下MESI协议，MESI分别代表了高速缓存行的四种状态： 最开始只有一个核读取了A数据，此时状态为E独占，数据是干净的， 后来另一个核又读取了A数据，此时状态为S共享，数据还是干净的， 接着其中一个核修改了数据A，此时会向其他核广播数据已被修改，让其他核的数据状态变为I失效，而本核的数据还没回写内存，状态则变为M已修改，等待后续刷新缓存后，数据变回E独占，其他核由于数据已失效，读数据A时需要重新从内存读到高速缓存，此时数据又共享了

恍然大悟，原来这就是要求我们写高复用性代码的原因，针对经常会用到的功能封装成通用函数或库，供整个程序调用，这些通用函数装载入cache后，因为其高复用性长久的存在于cache中，cpu自然就跑得更快。

1. 减少使用带有jmp指令的代码，提高指令cache的局部性（不过cpu貌似有分支预测器来优化jmp指令带来的性能损耗） 2. 对于需要连续访问的数据，可以将其放在一块以提高数据cache的局部性 3. 对于需要被多个CPU执行写操作的多个数据，可以根据cache line的大小对这些数据进行padding操作，来降低缓存一致性协议带来的读写内存频率

提高Cache的命中率可以从优化指令布局和优化数据布局两个方面开展。比如减少频繁的跳转，数据集中连续存放等。

回答一下思考题. 因为缓存行是固定的，32或64个字节，只能在写入内存的数据上尽量补齐，比如一个int 占4个字节(java),32位系统的对象头占8个字节，这样再多写5个int就对齐一个缓冲行了，jdk也提供了一个 annotation 即@Commented来解决，另外内存队列disruptor也用同样的方式优化了同样的问题，但是如此这数据，势必会造成资源浪费，如何权衡这2者还请老师分享一下经验

《深入理解计算机系统》 6.2 局部性 局部性分为：1. 时间局部性 2. 空间局部性 int sumvec(int v[N]) { int i, sum = 0; // sum在每次循环迭代中被引用一次，因此对于sum来说，有好的时间局部性；另一方面因为sum是标量，对于sum来说，没有空间局部性 for (i = 0; i < N; i++) { sum += v[i]; // 向量v的元素是被顺序读取的，因此对于变量v，函数有很好的空间局部性；但是时间局部性很差，因为每个向量元素只被访问一次 } return sum; } // 所以可以说：以被重复访问的次数衡量时间局部性，以访问是否有序、步长大小衡量空间局部性