设计代码以适应CPU缓存？

Question

写模拟时，我的好友说他喜欢尝试编写足够小的程序以适应缓存。这有什么真正的意义？我知道缓存比RAM和主内存更快。是否可以指定您希望程序从缓存运行或至少将变量加载到缓存中？我们正在编写模拟程序，因此任何性能/优化增益都是巨大的优势。

如果您知道任何解释CPU缓存的好链接，请指出该方向。

Answer 1

至少在典型的台式机CPU中，您不能直接指定有关缓存使用情况的信息。尽管如此，您仍然可以尝试编写缓存友好的代码。在代码方面，这通常意味着展开循环（仅用于一个明显的示例）很少有用 - 它扩展了代码，现代CPU通常会最小化循环开销。您通常可以在数据方面做更多的工作，以改善参考的局部性，防止错误共享（例如，两个常用的数据片段将尝试使用高速缓存的相同部分，而其他部分仍未使用）。

编辑（使一些点位更清楚了）：

一个典型的CPU有许多不同的缓存。现代台式机处理器通常至少具有2级并且通常3级缓存。通过（至少接近）普遍认同，“1级”是与处理元件“最接近”的高速缓存，并且数字从那里上升（2级是下一级，3级之后等）。

大多数情况下（至少）1级高速缓存分为两部分：指令高速缓存和数据高速缓存（英特尔486几乎是我意识到的唯一例外，其中一个高速缓存用于指令和数据 - - 但它是如此彻底的过时，可能不值得思考）。

在大多数情况下，缓存被组织为一组“行”。缓存的内容通常是一次读取，写入和跟踪一行。换句话说，如果CPU要使用来自缓存行的任何部分的数据，那么将从下一个较低级别的存储中读取整个缓存行。靠近CPU的缓存通常较小，缓存线较小。

这个基本的体系结构导致了高速缓存的大部分编写代码的特性。尽可能地，你想要将某些内容读入缓存中，然后用它去做所有事情，然后转向其他的东西。

这意味着当您处理数据时，通常读取较少量的数据（足够小以适应缓存），尽可能多地处理该数据，然后转到下一块数据。像Quicksort这样的算法可以快速将大量输入分解为逐渐变小的数据，这或多或少会自动执行，因此它们往往相当缓存友好，几乎不考虑缓存的精确细节。

这也会影响您如何编写代码。如果你有这样一个循环：

for i = 0 to whatever 
    step1(data); 
    step2(data); 
    step3(data); 
end for 

你通常会更好串尽可能多的措施一起，你可以最多，将适合在高速缓存中的量。一旦你溢出缓存，性能可能会急剧下降。如果上述步骤3中的代码是足够大，它不适合到缓存中，你通常会更好断开回路成两片这样的（如果可能）：

for i = 0 to whatever 
    step1(data); 
    step2(data); 
end for 

for i = 0 to whatever 
    step3(data); 
end for 

循环展开是一个颇受争议的话题。一方面，它可以导致代码的更多的CPU友好，减少了循环本身执行的指令的开销。同时，它可以（并且通常会）增加代码大小，所以它相对缓存不友好。我自己的经验是，在合成基准测试中，往往对真正的大量数据进行非常少量的处理，从循环展开中获得很多。在更实用的代码中，如果您倾向于对单个数据片进行更多处理，您的获益就会少得多 - 并且导致严重性能损失的缓存溢出并不是特别罕见。

数据缓存也被限制在尺寸。这意味着您通常希望您的数据尽可能密集地包装，以便尽可能多的数据适合缓存。仅举一个明显的例子，用指针连接在一起的数据结构需要在计算复杂性方面获得相当多的补偿，以弥补这些指针所使用的数据缓存空间的数量。如果您要使用链接的数据结构，通常至少要确保您将相对较大的数据链接在一起。然而，在很多情况下，我发现我最初学习的用于将数据适配到微小处理器中的小技巧已经学会了几十年（大部分）已经过时了几十年的技巧，在现代处理器上效果不错。目的是让更多的数据放入缓存而不是主内存中，但效果几乎相同。在相当多的情况下，你能想到的CPU指令，近免费的，并且执行的整体速度是由带宽，缓存（或主存储器），所以额外的处理解压数据治理从密集的格式，作品出来你的青睐。当你处理的数据足够多时，这种情况尤其会发生，因为总体速度将受到主内存带宽的控制。在这种情况下，您可以执行lot指令来节省一些内存读取，并且仍然会提前。

