“缓存友好代码”和“缓存友好”代码之间有什么区别?
如何确保编写缓存高效的代码?
“缓存友好代码”和“缓存友好”代码之间有什么区别?
如何确保编写缓存高效的代码?
当前回答
除了@Marc Claesen的答案之外,我认为缓存不友好代码的一个有启发性的经典例子是按列而不是按行扫描C二维数组(例如位图图像)的代码。
在一行中相邻的元素在内存中也是相邻的,因此按顺序访问它们意味着按升序访问它们;这是缓存友好的,因为缓存倾向于预取连续的内存块。
相反,按列访问这样的元素对缓存不友好,因为同一列上的元素在内存中彼此相距很远(特别是,它们的距离等于行的大小),所以当您使用这种访问模式时,您在内存中跳跃,可能会浪费缓存检索内存中附近元素的努力。
而破坏表演所需的一切就是
// Cache-friendly version - processes pixels which are adjacent in memory
for(unsigned int y=0; y<height; ++y)
{
for(unsigned int x=0; x<width; ++x)
{
... image[y][x] ...
}
}
to
// Cache-unfriendly version - jumps around in memory for no good reason
for(unsigned int x=0; x<width; ++x)
{
for(unsigned int y=0; y<height; ++y)
{
... image[y][x] ...
}
}
在具有小缓存和/或使用大阵列的系统中(例如,当前机器上的10+百万像素24bpp图像),这种效果可能非常显著(速度上有几个数量级);因此,如果您必须进行多次垂直扫描,通常最好先将图像旋转90度,然后再执行各种分析,将缓存不友好的代码限制在旋转范围内。
其他回答
需要澄清的是,不仅数据应该是缓存友好的,它对代码也同样重要。这除了分支预处理、指令重新排序、避免实际除法和其他技术之外。
通常,代码越密集,存储它所需的缓存线就越少。这会导致更多缓存线可用于数据。
代码不应该到处调用函数,因为它们通常需要一个或多个自己的缓存线,从而导致数据的缓存线更少。
函数应该从缓存行对齐友好地址开始。尽管有(gcc)编译器开关,但要注意,如果函数很短,那么每个函数占用整个缓存线可能会很浪费。例如,如果三个最常用的函数放在一个64字节的缓存行中,那么这比每个函数都有自己的缓存行时浪费更少,并且导致两个缓存行不可用于其他用途。典型的对齐值可以是32或16。
所以,花一些额外的时间让代码更密集。测试不同的构造,编译并检查生成的代码大小和配置文件。
今天的处理器可以处理许多级别的级联内存区域。因此,CPU芯片上会有一堆内存。它可以快速访问此内存。有不同级别的缓存,每次访问速度都比下一次慢(并且更大),直到您到达不在CPU上且访问速度相对较慢的系统内存。
从逻辑上讲,对于CPU的指令集,您只需要引用一个巨大的虚拟地址空间中的内存地址。当你访问一个单独的内存地址时,CPU会去获取它。在过去,它只会获取那个单独的地址。但今天,CPU将在您请求的位周围获取一堆内存,并将其复制到缓存中。它假设如果你要求一个特定的地址,那么你很可能很快就会要求附近的地址。例如,如果您正在复制缓冲区,您将从连续地址读取和写入数据—一个紧接着另一个。
所以今天当你获取一个地址时,它会检查第一级缓存,看看它是否已经将该地址读取到缓存中,如果它没有找到它,那么这就是缓存未命中,它必须进入下一级缓存才能找到它,直到它最终进入主内存。
缓存友好的代码试图使访问在内存中保持紧密,以便最大限度地减少缓存未命中。
所以一个例子是假设你想要复制一个巨大的二维表格。它在内存中以连续的到达行组织,一行紧接着下一行。
如果您从左到右一次复制一行元素,这将是缓存友好的。如果您决定一次复制一列表,您将复制完全相同的内存量,但这将不利于缓存。
优化缓存使用率主要取决于两个因素。
参考地点
第一个因素(其他人已经提到)是参考的地方性。然而,引用的地点实际上有两个维度:空间和时间。
空间的
空间维度也可以归结为两件事:首先,我们希望将信息密集地打包,这样在有限的内存中就可以容纳更多的信息。这意味着(例如)您需要在计算复杂性方面进行重大改进,以证明基于由指针连接的小节点的数据结构是正确的。
第二,我们希望将一起处理的信息也位于一起。典型的缓存以“行”方式工作,这意味着当您访问某些信息时,附近地址的其他信息将与我们接触的部分一起加载到缓存中。例如,当我触摸一个字节时,缓存可能会在该字节附近加载128或256个字节。为了利用这一点,您通常希望对数据进行排列,以最大限度地提高同时使用其他数据的可能性。
对于一个非常简单的例子,这可能意味着线性搜索比二进制搜索更具竞争力。一旦从缓存行加载了一个项目,那么使用该缓存行中的其余数据几乎是免费的。只有当数据足够大,二进制搜索可以减少访问的缓存行数时,二进制搜索才会变得明显更快。
时间
时间维度意味着当您对某些数据执行某些操作时,您希望(尽可能)同时对该数据执行所有操作。
既然您已经将其标记为C++,我将指出一个相对不友好的缓存设计的经典示例:std::valarray。valarray重载了大多数算术运算符,所以我可以(例如)说a=b+c+d;(其中a、b、c和d都是valarrays),以便对这些数组进行元素加法。
这个问题是它遍历一对输入,将结果放入一个临时的,遍历另一对输入等等。对于大量数据,一次计算的结果可能会在下一次计算中使用之前从缓存中消失,因此我们最终会在得到最终结果之前重复读取(和写入)数据。如果最终结果的每个元素都类似于(a[n]+b[n])*(c[n]+d[n]);,我们通常更希望读取每个a[n]、b[n]、c[n]和d[n]一次,进行计算,写入结果,递增n并重复,直到完成。2
线路共享
第二个主要因素是避免线路共享。为了理解这一点,我们可能需要备份并稍微看看缓存是如何组织的。最简单的缓存形式是直接映射。这意味着主存储器中的一个地址只能存储在缓存的一个特定位置。如果我们使用映射到缓存中同一位置的两个数据项,则效果很差——每次使用一个数据项时,必须从缓存中清除另一个数据,以便为另一个腾出空间。缓存的其余部分可能为空,但这些项不会使用缓存的其他部分。
为了防止这种情况,大多数缓存都是所谓的“集合关联”。例如,在4路集合关联缓存中,主内存中的任何项目都可以存储在缓存中的4个不同位置中的任意位置。因此,当缓存要加载一个项目时,它会在这四个项目中查找最近最少使用的3个项目,将其刷新到主内存,并在其位置加载新项目。
问题可能相当明显:对于直接映射的缓存,恰好映射到同一缓存位置的两个操作数可能会导致错误行为。N路集合关联缓存将数字从2增加到N+1。将缓存组织为更多的“方式”需要额外的电路,通常运行速度较慢,因此(例如)8192方式集关联缓存也很少是好的解决方案。
最终,这个因素在可移植代码中更难控制。您对数据放置位置的控制通常相当有限。更糟糕的是,从地址到缓存的精确映射在其他类似处理器之间有所不同。然而,在某些情况下,可以做一些事情,比如分配一个大的缓冲区,然后只使用分配的部分来确保数据共享相同的缓存线(即使您可能需要检测到确切的处理器并相应地执行此操作)。
虚假共享
还有一个相关的项目叫做“虚假分享”。这出现在多处理器或多核系统中,其中两个(或多个)处理器/核具有独立的数据,但位于同一缓存线中。这迫使两个处理器/内核协调对数据的访问,即使每个处理器/内核都有自己的独立数据项。特别是如果两个处理器交替修改数据,这可能会导致数据在处理器之间不断穿梭,从而导致速度大幅放缓。通过将缓存组织成更多的“方式”或类似的方式,这是不容易解决的。防止这种情况的主要方法是确保两个线程很少(最好永远不会)修改可能位于同一缓存行中的数据(同时也要注意控制数据分配地址的难度)。
熟悉C++的人可能会想,这是否可以通过表达式模板等方式进行优化。我很肯定答案是肯定的,这是可能的,如果是的话,这可能是一场相当可观的胜利。然而,我不知道有人这样做,而且考虑到valarray的使用量很少,看到有人这么做,我至少会有点惊讶。如果有人想知道valarray(专门为性能而设计的)是如何严重错误的,那就归结为一件事:它确实是为像旧版Crays这样的机器设计的,使用了快速的主内存,没有缓存。对他们来说,这真的是一个近乎理想的设计。是的,我在简化:大多数缓存并没有精确地测量最近最少使用的项目,但它们使用了一些启发式方法,目的是为了接近这一点,而不必为每次访问保留完整的时间戳。
缓存友好代码是经过优化以有效利用CPU缓存的代码。这通常涉及以利用空间和时间局部性的方式组织数据,这是指一起访问的数据可能一起存储在内存中,并且频繁访问的数据很可能在不久的将来再次访问。
有几种方法可以使代码缓存友好,包括:
使用连续内存布局:通过在连续内存中存储数据块,可以利用空间位置和减少缓存未命中的数量。使用数组:当您需要按顺序访问数据,因为它们允许您利用时间局部性,并将热数据保存在缓存中。小心使用指针:指针可用于访问不连续存储在内存中,但它们也会导致如果过度使用,缓存将丢失。如果您需要使用指针,尝试以利用空间的方式使用它们以及时间局部性,以最小化缓存未命中。使用编译器优化标志:大多数编译器都有优化可用于优化CPU缓存使用的标志。这些标志可以帮助减少缓存未命中的数量代码的总体性能。
需要注意的是,最适合优化CPU缓存使用的特定技术将取决于系统的特定要求和约束。可能需要尝试不同的方法,以找到满足您需求的最佳解决方案。
请注意,缓存不只是缓存连续内存。它们有多行(至少4行),因此不连续和重叠的记忆通常可以同样有效地存储。
以上所有示例中缺少的是衡量基准。关于表演有很多神话。除非你测量它,否则你不知道。除非有明显的改进,否则不要使代码复杂化。