设计代码以适应CPU缓存?

esaepe 发布于 2019-11-10 c 最后更新 2019-11-10 12:10 249 浏览

在编写模拟文件时,我的好友说他喜欢尝试编写足够小的程序以适应缓存。这有什么真正的意义?我知道缓存比RAM和主内存更快。是否可以指定您希望程序从缓存运行或至少将变量加载到缓存中?我们正在编写模拟程序,因此任何性能/优化增益都是巨大的优势。 如果你知道解释CPU高速缓存的任何好的链接,那么请指出我的方向。

已邀请:

qnon

赞同来自:

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

gquia

赞同来自:

Ulrich Drepper的What Every Programmer Should Know About Memory是一篇非常有用的论文,它将告诉您关于缓存的更多信息。 Hennessey非常详尽。 Christer和Mike Acton也写了很多关于这个的好东西。 我认为你应该比指令缓存更担心数据缓存—根据我的经验,dcache misses更频繁,更痛苦,更有用。

uet

赞同来自:

内容太长未翻译

zamet

赞同来自:

如果我是你,我会确保我知道代码的哪些部分是热点,我将其定义为

  • 一个不包含任何函数调用的紧密循环,因为如果它调用任何函数,那么PC将花费大部分时间在该函数中,
  • 占执行时间的很大一部分(例如> = 10%),您可以从分析器中确定。 (我只是手动对堆栈进行采样。)
如果您有这样的热点,那么它应该适合缓存。我不知道你是怎么告诉它的,但我怀疑它是自动的。

xeos

赞同来自:

这是Christer Ericsson(战争之神I / II / III成名)对缓存/内存优化的非常好的paper的链接。它已经有几年了,但它仍然非常重要。

noptio

赞同来自:

更新:2014年1月13日 根据这位资深芯片设计师的说法,缓存未命中现在是代码性能的绝对主导因素,因此我们基本上可以追溯到80年代中期和快速286芯片的负载,存储,整数的相对性能瓶颈算术和缓存未命中。 A Crash Course In Modern Hardware by Cliff Click @ Azul 。 。 。 。 。 ---我们现在回到您的定期计划--- 有时,一个例子比描述如何做某事要好。在这种精神下,这是一个特别成功的例子,说明我如何更改一些代码以更好地使用芯片缓存。这是在不久前在486 CPU上完成的,后者迁移到第一代Pentium CPU。对性能的影响是相似的。 示例:下标映射 这是我用来将数据拟合到具有通用实用程序的芯片缓存中的技术的示例。 我有一个长度为1,250个元素的双浮点矢量,这是一个非常长尾的流行病学曲线。曲线的“有趣”部分只有大约200个唯一值,但我不希望双侧if()测试弄乱CPU的管道(因此长尾,可以用作最极端的下标)值蒙特卡罗代码会吐出来的,我需要在代码中的“热点”内进行十几个其他条件测试的分支预测逻辑。 我决定使用一个8位整数向量作为双向量下标的方案,我将其缩短为256个元素。微小的整数在零之前的128之前都具有相同的值,在零之后的128之前具有相同的值,因此除了中间的256个值之外,它们都指向双向量中的第一个或最后一个值。 这会将存储需求缩减为2k(双精度)和1,250字节(8位下标)。这缩小了10,000字节,降至3,298。由于程序在这个内循环中花费了90%或更多的时间,因此2个向量永远不会被推出8k数据缓存。该计划立即使其表现翻了一番。在计算100万抵押贷款的OAS值的过程中,该代码达到了大约1000亿次。 由于曲线的尾部很少被触及,因此很可能只有微小的int矢量的中间200-300个元素实际上保存在缓存中,160-240个中间双精度代表感兴趣的百分之八。在一个下午完成的计划中,我花了一年多时间进行优化,这是一个显着的性能提升。 我同意Jerry,因为我的经验也是如此,将代码倾斜到指令高速缓存并不像优化数据高速缓存那样成功。这就是我认为AMD的常见缓存不如英特尔独立的数据和指令缓存有用的原因之一。 IE:你不希望指令占用缓存,因为它不是很有帮助。在某种程度上,这是因为CISC指令集最初是为了弥补CPU和内存速度之间的巨大差异而创建的,除了80年代后期的异常外,这几乎总是如此。 我用来支持数据缓存和野蛮指令缓存的另一种最受欢迎​​的技术是在结构定义中使用大量的bit-ints,并且通常使用尽可能小的数据大小。要屏蔽4位int以保存一年中的月份,或者用9位来保存一年中的某一天等,需要CPU使用掩码来屏蔽位正在使用的主机整数,这会缩小数据,有效地增加了缓存和总线大小,但需要更多指令。虽然这种技术产生的代码在综合基准测试中表现不佳,但在用户和进程竞争资源的繁忙系统上,它的工作效果非常好。

