通过使用数据缓存加速程序
通过使用数据缓存加速程序
开发者时刻面临着如何加速程序，其中最明显的是通过花哨的算法来降低复杂度。比如说将 O ( n 2 ) O(n^2) O(n2) 复杂度的算法，使用 O ( n l o g n ) O(nlogn) O(nlogn) 替换等等。这是很好的方法，但是并不是所有的程序都有更好的算法来优化。那么应该怎么办否存在一种方法来优化我们已存在的算法。事实上是存在的，它叫：底层优化(low-level optimizations)。
首先，先来了解一下底层优化的情况。底层优化关注于如何最好地利用底层架构的特殊性来获得更好的性能。这是这个系列的第一篇，将会涉及到底层优化。我们将在如何更好地利用内存缓存子系统上探索一系列的方法。对于熟悉现代多进程系统内存缓存原理的读者，可以调过 数据缓存 章节。
数据缓存
计算机系统通常包含处理器和内存。在现代计算机系是中内存是比处理器慢百倍的，因此处理器通常都要等待内存传输数据。聪明的硬件工程师想出了一个解决方案来抵消速度上差异：他们添加了一个很小的快速内存被称为缓存的东西，用以弥补不同的速度。当程序需要访问主存中的数据，它首先会检查数据是否已经在缓存中，如果在，它可以很快的获取数据。否则，计算机会牺牲一些处理器周期，等待主内存提供数据。
通常情况下，缓存存储器分为指令缓存存储器和数据缓存存储器。指令缓存器的目的是加速对指令的访问，数据缓冲器的目的是加快对指令所使用的数据的访问。这篇文章主要关注如何使用数据缓存器来加速程序。
为什么内存缓存可以使程序运行的更快/h2>
那么，为什么增加缓存内存能起作用呢毕竟，程序可以在任何时候都可以访问任何内存位置，因此，这些数据不应该在缓存中。理论上是这样的，但在实践中，真正的程序几乎不会以随机方式访问内存。
有两个原则制约着现实世界的程序行为。第一条被称为时间局部性，即如果处理器目前正在访问某个内存地址，就很有可能在不久的将来访问这个内存地址(例如：循环中的计数器)。第二种被称为空间局部性，其含义是如果处理器目前正在访问某个内存地址，那么它很有可能会在不久的将来访问邻近的内存地址（例如：处理数组中的数据）。
数据缓存内部组织形式
现在让我们来看看缓存的内部情况。在现代计算机处理器中被分解为 Cache line，每个 Cache line 通常情况下是 64bytes 的大小。一个 Cache line 对应主存中 64byte 的内存块。获取 64byte 中的任意 1byte 数据，意味着需要加载整个 64byte 内存块到缓存中来。当 cache line 长时间没有使用或需要使用新的数据去替换，缓存将返回修改后的块到主存中去。这整个过程程序并不知道。
让程序运行更快的一些技巧
对数据缓存有了一定的了解后，让我们来看看如何将数据缓存相关的原理应用到你的程序中，从而使你的程序拥有更好的性能。
注意：下面每小节，我使用 C 写法的数组和 C++ 写法的数组(vector、array),以及 C 写法(struct)和 C++ 写法(class)的类。
当获取线性数据时，尽量使用vector和array
链表，hash maps,字典等，都是十分有用的数据结构，但是，它们都不是缓存优化的。在这些数据结构中遍历，将会带来很大的缓存丢失。如果，当前程序性能是最重要的因素，那么将这些数据结构转为数组。 如果这是不可能的，尝试将数组的缓存效率和其他数据的灵活性结合起来。Gap_buffer 是这种结合的很好例子。它将链表结构和数组结构结合，这使得其具有卓越的缓存效率和较低代价的元素添加和删除。另一个例子是 Judy_array ，稀疏数组的树形实现，同样的拥有很低代价的元素插入和删除并且缓存友好。
经常访问的数据，在内存中应当是相邻的
如果有几个变量被一起访问，它们应该被逐一声明。这就增加了另一个变量在处理器访问后已经在缓存中的可能性。因为在处理器访问了第一个变量之后，另一个变量已经在缓存中了。从而避免了缓冲区的缺失。
考虑下面的类：
这个类实现了一个链接指针列表。如果我们的程序以这样的方式使用该类，即把变量 head 和 count 作为一个包来访问，那么它们应该一个接一个地放在类定义中。在这种情况下我们增加了它们实际在同一缓存行中的概率。
使用数据数组替换指针数组
当谈到类或结构的数组时，人们想到的第一个想法是使用指针而不是值。这种解决方案与数组相比有很多优点，包括运行时的多态性和在数组中未分配元素的情况下，对内存的使用更少，但会有一个性能缺陷。 使用指针访问该变量时，必然会涉及到高速缓存的缺失。 因此，为了快速访问数组，可以不使用指针而使用值。
因此，现在当把类的数组作为值时，我们将获得一些好处。每当我们访问数组中的一个元素时，缓存预取器就会获取更多与我们当前访问的元素接近的元素。 如果，我们访问的是数组中彼此相邻的元素，数据缓存被最大限度地利用了。
优化对类或结构数组的访问
如果我们以随机的方式访问数组中的元素，就会出现一些缓存丢失的情况。但是我们会有更多或者更少的丢失取决于我们在类中如何组织数据。例如：
假设我们有一个类 并且该类的大小为 48btyes。阵列的第一个元素从偏移量 0 开始，第二个元素从偏移量 48 开始，第三个元素从偏移量 96 开始，第四个元素从偏移量 96 开始。如果我们的cache line是64bytes，那么意味着第一个类元素在第一个 cache line 中，第二个元素将被分别存在第一个和第二个cache line中，第三个元素也将被分别存在两个 cache line 中…
在对类的元素进行随机访问的情况下，将一个元素分割在两个高速缓存线之间，从数据缓存利用率的角度来说是不好的。缓存存储器需要两次访问主存储器才能读取一个元素。那么如何避免呢何使每个元素适合最小数量的cache line面是一些规则：
- 类的大小需要是cache line大小的倍数。
- 数组的起始地址需要是cache line大小的倍数。
要使类的大小是缓存行大小的倍数，我们可以手动的填充使其满足cache line 或者告诉编译器自动帮我们填充，在C++11中允许使用 来指定。当然 GCC/CLANG 编译器提供了 实现相同功能。更好的解决方案是让编译器和库来帮助我们；我们可以用 去分配对齐的内存在堆中，或者使用 和 在栈或者全局内存中分配内存。下面是一个使用分配类数组的例子:
语法看起来非常的复杂，其实很简单。我们声明了 类型的指针，该指针用来保存类数组。接下来我们使用 去为数组分配内存。同时指定了对其参数为64。最后，在循环中，我们为数组中的每个元素调用构造函数。注意，我们使用的是操作符，这个操作符不做内存分配，而是它在作为参数提供的内存上执行构造函数（简单的说，就是执行 array_of_my_class[i] 构造函数，而不进行内存分配）。
有效地访问你的矩阵中的数据
如果你的程序需要处理矩阵，你需要了解矩阵是如何存储在内存中的。矩阵被定义为二维的，但是内存是一维的。C 和 C+ 编译器将矩阵逐行排列。这就意味着如果我们获取矩阵中的某个元素，和这个元素在相同行的一些元素也已经被加载到数据缓存中。
这看起来微不足道，但它会对性能产生深远的影响。考虑一下简单的矩阵乘法算法：
矩阵相乘就是对 的行，和对 的列做运算，按照这个计算规律结合上文的内容，我们可知 是符合缓存规律的，但是， 将会是缓冲的灾难。在 中每访问下一个元素都会导致 cache 丢失，因此上面的代码具有很大的性能缺陷。
那么如何解决上述问题实很简单。进行一种叫做循环互换的转换。 将j上的循环移到最里面的位置。这个解决方案的具体实现如下：
通过这种转换，逐行运行，也要逐行运行。这对性能有很大的影响。
在你的类和结构体中避免填充
关于数据对齐的一个小说明， 适用于所有原始数据类型，如果数据类型为4字节大小，其起始地址需要能被 4 整除。如果数据类型为8字节大小，其起始地址需要能被 8 整除。以此类推对于N字节大小的数据类型，它的起始地址应当能被 N 整除，我们说变量是正确对齐的，或是对齐的，此外都是未对齐。对齐要求通常是由硬件提出的，并由编译器尽可能地强制执行。
为了确保你的类和结构中的数据能正确对齐，C 和 C++ 编译器可以添加填充：这些是在类的成员之间添加的未使用的字节，以确保所有成员都正确对齐。请看下面的例子：
人们期望这个结构体的大小是 ，然而，double需要8字节对其。因此在 之后，编译器添加了 4bytes 的填充，此时 内存对齐了。因此，当前的结构体需要20bytes。
此外，为了使类的数据在数组中正确对齐，类采取了根据其最大成员大小来对齐。而且类的大小是其最大成员大小的整数倍。在上面的例子中，整型是 4 字节对齐，双精度浮点型是 8 字节对齐，因此我们的类应当 8 字节对齐。由于类的大小需要是其对齐方式的倍数，编译器在类的末尾增加了 4 字节的填充。因此，类的大小从原来的 20 字节增加到 24 字节。填充物是如何影响缓存效率的方说，我们的高速缓存存储器有一个 64 字节的 cache line。在我们的例子中，只有2.7个 类可以填充到 cache line 中，而不是我们所期望的四个类实例。另外，填充字节被加载到高速缓存中，但是你的程序是不会用这些填充字节的。这保证了编译器不会插入任何填充物，程序将更好地使用数据缓存。下面对上面类进行了修改的类，其类成员的顺序略有修改，从而避免编译器填充。
这个类的大小现在是 16 字节，四个类实例符合一个 cache line 大小。
在linux中有个叫做 工具可以查找你类的填充，它需要从源码构建。并且不支持 C++11。
尽可能的使用最小的类型
尽可能的使用字节数少的类型也是避免编译器填充的一种方法。有时 可以满足需求的，我们却习惯性的用 。或者说在你的类的定义中有几个变量，你用它来保持各种。你可以用或位域来代替使用。
在上面的例子中，每个 占了 1 bit。但是，编译器为了和 对齐会在 后面自动填充。这可以通过重新安排成员的顺序来避免。
另外的例子：一个64字节的cache line可以存储8个整型或者4个长整型。 如果你有一个 1M 元素的数组，若该数组元素是整型那么将占 4MB，若为长整型就是 8MB。显而易见的是，加载 8MB 到缓冲中，比加载 4MB 慢。
但要注意！处理器在内部以原生字节数（例如：8字节对于现代64位计算机，或者在嵌入式系统的结构中，可能适用更小的字节数）为最佳工作方式。 使用较小的数据类型甚至可能降低速度。因此，你将需要测量以获得确定的性能差异。
尽可能避免堆分配
由于下面几个原因，堆的效率很低：
- 调用 和 是很慢的。
- 对这些位置的访问是间接(通过指针)的，这种方式将导致更多的高速缓存不命中的情况。
另一方面，栈顶几乎总是在缓存中，分配和删除的速度超快。你可以用下面几个技巧来加速。如果，你的程序需要分配可变大小的数组，可以考虑在栈而不是堆上分配数组（ GCC 支持但是有些编译器不支持）。如果，你的程序需要使用malloc分配大量的小内存块，可以考虑分配一个大的内存块，然后根据你的需要把它分成小的。如果，你的程序需要频繁的分配和释放同一类型的对象，那么我们可以考虑缓存内存块，而不是直接释放，如果我们重新需要时，可以很快的重新分配。
尽可能的重复使用缓冲中的数据
理想情况下，我们希望从内存中加载数据到缓存中，对其进行一些修改，然后再把它们返回到操作内存中。如果你需要两次获取相同的数据，你就没有最佳地使用缓存。
以查找一个数组中的最大元素和最小元素为例。
我们在这里调用了两个函数，一个是找到最大值，一个是找到数组中的最小值。每个函数都有自己的循环，并在循环中遍历数组中的元素。
假设数组足够大，数组中的元素将被加载到缓存中两次。
解决办法很简单：在一个循环中完成对数组的所有工作。下面是更正后的版本。
这里我们只对数组进行一次迭代。数组数据只被加载到数据缓存中一次，这样可以更好地利用数据缓存。
尽量避免写内存
所有对内存的写入都要经过数据高速缓存。当进行写操作时，缓存将该 cache line 标记为 “dirty”。若一个 cache line 是 dirty 的，这就意味着他和内存中的数据不同，它的内容迟早会被写回内存中。这导致了速度的减慢。请看这两个算法:
void sort_fast(声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！