并行处理会加剧这个问题。在许多情况下，重写代码以允许并行处理可能导致性能上的增益，甚至有时甚至会导致性能损失。如果总体速度受CPU到内存带宽的控制，拥有更多核心竞争该带宽不太可能产生任何好处（并且可能造成实质性伤害）。在这种情况下，使用多个内核来提高速度往往归结为更紧密地打包数据，并利用更多的处理能力来分解数据，所以真正的速度增益来自减少消耗的带宽，而额外的核心不会浪费时间从密集格式解压缩数据。

可以并行编码产生的另一个基于高速缓存的问题的共享变量（和伪共享）。如果两个（或更多）内核需要写入内存中的相同位置，则保存该数据的高速缓存行最终可能会在内核之间来回穿梭，从而使每个内核都能访问共享数据。结果通常是并行运行速度慢于串行运行（即单个内核）的代码。这种被称为“虚假共享”的变体，其中不同核心上的代码正在写入单独的数据，但是不同核心的数据最终在同一缓存行中。由于缓存控制数据完全依据整行数据，因此数据在核心之间来回移动，导致完全相同的问题。

Answer 2

如果我是你，我会确保我知道这部分代码是热点，我定义为

• 紧密循环不包含任何函数调用，因为如果它调用的任何函数，那么PC将花费大部分时间在该功能上，该功能占据了执行时间的很大一部分（例如> = 10％），您可以从分析器中确定该时间的大部分时间（
• ）。 （我只是手动采样堆栈。）

如果你有这样一个热点，那么它应该适合缓存。我不确定你如何告诉它这样做，但我怀疑它是自动的。

Answer 3

下面是一个非常好的paper链路上通过的Christer爱立信（战争I/II的神/ III名望）高速缓存/内存优化。这已经有几年了，但仍然非常相关。

Answer 4

大多数C/C++编译器倾向于以优化尺寸，而不是为“速度”。也就是说，由于缓存效应，较小的代码通常比展开的代码执行得更快。

Answer 5

一个有用的文件，会告诉你，比你曾经想知道的高速缓存是由What Every Programmer Should Know About Memory乌利齐·德雷珀。 Hennessey涵盖了非常彻底。克里斯特和麦克阿克顿也写了一些关于这方面的好东西。

我觉得你应该比我的经验更关心数据缓存，比指令缓存—，dcache错过更频繁，更痛苦，更有用的修复。

Answer 6

晴这将作为一个占位符，直到我的时间做这个专题公正，但我想和大家分享我认为是一个真正的突破性里程碑 - 引入新的英特尔Hazwell微处理器专用的位操作指令。

它变得非常明显，当我写到这里的一些代码在计算器上扭转位在4096位阵列，引入个人电脑后30+年，微处理器只是不要投入太多的关注或资源位，我希望会改变。特别是，我很想看看，对于初学者来说，bool类型在C/C++中变成了实际的位数据类型，而不是当前浪费的浪费字节。

UPDATE：2013年12月29日

我最近有机会，以优化其在毫秒粒度跟踪512个不同资源用户的需求的系统上的环形缓冲器。有一个计时器每隔几毫秒触发一次，它添加了最新切片的资源请求的总和，并减去了第1,000时间片的请求，包括现在1,000毫秒的资源请求。

头，尾巴矢量在内存中彼此相邻，除非首先是头部，然后是尾部包裹并重新开始在数组的开头。然而，（滚动式）摘要片却处于一个固定的，静态分配的数组中，与其中的任何一个都不是特别接近，甚至没有从堆中分配。

思考这个问题，研究代码几个细节引起了我的注意。

1. 该被进入的需求的代码相邻行被添加到头部，并在同一时间的摘要切片，右边彼此相邻。

2. 当计时器所触发，尾巴被减去摘要片的，结果被留在总结片，如你所期望

3. 调用的时候，计时器所触发的所有先进的第2个功能服务于戒指的指针。特别.... 团长覆盖了尾部，从而占据相同的存储器位置 新尾占用的下一个512个存储位置，或缠绕

4. 用户希望在要求的数量更多的灵活性被管理，从512到4098，或者更多。我觉得最强大，最笨的方法就是将1000个时间片和摘要片一起作为一个连续的内存块分配，这样对于摘要片最终会成为一个不同的长度将是不可能的比其他1,000个时间片。

5. 鉴于上述情况，我开始怀疑，如果我能，如果获得更高的性能，而不必摘要切片保持在一个位置，我有头和尾之间为“漫游”，所以总是对的在头部旁边添加新的需求，并在计时器开启时​​尾部旁边，并且必须从摘要中减去尾部值。