eomnis

赞同来自:

大多数情况下,这将作为一个占位符,直到我有时间做这个主题正义,但我想分享我认为是一个真正开创性的里程碑 - 在新的英特尔Hazwell微处理器中引入专用位操作指令。 当我在StackOverflow上编写一些代码来反转4096位阵列中的位时,这很容易让人感到非常明显,这些位在引入PC之后30多年,微处理器只是没有太多关注或资源,我希望将更改。特别是,我很乐意看到,对于初学者来说,bool类型在C / C++中变成了一个实际的位数据类型,而不是它当前的荒谬浪费字节。

Hazwell's new Bit Manipulation Instructions 更新:12/29/2013 我最近有机会优化一个环形缓冲区,它以毫秒级的粒度跟踪512个不同资源用户对系统的需求。有一个定时器,每毫秒触发一次,它加上最新切片资源请求的总和,并减去第1,000个时间片的请求,包括现在1000毫秒的资源请求。 头部,尾部向量在内存中彼此相邻,除非首先是头部,然后尾部包裹并在阵列的开始处重新开始。然而,(滚动)摘要切片位于一个固定的,静态分配的数组中,该数组并不特别接近其中任何一个,甚至没有从堆中分配。 考虑到这一点,并研究代码,一些细节引起了我的注意。
  1. 进入的需求同时被添加到Head和Summary切片中,在相邻的代码行中彼此相邻。
  2. 当计时器触发时,Tail被从摘要切片中减去,结果将保留在摘要切片中,正如您所期望的那样
  3. 当计时器触发时调用的第二个函数使服务环的所有指针都前进。尤其是.... 头部覆盖尾部,从而占据相同的记忆位置 新的Tail占用了接下来的512个内存位置,或者包裹了
  4. 用户希望管理的需求数量更灵活,从512到4098,或者更多。我觉得这样做最强大,最笨拙的方法是将1000个时间片和摘要片一起分配为一个连续的内存块,这样,摘要片最终会变成不同的长度是不可能的。比其他1000个时间片。
  5. 鉴于上述情况,我开始怀疑,如果我没有将摘要切片保留在一个位置,而是让它在Head和Tail之间“漫游”,那么我是否能获得更多性能,所以它总是在旁边用于添加新需求的Head,以及当计时器触发时Tail旁边的尾部,并且必须从Summary中减去Tail的值。
我做到了这一点,但后来在这个过程中发现了一些额外的优化。我更改了计算滚动摘要的代码,以便将结果保留在Tail中,而不是Summary切片。为什么?因为下一个函数正在执行memcpy()以将Summary切片移动到刚刚被Tail占用的内存中。 (奇怪但是真的,Tail引领头部,直到环绕它结束时)。通过在Tail中保留求和的结果,我不必执行memcpy(),我只需将pTail分配给pSummary。 以类似的方式,新的Head占用了现在陈旧的Summary slice的旧内存位置,所以我再次将pSummary分配给pHead,并将memset的所有值归零。 引导到环的末端(实际上是鼓,512轨道宽)是Tail,但我只需将其指针与常量pEndOfRing指针进行比较以检测该条件。所有其他指针都可以在其前面分配向量的指针值。 IE:我只需要1:3指针的条件测试来正确包装它们。 最初的设计使用了字节整数来最大化缓存使用率,但是,我能够放松这个约束 - 满足用户处理每个用户每毫秒更高资源数的请求 - 使用无符号短路和STILL双重性能,因为即使有3个相邻512个无符号短路的向量,L1高速缓存的32K数据高速缓存可以轻松容纳所需的3,720个字节,其中2/3个在刚刚使用的位置。仅当尾部,摘要或头部被包裹时,3个中的1个被8MB L3cache中的任何重要“步骤”分开。 此代码的总运行时内存占用量低于2MB,因此它完全由片上高速缓存运行,即使在具有4个内核的i7芯片上,也可以运行此过程的4个实例而不会降低性能,5个进程正在运行,总吞吐量略有增加。这是关于缓存使用的Opus Magnum。