@information 姓名：李靖，学号：22011211070，智慧宇宙投稿
转载自知乎
作者：pcdack
链接：https://www.zhihu.com/question/37692782/answer/2402677930
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
可以试试缓存优化
缓存友好程序设计指南
译者注：本文原始链接为<Make your programs run faster by better using the data cache>，翻译获得作者同意。本文中的一些策略只对大量数据处理有优化的可能，小量数据很可能带来性能下降。
性能优化相关的文章
vec.emplace_back(x)和vec[x]相比那个更快？
通过使用数据缓存加速程序
开发者时刻面临着如何加速程序，其中最明显的是通过花哨的算法来降低复杂度。比如说将O(n2)O(n^2)O(n^2)复杂度的算法，使用O(nlogn)O(nlogn)O(nlogn)替换等等。这是很好的方法，但是并不是所有的程序都有更好的算法来优化。那么应该怎么办？是否存在一种方法来优化我们已存在的算法。事实上是存在的，它叫：底层优化(low-level optimizations)。
首先，先来了解一下底层优化的情况。底层优化关注于如何最好地利用底层架构的特殊性来获得更好的性能。这是这个系列的第一篇，将会涉及到底层优化。我们将在如何更好地利用内存缓存子系统上探索一系列的方法。对于熟悉现代多进程系统内存缓存原理的读者，可以跳过数据缓存章节。
数据缓存
计算机系统通常包含处理器和内存。在现代计算机系中内存是比处理器慢百倍的，因此处理器通常都要等待内存传输数据。聪明的硬件工程师想出了一个解决方案来抵消速度上差异：他们添加了一个很小的快速内存——缓存，用以弥补不同的速度。当程序需要访问主存中的数据，它首先会检查数据是否已经在缓存中，如果在，它可以很快的获取数据。否则，计算机会牺牲一些处理器周期，等待主内存提供数据。
通常情况下，缓存存储器分为指令缓存存储器和数据缓存存储器。指令缓存器的目的是加速对指令的访问，数据缓冲器的目的是加快对指令所使用的数据的访问。这篇文章主要关注如何使用数据缓存器来加速程序。
为什么内存缓存可以使程序运行的更快?
那么，为什么增加缓存内存能起作用呢？ 毕竟，程序可以在任何时候都可以访问任何内存位置，因此，这些数据不应该在缓存中。理论上是这样的，但在实践中，真正的程序几乎不会以随机方式访问内存。
有两个原则制约着现实世界的程序行为。第一条被称为时间局部性，即如果处理器目前正在访问某个内存地址，就很有可能在不久的将来再次访问这个内存地址(例如：循环中的计数器)。第二种被称为空间局部性，其含义是如果处理器目前正在访问某个内存地址，那么它很有可能会在不久的将来访问邻近的内存地址（例如：处理数组中的数据）。
数据缓存内部组织形式
现在让我们来看看缓存的内部情况。在现代计算机处理器中缓存被分解为 Cache line，每个 Cache line 通常情况下是 64bytes 的大小。一个 Cache line 对应主存中 64bytes 的内存块。获取 64byte 中的任意 1byte 数据，意味着需要加载整个 64byte 内存块到缓存中来。当 cache line 长时间没有使用或需要使用新的数据去替换时，缓存将返回修改后的块到主存中去。这整个过程程序并不知道。
让程序运行更快的一些技巧
对数据缓存有了一定的了解后，让我们来看看如何将数据缓存相关的原理应用到你的程序中，从而使你的程序拥有更好的性能。
注意：下面每小节，我使用 C 写法的数组和 C++ 写法的数组(vector、array),以及 C 写法(struct)和 C++ 写法(class)的类。
当获取线性数据时，尽量使用vector和array
链表，hash maps,字典等，都是十分有用的数据结构，但是，它们都不是缓存友好的。在这些数据结构中遍历，将会带来很大的缓存丢失。如果，当前程序性能是最重要的因素，那么可以将这些数据结构转为数组。 如果这是不可能的，尝试将数组的缓存效率和其他数据的灵活性结合起来。Gap_buffer是这种结合的很好例子。它将链表结构和数组结构结合，这使得其具有卓越的缓存效率和较低代价的元素添加和删除。另一个例子是Judy_array，稀疏数组的树形实现，同样的拥有很低代价的元素插入和删除，并且缓存友好。
经常访问的数据，在内存中应当是相邻的
如果有几个变量被一起访问，它们应该被逐一声明。这就增加了另一个变量在处理器访问后已经在缓存中的可能性。因为在处理器访问了第一个变量之后，另一个变量已经在缓存中了。从而避免了缓存的缺失。
考虑下面的类：
这个类实现了一个链接指针列表。如果我们的程序以这样的方式使用该类，即把变量 head 和 count 作为一个包来访问，那么它们应该一个接一个地放在类定义中。在这种情况下我们增加了它们实际在同一缓存行中的概率。
使用数据数组替换指针数组
当谈到类或结构的数组时，人们想到的第一个想法是使用指针而不是值。这种解决方案与数组相比有很多优点:包括运行时的多态性和在数组中未分配元素的情况下，对内存的使用更少。但会有一个性能缺陷，即使用指针访问该变量时，必然会涉及到高速缓存的缺失。 因此，为了快速访问数组，可以不使用指针而使用值。
因此，现在当把类的数组用值填充时，我们将获得一些好处。每当我们访问数组中的一个元素时，缓存预取器就会获取更多与我们当前访问的元素接近的元素。 如果我们访问的是数组中彼此相邻的元素，那么数据缓存就被最大限度地利用了。
优化对类或结构数组的访问
如果我们以随机的方式访问数组中的元素，就会出现一些缓存丢失的情况。但是缓存丢失的多少取决于我们在类中如何组织数据。例如：
假设我们有一个类my_class并且该类的大小为 48btyes。数组的第一个元素从偏移量0 开始，第二个元素从偏移量 48 开始，第三个元素从偏移量 96 开始，第四个元素从偏移量 96 开始。如果我们的cache line是64bytes，那么意味着第一个类元素在第一个 cache line 中，第二个元素将被分别存在第一个和第二个 cache line 中，第三个元素也将被分别存在两个 cache line 中...
在对类的元素进行随机访问时，将一个元素分割在两个高速缓存线之间，从数据缓存利用率的角度来说是不好的。缓存存储器需要两次访问主存储器才能读取一个元素。那么如何避免呢？如何使每个元素适合最小数量的cache line？下面是一些规则：
类的大小需要是cache line大小的倍数。
数组的起始地址需要是cache line大小的倍数。
要使类的大小是缓存行大小的倍数，我们可以手动的填充使其满足cache line 或者告诉编译器自动帮我们填充，在C++11中允许使用alignas(64)来指定。当然 GCC/CLANG 编译器提供了__attribute__((aligned (64)))实现相同功能。更好的解决方案是让编译器和库来帮助我们；我们可以用posix_memalign去分配对齐的内存在堆中，或者使用alignas(64)和__attribute__((aligned (64)))在栈或者全局内存中分配内存。下面是一个使用posix_memalign分配类数组的例子:
语法看起来非常的复杂，其实很简单。我们声明了my_class类型的指针，该指针用来保存类数组。接下来我们使用posix_memalign去为数组分配内存。同时指定了对齐参数为 64。最后，在循环中，我们为数组中的每个元素调用构造函数。注意，我们使用的是::new操作符，这个操作符不做内存分配，而是它在作为参数提供的内存上执行构造函数（简单的说，就是执行 array_of_my_class[i] 构造函数，而不进行内存分配）。
有效地访问你的矩阵中的数据
如果你的程序需要处理矩阵，你需要了解矩阵是如何存储在内存中的。矩阵被定义为二维的，但是内存是一维的。C 和 C++ 编译器将矩阵逐行排列。这就意味着我们获取矩阵中的某个元素时，和这个元素在相同行的一些元素也已经被加载到数据缓存中。
这看起来微不足道，但它会对性能产生深远的影响。考虑一下简单的矩阵乘法算法：
矩阵相乘就是对in_matrix1的行，和对in_matrix2的列做运算，按照这个计算规律结合上文的内容，我们可知in_matrix1是符合缓存规律的，但是，in_matrix2将会是缓存不友好的。在in_matrix2中每访问下一个元素都会导致 cache 丢失，因此上面的代码具有很大的性能缺陷。
那么如何解决上述问题？其实很简单。进行一种叫做循环互换的转换， 将 j 上的循环移到最里面的位置。这个解决方案的具体实现如下：
通过这种转换，逐行运行in_matrix和result。这对性能有很大的影响。