我这样做了，但后来在这个过程中发现了一些额外的优化。我更改了计算滚动摘要的代码，以便将结果留在尾部，而不是摘要片段。为什么？因为下一个函数正在执行memcpy（）来将摘要切片移入刚刚由尾部占据的内存中。 （怪异但真实，尾巴领先头部直到环绕它结束时）。通过将总和的结果留在Tail中，我不必执行memcpy（），我只需将pTail分配给pSummary。

以类似的方式，新的头部占据了已经陈旧摘要片的老内存的位置，如此反复，我刚分配到pSummary PHEAD，并清零所有的值与memset的零。尾部是引导环到达尾部的方式（实际上是一个鼓，512个音轨宽），但我只需要将其指针与一个常量pEndOfRing指针进行比较以检测该条件。所有其他指针都可以被赋值为它之前的向量的指针值。 IE：我只需要1：3指针的条件测试来正确包装它们。

初步设计已经使用字节整数最大化缓存使用，但是，我可以放宽这个限制 - 满足用户要求，以每毫秒处理每用户更高的资源数 - 使用无符号的短裤和STILL 双重性能 ，因为即使有3个512个无符号短路的相邻向量，L1缓存的32K数据缓存也可以容易地保存所需的3,720个字节，其中2/3个字节位于刚才使用的位置。只有尾部，摘要或头部包装的三个中的任何一个在8MB L3cache中的任何重要“步骤”之间分开时才是其中之一。

此代码的总运行时内存占用量小于2MB，因此它完全从片上高速缓存运行，甚至在具有4个内核的i7芯片上，该进程的4个实例可以运行而不会发生任何降级在性能方面，5个进程运行时总吞吐量略有提高。这是关于缓存使用情况的Opus Magnum。

Answer 7

更新：2014年1月13日 根据这一高级芯片设计，高速缓存未命中现在是在代码的性能绝对主导地位的因素，所以我们基本上所有的方式回到了80年代中期，快速286芯片在加载，存储，整数运算和缓存未命中的相对性能瓶颈方面。

A Crash Course In Modern Hardware by Cliff Click @ Azul 。 。 。 。 。

---我们现在返回到你的定期节目---

有时候一个例子是比如何做一个更好的描述。本着这种精神，我特别成功地举例说明了如何更改一些代码以更好地使用芯片缓存。一段时间以前，这是在486 CPU上完成的，后者被迁移到第一代奔腾CPU。对性能的影响是相似的。

实施例：下标映射

下面是我用于将数据装配到芯片的高速缓存，其具有通用效用的技术的一个例子。

我有一个双浮动向量为1,250元件长，这与非常长尾巴的流行病学曲线。曲线中“有趣”的部分只有大约200个独特的值，但我不希望用双面if（）测试来弄乱CPU的管道（因此长尾巴可以用作下标，值的蒙特卡罗代码将吐出），并且我需要在代码中的“热点”内的十几个其他条件测试的分支预测逻辑。

我定居在哪里使用8位整数的向量作为下标到双载体，其余缩短至256种元素的方案。小的整数在128之前都有相同的值，在零之前128，在零之后有128，因此除了中间的256值之外，它们都指向双向量中的第一个或最后一个值。

这缩水存储需求至2k双打，而对于8位标1250个字节。这将10000个字节缩减到3,298。由于该程序花费了90％以上的时间在这个内部循环中，因此2个向量永远不会从8k数据缓存中排出。该计划立即使其性能翻倍。这个代码在计算100万按揭贷款的OAS价值的过程中已经达到了1000亿次。由于很少涉及曲线的尾部，所以很有可能只有微小的int向量中的中间200-300个元素实际上保存在缓存中，而160-240个中间的双元代表1/8的百分比利益。这是一个显着的性能提高，在一个下午完成了一个我花了一年时间优化的项目。

我同意杰里，因为它一直是我的经验也，谓倾斜代码对指令缓存是几乎没有对数据高速缓存/ s的优化成功。这是我认为AMD的普通缓存不如英特尔独立的数据和指令缓存有用的原因之一。 IE：你不希望指令占用缓存，因为它不是很有用。部分原因是因为CISC指令集最初是为了弥补CPU和内存速度之间的巨大差异而创建的，除了80年代后期出现畸变以外，这几乎总是如此。

另一个我喜欢使用数据缓存和野蛮指令缓存的最受欢迎的技术是在结构定义中使用了大量的位元，并且通常使用最小的可能数据大小。为了屏蔽4位整数来保存一年的月份，或9位来保存一年中的某一天，等等，要求CPU使用掩码来屏蔽这些位正在使用的主机整数，这会缩小数据，有效地增加了缓存和总线的大小，但需要更多指令。虽然这种技术产生的代码在综合基准测试中表现不佳，但在繁忙的系统上，用户和进程正在争夺资源，它的功能奇妙。