这听起来像是一个主观问题,但我正在寻找的是特定的实例,你可能遇到过与此相关的问题.
如何制作代码,缓存有效/缓存友好(更多缓存命中,尽可能少的缓存未命中)？从两个角度来看,数据缓存和程序缓存(指令缓存),即一个代码中与数据结构和代码结构相关的内容,应该由一个人来处理,使其缓存有效.
是否有必须使用/避免的特定数据结构,或者是否有特定方式来访问该结构的成员等...以使代码缓存有效.
是否存在任何程序结构(if,for,switch,break,goto,...),代码流(对于if内部,如果在for之内等等),应该遵循/避免这个问题？
我期待听到有关制作缓存高效代码的个人经验.它可以是任何编程语言(C,C++,汇编,...),任何硬件目标(ARM,Intel,PowerPC,...),任何操作系统(Windows,Linux,S ymbian,...)等. .
这种变化将有助于更好地理解它.
缓存用于减少CPU停止等待内存请求的停顿次数(避免内存延迟),作为第二种效果,可能减少需要传输的数据总量(保留)内存带宽).
避免遭受内存提取延迟的技术通常是首先要考虑的因素,有时候还有很长的路要走.有限的内存带宽也是一个限制因素,特别是对于许多线程想要使用内存总线的多核和多线程应用程序.一组不同的技术有助于解决后一个问题.
改进空间局部性意味着确保每个缓存行在映射到缓存后完全使用.当我们查看各种标准基准测试时,我们已经看到,在高速缓存行被逐出之前,其中很大一部分未能使用100%的获取高速缓存行.
提高缓存线利用率有三个方面:
它倾向于在缓存中容纳更多有用的数据,从而大大增加了有效的缓存大小.
它倾向于在同一缓存行中容纳更多有用的数据,从而增加了在缓存中找到请求数据的可能性.
它减少了内存带宽要求,因为提取的次数会减少.
常用技巧有:
使用较小的数据类型
组织数据以避免对齐孔(通过减小大小来排序结构成员是一种方式)
注意标准的动态内存分配器,它可能会引起漏洞并在内存中随着时间的推移将数据传播开来.
确保所有相邻数据实际上都在热循环中使用.否则,请考虑将数据结构分解为热和冷组件,以便热循环使用热数据.
避免表现出不规则访问模式的算法和数据结构,并支持线性数据结构.
我们还应该注意,除了使用缓存之外,还有其他方法可以隐藏内存延迟.
现代CPU:通常有一个或多个硬件预取程序.他们在缓存中训练未命中并尝试发现规律.例如,在几次未命中后续缓存行之后,hw预取程序将开始将缓存行提取到缓存中,从而预测应用程序的需求.如果您有常规访问模式,硬件预取器通常做得很好.如果您的程序没有显示常规访问模式,您可以通过自己添加预取指令来改进.
以这样的方式重新组合指令使得总是在高速缓存中丢失的指令彼此接近,CPU有时可以重叠这些提取,使得应用程序仅维持一个等待时间命中(内存级并行性).
要减少整体内存总线压力,您必须开始解决所谓的时间局部性.这意味着您必须重复使用数据,同时仍然没有从缓存中逐出数据.
合并触摸相同数据的循环(循环融合),并采用称为平铺或阻塞的重写技术,努力避免那些额外的内存提取.
虽然这个重写练习有一些经验法则,但您通常必须仔细考虑循环携带的数据依赖性,以确保不会影响程序的语义.
这些东西在多核世界中真正得到回报,在添加第二个线程后,您通常不会看到大量的吞吐量改进.
我无法相信没有更多答案.无论如何,一个经典的例子是"内向外"迭代一个多维数组:
pseudocode
for (i = 0 to size)
for (j = 0 to size)
do something with ary[j][i]
这是高速缓存效率低的原因是因为当您访问单个内存地址时,现代CPU将从主内存加载具有"近"存储器地址的高速缓存行.我们在内部循环中遍历数组中的"j"(外部)行,因此对于通过内部循环的每次行程,高速缓存行将导致刷新并加载一行接近[[ j] [i]进入.如果将其更改为等效:
for (i = 0 to size)
for (j = 0 to size)
do something with ary[i][j]
它运行得更快.
基本规则实际上相当简单.它变得棘手的地方在于它们如何应用于您的代码.
缓存的工作原理有两个:时间局部性和空间局部性.前者的想法是,如果您最近使用了一定数量的数据,您可能很快就会再次需要它.后者意味着如果您最近使用地址X处的数据,您可能很快就会需要地址X + 1.
缓存试图通过记住最近使用的数据块来适应这种情况.它使用高速缓存行运行,通常大小为128字节左右,因此即使您只需要一个字节,包含它的整个高速缓存行也会被拉入高速缓存.因此,如果您之后需要以下字节,它将已经在缓存中.
这意味着您总是希望自己的代码尽可能地利用这两种形式的局部性.不要跳过记忆.在一个小区域做尽可能多的工作,然后继续前进到下一个区域,尽可能多地在那里工作.
一个简单的例子是1800的答案显示的2D数组遍历.如果你一次遍历一行,你就会按顺序读取内存.如果按列方式执行,则会读取一个条目,然后跳转到完全不同的位置(下一行的开头),读取一个条目,然后再次跳转.当你最终回到第一行时,它将不再在缓存中.
这同样适用于代码.跳转或分支意味着缓存使用效率较低(因为您不是按顺序读取指令,而是跳转到不同的地址).当然,小的if语句可能不会改变任何东西(你只是跳过几个字节,所以你仍然会在缓存区域内结束),但函数调用通常意味着你跳到一个完全不同的可能未缓存的地址.除非最近被称为.
指令缓存的使用通常远不是问题.您通常需要担心的是数据缓存.
在结构或类中,所有成员都是连续布局的,这很好.在数组中,所有条目也是连续布局的.在链表中,每个节点都分配在一个完全不同的位置,这很糟糕.指针通常倾向于指向不相关的地址,如果取消引用它,可能会导致缓存未命中.
如果你想利用多个内核,它会变得非常有趣,因为通常一次只有一个CPU在其L1缓存中可能有任何给定的地址.因此,如果两个内核不断访问同一个地址,则会导致持续的缓存未命中,因为它们正在争夺地址.
我建议阅读这篇由九部分组成的文章,如果你对内存和软件的交互方式感兴趣,那么Ulrich Drepper 应该对每个程序员的内存有所了解.它也可以104页PDF格式提供.
与此问题特别相关的部分可能是第2部分(CPU缓存)和第5部分(程序员可以做什么 - 缓存优化).
除数据访问模式外,缓存友好代码中的主要因素是数据大小.较少的数据意味着更多的数据适合缓存.
这主要是内存对齐数据结构的一个因素."常规"智慧说数据结构必须在字边界对齐,因为CPU只能访问整个字,如果一个字包含多个值,你必须做额外的工作(读 - 修改 - 写而不是简单的写) .但是缓存可以完全使这个论点无效.
类似地,Java布尔数组为每个值使用整个字节,以便允许直接对单个值进行操作.如果使用实际位,则可以将数据大小减小8倍,但随后对单个值的访问变得更加复杂,需要进行位移和掩码操作(BitSet类会为您执行此操作).但是,由于缓存效应,当数组很大时,这仍然比使用boolean []快得多.IIRC我用这种方式实现了加速2或3倍.
缓存的最有效数据结构是数组.如果您的数据结构按顺序排列,则CPU会从主内存中读取整个缓存行(通常为32个字节或更多),因此缓存效果最佳.
任何以随机顺序访问内存的算法都会破坏缓存,因为它总是需要新的缓存行来容纳随机访问的内存.另一方面,顺序运行数组的算法最好,因为:
它为CPU提供了预读的机会,例如推测性地将更多内存放入缓存中,稍后将对其进行访问.这种预读可以带来巨大的性能提升.
在大型阵列上运行紧密循环还允许CPU缓存在循环中执行的代码,并且在大多数情况下允许您完全从高速缓存存储器执行算法,而不必阻止外部存储器访问.
我在游戏引擎中看到的一个例子是将数据移出对象并移入自己的数组中.受物理影响的游戏对象也可能附加了许多其他数据.但是在物理更新循环期间,所有关注的引擎都是关于位置,速度,质量,边界框等的数据.因此所有这些都被放入其自己的阵列中并尽可能地优化SSE.
因此在物理循环期间,物理数据使用矢量数学以数组顺序处理.游戏对象使用它们的对象ID作为各种数组的索引.它不是指针,因为如果必须重新定位数组,指针可能会失效.
在许多方面,这违反了面向对象的设计模式,但是通过将数据放在一起需要在相同的循环中进行操作,使代码更快.
这个例子可能已经过时了,因为我希望大多数现代游戏都使用像Havok这样的预建物理引擎.
只有一篇文章触及它,但在进程之间共享数据时出现了一个大问题.您希望避免多个进程尝试同时修改同一缓存行.这里要注意的是"错误"共享,其中两个相邻的数据结构共享一个缓存行,对一个数据结构的修改使另一个的缓存行无效.这可能导致高速缓存行不必要地在多处理器系统上共享数据的处理器高速缓存之间来回移动.避免它的一种方法是对齐和填充数据结构以将它们放在不同的行上.
用户1800信息对"经典例子" 的评论(评论太长)
我想检查两个迭代次序("outter"和"inner")的时间差异,所以我做了一个大型2D数组的简单实验:
measure::start();
for ( int y = 0; y < N; ++y )
for ( int x = 0; x < N; ++x )
sum += A[ x + y*N ];
measure::stop();
和for交换循环的第二种情况.
较慢的版本("x first")为0.88秒,较快的版本为0.06秒.这就是缓存的力量:)
我用过gcc -O2,但仍然没有优化循环.里卡多的评论"大多数现代编译器都可以自己解决这个问题"并不成立
京公网安备 11010802040832号 | 京ICP备19059560号-6 
