程序性能优化——六、访存时的优化（上）

我们都知道，现代计算机都是基于冯诺依曼体系构建的，程序指令和数据都是存储在存储器中，随着程序的执行不断被调用------存储器的读取速度对程序的速度有着较大影响，所以，本篇文章介绍的就是如何对访存进行优化。

目录

1寄存器优化

寄存器是速度最接近处理器的存储器，但是受限于成本、设计等因素，容量较小。以下介绍针对寄存器的诸多优化方法。

寄存器分配

1.减少全局变量

全局变量会占用寄存器，所以尽量不要使用全局变量，或改为局部变量使用。

2.直接读寄存器

在多次使用数组时，应将数组转为标量（只含有一个值的变量）使用，这样可以直接读取寄存器的数据，而不是从缓存中调用数组浪费时间。

优化前

for(int i=0; i<N; i++){
  c[i]= a[i]+ b[i];
  d[i]= a[i]- b[i];}

优化后

for(int i=0; i<N; i++){int x = a[i];int y = b[i];
  c[i]= x + y;
  d[i]= x - y;}

3.直接写寄存器

同样，在对数组进行写入的时候也可以使用临时变量保存中间结果，最后再赋值给数组。

优化前

for(int i=0; i<N; i++){
  a[0]+= b[i];}

优化后

int temp_sum =0;for(int i=0; i<N; i++){
  temp_sum += b[i];}
a[0]= temp_sum;

寄存器重用

在五、程序编写时的优化（下）的5语句优化中我们提到了依赖关系会破坏程序的并行性，但是依赖性也有它的好处，就是寄存器不用重新被赋值，可以继续重用从而加快速度。

优化前

int temp_sum =0;for(int i=0; i<4*N; i++){
  temp_sum += b[i];}
a[0]= temp_sum;

优化后

int temp_sum =0;for(int i=0; i<4*N; i+=4){
  temp_sum += b[i];
  temp_sum += b[i+1];
  temp_sum += b[i+2];
  temp_sum += b[i+3];}
a[0]= temp_sum;

可以看到，上述代码在五、程序编写时的优化（下）的4循环优化中由于依赖性是不能起到并行的作用的，但是由于寄存器的重用效果，它也能起到优化的效果。

同样，考虑寄存器的因素也能够解释为什么我们将循环展开后性能有可能上升有可能下降，因为当展开的数量过多出现了寄存器溢出（需要的寄存器个数大于实际的寄存器个数）时，就需要调用缓存，反而降低了性能。

2缓存优化

高速缓存是计算机系统中用于临时存储数据的一种特殊存储器。它位于主存和CPU之间，用于存储最常用的数据和指令，以提高数据访问速度。高速缓存通常分为多级，根据其距离CPU的远近和容量大小进行层级划分，常见的有L1、L2和L3缓存。

缓存利用局部性原理来优化性能是一种基于观察到的数据访问模式的优化策略。局部性原理包括两种类型：时间局部性和空间局部性。

1. 时间局部性：时间局部性指的是程序在一段时间内对同一数据的反复访问。缓存利用时间局部性通过将最近使用的数据缓存在高速缓存中，以便程序下次访问同一数据时能够更快地获取到。这种机制有效地减少了CPU等待数据的时间，提高了程序的执行效率。
2. 空间局部性：空间局部性指的是程序在一段时间内对相邻内存位置的访问。缓存利用空间局部性通过将一段连续的内存数据缓存在高速缓存中，以便程序在访问某个内存位置时能够一次性获取到附近的一组数据。这种机制有效地减少了对主存的访问次数，降低了内存访问的延迟。

缓存利用局部性原理优化性能的关键在于根据程序的数据访问模式，预测并缓存可能被频繁访问的数据，以提高数据的访问速度和系统的整体性能。

以下是三类针对缓存的优化方法：

缓存分块

我们知道缓存是利用指令和代码的局部性以起到加速的效果的，所以也要尽可能地提升程序的局部性来最大化缓存的命中次数。

这一步有点类似于循环分段和循环交换。

优化前

for(int i=0; i<N; i++){//矩阵乘法算法for(int j=0; j<N; j++){int r=0;for(int k=0; k<N; k++){
      r+=y[i][k]*z[k][j];}
    x[i][j]= r;}}

优化后（将大矩阵分割为小矩阵参与运算，保证每个小矩阵都能存储于缓存中，增加了程序的局部性）

for(int jj=0; jj<N; jj+=S){//矩阵乘法算法,S为分块大小for(kk=0; kk<N; kk+=S){for(int i=0; i<N; i++){for(int j=jj; j<min(jj+S,N); j++){int r=0;for(int k=0; k<min(kk+S,N); k++){
          r+=y[i][k]*z[k][j];}
        x[i][j]+= r;}}}}

减少伪共享

什么是缓存一致性？

