优化内存访问

优化内存访问

代码和数据缓存

高速缓存是计算机贮存的代理，代理更小，更接近CPU，访问速度快很多，可能有二级或者三级缓存

CPU的速度比RMA内存的速度增长要快，因此高效的缓存变得很重要

缓存结构

在程序中为了防止缓存竞争，了解缓存的组织结构将对于优化程序性能有很大作用

由于内存取数据到缓存的映射规则，当两个地址之间的间隔正好是关键步长的倍数（类似于同余）的情况下，会被取道相同的缓存组中，容易引起缓存竞争。关键步长等于缓存总大小除以每组缓存线的数量。

如果一个程序包含许多分散在内存中的变量和对象，那么就存在多个变量恰好被多个关键步长隔开，从而在数据缓存中引起竞争，同理分散的函数也是如此；

一起使用的函数应该被放在一起。

如果代码内存中使用的函数彼此接近，那么代码缓存的工作效率最高。函数通常按照他们在源代码中出现的顺序存储，因此，最好将代码中最关键的部分使用的函数集中在同一个源文件中，这些函数彼此相邻，并将经常使用的函数与很少使用的函数分开，减少数据缓存竞争，提高效率。

一起使用的变量应该被放在一起

缓存不命中的代价很大，从缓存中加载一个变量只需要几个时钟周期，而若变量不在缓存中，通常需要耗费超过100个时钟周期的时间来从RAM加载他。

如果一起使用的数据片段在内存中彼此靠近存储，则缓存的工作效率最高，变量好对象最好在使用他们的函数中声明，这些变量好对象将存储在栈中，而栈很有可能在一级缓存中。如果可能，尽量避免全局变量和静态变量，并避免内存分配（new 和 delete）。

面向对象编程是一种将数据存储到一起的有效方法。

如果代码中有大数据结构，那么存储数据变得很重要，例如如果1程序有两个数组a和b并且元素的访问顺序是a[0], b[0], a[1], b[1]如此交替访问，那么可以通过将数据组织为结构体数组来提高性能。

1
2
3
4
struct sab {
    int a, int b
};
sab ab[N];

数据对齐

如果将变量存储在可被变量大小整除的内存地址中，则访问变量的访问效率最高，例如double占用8字节的存储空间，因此，最好将其存储在可以被8整除的地址

结构体和类成员可能会造成缓存空间的浪费。

还可以选择按缓存线大小（通常是64字节）对齐大对象和数组，这样可以确保对象或数据或数组的开头地址与缓存线的开头地址一致部分编译器会自动对齐大的静态数组，但是也可以通过以下方式显式指定：

1
2
3
4
/*规定数据对齐的位置，而没有规定数据实际占用的内存长度*/
__declspec(align(64)) int BigArray[1024];
int BigArray[1024] __attribute__((align(64)));

动态内存分配

对象和数组可以通过new、delete或者malloc和free动态分配，在编译时期不知道所需的内存大小时很有用。
优点：

  • 某些情况下提供更清晰的程序结构
  • 不会分配超过所需的空间，与固定大小的数组变得很大时效率比较高
  • 当不能预测给出所需内存空间的合理上限时，比较有用。

缺点：

  • 动态分配和释放的过程需要更多时间，效率低下
  • 随机顺序分配和释放不同大小对象后，堆空间会变得碎片化，使得数据缓存效率低下，堆管理器的垃圾收集机制也可能会导致程序执行的延迟。
  • 程序员需要确保已分配的内容被释放，否则会内存泄露，也需要确保释放后的对象不能在被访问。
  • 分配的内存可能不是最佳对齐的
  • 编译器难以优化使用指针的代码，因为不能排除别名
  • 当数组长度在编译器未知时，矩阵或者多维数组的效率比较低。

当数组的大小或者对象的数量在编译时已知或者知道合理的上限的时候，没有理由使用动态内存分配。

当分配数量有限时，动态分配的成本可以忽略不计，大概一个程序有一个或者几个可变大小的数组时，动态分配有利。另外可以将数组设置的非常大（ACM常用操作），但若程序有几个大数组，且每个数组的大小都是关键步长，很有可能引起缓存竞争。

如果数组元素数量在程序执行期增长，最好是一开始就分配最终的数组大小，而不是一步一步的分配更多的空间。

为所有对象分配一个大内存块通常比为每个对象分配一个小内存块效率更高，例如链表的效率就不如线性数组，原因如下：

  • 每个对象都是单独分配的，分配、释放和垃圾收集耗时很久
  • 对象没有连续的储存在内存中，会降低数据缓存的效率
  • 额外的内存空间用于连接指针和堆管理器为每个分配的快存储的信息。
  • 遍历链表要比边遍历线性数组花费更多时间，在加载前一个元素指针之前，不能加载任何指针，形成了关键的依赖链，妨碍乱序执行

替代方法是用alloca分配来代替（int *a = (int *) alloca(4 * sizeof(int));），这是一个在栈上分配空间的函数（Linux默认栈空间 8MB，开int数组大概可以开到2e6很强）但编译器似乎对int a[n]这样的写法也是支持的，并且也是在栈上分配

容器类

最常用的容器集是标准模板库（STL），STL以通用性和灵活性为准则设计，执行速度、内存经济性、缓存效率和代码大小的优先级较低。

STL对内存分配存在不必要的浪费，例如list,set,map等，甚至可能分配比容器中对象更大的内存块。

对于vector这种，建议是调用reserve预先分配大小，而其他stl则没有预先分配内存的功能。

可以通过自定义内存池改善效率（PMR YYDS）也可以自己实现一些特化版本的容器库，提高效率

字符串

string类使用new 和 delet在每次创建或者修改字符串时分配一个新内存块，如果程序创建或修改了很多字符串，可能会非常低效。

大多数情况下，处理字符串最快的方法是用C风格的字符数组。

按顺序访问数据

当按顺序访问数据时，缓存的工作效率最高，当逆序访问数据是，工作效率略低，而当随机方式访问数据时，工作效率则显著降低，这适用于读取和写入数据。

多维数组应该在最内层循环中变化最后一个索引的方式访问，更好的利用缓存。

在大数据结构中的缓存竞争

有时候我们无法按顺序访问数据，若一个大矩阵中的行的距离恰好等于关键步长，这会导致严重的延迟，如果矩阵行的大小是2的高次幂，就会发生这样的情况。

比如我们不得不按列访问某矩阵，若其行数刚好为关键步长的倍数，那么我们的缓存利用率会显著降低。这种时候就可以考虑改变每行的数量，避免是关键步长的倍数。还可以采用叫做是square locking之类，将矩阵分为更小的正方形，一次处理一个正方形。比较复杂。

关键步长导致的竞争在二级缓存中更为明显，因为由于乱序执行机制，一级缓存可以预先加载数据，而二级缓存不行。

显示缓存控制

具有SSE和SSE2指令集的微处理器具有某些指令，允许我们操作数据缓存，这些指令可以从支持指令集函数（如Microsoft、intel和Gnu）的编译器访问，而其他编译器需要通过汇编代码来访问这些指令。（有点高端，而且理解不深的话可能没有编译器或CPU自己处理的来得好，暂时放弃）