在多核多线程程序中，每个核心都有自己的缓存用于存储最常用的数据，以提高访问速度。缓存一致性是指确保在多个核心之间对共享数据的访问是一致的。当一个核心修改了某个共享数据的副本时，其他核心的缓存中的该数据副本也需要被更新，以确保所有核心看到的数据都是最新的。否则，如果不同核心之间的缓存不一致，就可能导致程序出现错误或不确定的行为。

为了保证缓存一致性，现代处理器使用了一些技术，如缓存一致性协议（如MESI协议）和总线事务（如读取-修改-写入操作）等，以确保共享数据的一致性。

什么是伪共享？

伪共享问题是指由于多个线程在不同的核心上同时访问同一块内存区域的不同部分而导致的性能问题。虽然这些线程可能在访问不同的数据，但它们所访问的数据可能被存储在同一缓存行（Cache Line）中。由于缓存行是缓存管理的最小单位，因此当一个线程修改了缓存行中的数据时，该缓存行的副本会被标记为"被修改"并在需要时写回主内存。这就导致其他线程访问同一缓存行中的数据时可能因为缓存一致性协议的影响而产生额外的缓存通信开销，从而降低程序的性能。

伪共享问题的出现主要是由于现代处理器中缓存的一致性和管理策略。当多个线程并发地修改同一缓存行中的不同数据时，即使它们修改的是不同的数据，由于缓存一致性协议的作用，所有的修改都会被标记为"被修改"，从而触发缓存行的写回操作，而这些写回操作可能会导致其他线程需要重新加载该缓存行，造成额外的开销。

简而言之，就是在多线程程序中，不同核心使用的某个数据不需要更新却被更新了，造成了额外开销。

可以使用以下原则来避免该问题：

1. 将不同的数据分别存储在不同的缓存行中
2. 填充无关的数据以确保不同数据不会存储在同一缓存行
3. 尽量少使用共享数据
4. 尽量少修改数据
5. 避免多个线程频繁访问同一缓存行（比如使用临时变量存储中间结果，很熟悉吧，很多方法都是相似的）

工具

Linux系统中可以使用perf工具对伪共享问题进行分析

Windows系统中可以使用PerfView工具对伪共享问题进行分析

数据预取

简而言之就是访存与计算的过程重叠，让处理器在计算的同时，总线从缓存中抽取数据，减少了下一次抽取的等待时间。

硬件预取于软件预取

硬件预取的预测正确性很不一定，而且假设程序本身的局部性不好，还可能出现反向优化的效果。

以下举一个例子介绍软件预取的方法，使用的是SSE指令集中的void __bulitin_prefetch(const void*addr,rw,locality)指令，其中第一个参数是目标地址，第二个参数表示读(0)或写(1)，第三个参数表示时间局部性的大小(1-3)。

优化前

#include<stdio.h>#defineARRAY_SIZE6400intmain(){int array[ARRAY_SIZE];int sum =0;// 初始化数组for(int i =0; i < ARRAY_SIZE;++i){
        array[i]= i;}// 计算平方和for(int i =0; i < ARRAY_SIZE;++i){
        sum += array[i]* array[i];}printf("Sum of squares: %d\n", sum);return0;}

优化后

#include<stdio.h>#defineARRAY_SIZE6400#definePREFETCH_DISTANCE64// 预取距离intmain(){int array[ARRAY_SIZE];int sum =0;// 初始化数组for(int i =0; i < ARRAY_SIZE;++i){
        array[i]= i;}// 计算平方和，并添加预取for(int i =0; i < ARRAY_SIZE; i+=PREFETCH_DISTANCE){// 预取下一个缓存行__builtin_prefetch(&array[i + PREFETCH_DISTANCE],0,3);for(int j=i; j<i+PREFETCH_DISTANCE; j++)
          sum += array[j]* array[j];}printf("Sum of squares: %d\n", sum);return0;}

3内存优化（日更好累，前面的区域以后再来探索吧）

4磁盘优化（日更好累，前面的区域以后再来探索吧）

5数据布局（日更好累，前面的区域以后再来探索吧）

专栏安排（已有，或将有）

一、程序性能优化的意义

二、程序性能的度量指标

三、程序性能优化流程

四、程序性能的测量和分析

五、程序编写时的优化（上）：算法优化、数据结构优化、函数优化

五、程序编写时的优化（下）：循环优化、语句优化

六、访存时的优化（上）：寄存器优化、缓存优化、内存优化

六、访存时的优化（下）：磁盘优化、数据分布

七、编译与运行时的优化（上）：编译器结构、编译选项、编译优化

七、编译与运行时的优化（下）：数学库优化、运行时的优化

八、系统配置的优化

九、单核优化

十、OpenMP程序优化

十一、MPI程序优化

十二、…

如有不足之处，敬请批评指正

更欢迎在评论区留下你的见解，你的方法，如果有效我会增加在文章中，并@你。