Noa*_*oth 703 c++ memory performance caching cpu-cache
" 缓存不友好代码 "和" 缓存友好 "代码之间有什么区别？
如何确保编写高效缓存代码？
Mar*_*sen 913
在现代计算机上,只有最低级别的存储器结构(寄存器)可以在单个时钟周期内移动数据.然而,寄存器非常昂贵,并且大多数计算机核心具有少于几十个寄存器(总数为几百到几千字节).在存储器频谱(DRAM)的另一端,存储器非常便宜(即,便宜几百万倍),但在接收数据的请求之后需要数百个周期.为了弥合超快速和昂贵以及超慢速和廉价之间的这种差距,缓存存储器,称为L1,L2,L3,速度和成本降低.我们的想法是,大多数执行代码经常会遇到一小组变量,其余的(很多变量集)很少.如果处理器无法在L1缓存中找到数据,那么它将在L2缓存中查找.如果不存在,则L3缓存,如果不存在,则为主存.这些"未命中"中的每一个都是昂贵的.
(类比是缓存是系统内存,因为系统内存是硬盘存储.硬盘存储超级便宜,但速度很慢).
缓存是减少延迟影响的主要方法之一.用Herb Sutter解释(参见下面的链接):增加带宽很容易,但我们无法摆脱延迟.
始终通过内存层次结构检索数据(最小==最快到最慢).一个高速缓存命中/缺失通常是指在CPU缓存中的最高等级的命中/缺失-由最高级别我的意思是最大的==最慢的.缓存命中率对性能至关重要,因为每次缓存未命中都会导致从RAM中获取数据(或更糟糕的......),这需要花费大量时间(RAM需要数百个周期,HDD需要数千万个周期).相比之下,从(最高级别)高速缓存读取数据通常只需要少量的周期.
在现代计算机体系结构中,性能瓶颈是CPU死(例如访问RAM或更高).这只会随着时间的推移而变得更糟.处理器频率的增加目前不再与提高性能相关.问题是内存访问.因此,CPU中的硬件设计工作目前主要集中在优化高速缓存,预取,流水线和并发性上.例如,现代CPU在高速缓存上花费大约85%的死亡,在存储/移动数据时花费高达99%!
关于这个问题有很多话要说.以下是有关缓存,内存层次结构和正确编程的一些很好的参考:
缓存友好代码的一个非常重要的方面是关于局部性的原理,其目的是将相关数据放在内存中以允许有效的缓存.在CPU缓存方面,了解缓存行以了解其工作原理非常重要:缓存行如何工作？
以下特定方面对优化缓存非常重要:
使用适当的c ++容器
缓存友好对的一个简单的例子缓存不友好是C++的std::vector对比std::list.一个的元素std::vector被存储在连续的存储器,因此访问它们是多一个以上高速缓存友好比在访问元素std::list,其存储其内容所有的地方.这是由于空间局部性.
Bjarne Stroustrup在这个youtube剪辑中给出了一个非常好的例子(感谢@Mohammad Ali Baydoun的链接!).
不要忽视数据结构和算法设计中的缓存
尽可能尝试以允许最大程度地使用缓存的方式调整数据结构和计算顺序.这方面的常见技术是高速缓存阻塞 (Archive.org版本),这在高性能计算中非常重要(例如ATLAS).
了解并利用隐含的数据结构
另一个简单的例子,该领域的许多人有时会忘记的是列专业(例如fortran,matlab)与用于存储二维数组的行主要排序(例如c,c ++).例如,请考虑以下矩阵:
1 2
3 4
在行主要排序中,它存储在内存中1 2 3 4; 在列主要排序中,这将存储为1 3 2 4.很容易看出,不利用此排序的实现将很快遇到(容易避免!)缓存问题.不幸的是,我看到这样的东西很常在我的域(机器学习).@MatteoItalia在他的回答中更详细地展示了这个例子.
当从存储器中获取矩阵的某个元素时,它附近的元素也将被提取并存储在高速缓存行中.如果利用排序,这将导致更少的内存访问(因为后续计算所需的接下来的几个值已经在高速缓存行中).
为简单起见,假设高速缓存包括单个高速缓存行,该高速缓存行可以包含2个矩阵元素,并且当从存储器中取出给定元素时,下一个也是如此.假设我们想要对上面示例2x2矩阵中的所有元素求和(让我们调用它M):
利用排序(例如,首先在c ++中更改列索引):
M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached)
= 1 + 2 + 3 + 4
--> 2 cache hits, 2 memory accesses
不利用排序(例如,首先在c ++中更改行索引):
M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory)
= 1 + 3 + 2 + 4
--> 0 cache hits, 4 memory accesses
在这个简单的例子中,利用排序大约使执行速度加倍(因为内存访问需要比计算总和更多的周期).在实际应用中的性能差异可能是很多大.
避免不可预测的分支
现代架构具有流水线,编译器正在变得非常擅长重新排序代码,以最大限度地减少因内存访问而导致的延迟.当您的关键代码包含(不可预测的)分支时,很难或不可能预取数据.这将间接导致更多缓存未命中.
这里解释得非常好(感谢@ 0x90的链接):为什么处理排序数组比未排序数组更快？
避免使用虚函数
在c ++的上下文中,virtual方法代表了关于缓存未命中的一个有争议的问题(存在一种普遍的共识,即在性能方面应该尽可能避免它们).虚拟功能可以诱导查找过程中高速缓存未命中,但是这只是发生,如果不经常被称为特定功能(否则它可能会被缓存),所以这被看作是由一些非的问题.有关此问题的参考,请查看:在C++类中使用虚拟方法的性能成本是多少？
具有多处理器高速缓存的现代体系结构中的常见问题称为错误共享.当每个单独的处理器尝试使用另一个内存区域中的数据并尝试将其存储在同一缓存行中时,会发生这种情况.这导致缓存行 - 包含另一个处理器可以使用的数据 - 被一次又一次地覆盖.实际上,在这种情况下,不同的线程会通过引发缓存未命中而使彼此等待.另请参阅(感谢@Matt的链接):如何以及何时对齐缓存行大小？
RAM内存中缓存不佳的一个极端症状(可能不是你在这种情况下的意思)就是所谓的颠簸.当进程连续生成需要磁盘访问的页面错误(例如,访问不在当前页面中的内存)时,会发生这种情况.
Mat*_*lia 135
除了@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] ...
}
}
至
// 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百万像素24 bpp图像)的系统中,这种效果可能非常显着(速度的几个数量级); 因此,如果您必须进行多次垂直扫描,通常最好先旋转90度的图像,然后再执行各种分析,将缓存不友好的代码限制为旋转.
Jer*_*fin 83
优化缓存使用主要归结为两个因素.
第一个因素(其他人已经提到过)是参考地点.参考的位置确实有两个维度:空间和时间.
空间维度也归结为两件事:首先,我们希望密集地收集信息,因此更多信息将适合有限的内存.这意味着(例如)您需要在计算复杂性方面进行重大改进,以证明基于指针连接的小节点的数据结构.
其次,我们希望将一起处理的信息也放在一起.典型的缓存在"行"中工作,这意味着当您访问某些信息时,附近地址的其他信息将与我们触摸的部分一起加载到缓存中.例如,当我触摸一个字节时,缓存可能会在该字节附近加载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
第二个主要因素是避免线路共享.要理解这一点,我们可能需要备份并查看缓存的组织方式.最简单的缓存形式是直接映射.这意味着主存储器中的一个地址只能存储在缓存中的一个特定位置.如果我们使用两个映射到缓存中相同位置的数据项,它会很糟糕 - 每次我们使用一个数据项时,另一个必须从缓存中刷新以便为另一个数据项腾出空间.缓存的其余部分可能为空,但这些项不会使用缓存的其他部分.
为了防止这种情况,大多数缓存都被称为"set associative".例如,在4路组关联高速缓存中,来自主存储器的任何项目都可以存储在高速缓存中的4个不同位置中的任何位置.因此,当缓存要加载项目时,它会查找这四项中最近最少使用的3项,将其刷新到主内存,并将新项目加载到其位置.
问题可能相当明显:对于直接映射缓存,碰巧映射到同一缓存位置的两个操作数可能导致不良行为.N路组关联高速缓存将数量从2增加到N + 1.将缓存组织成更多"方式"需要额外的电路并且通常运行得更慢,因此(例如)8192路组关联缓存也很少是一个好的解决方案.
最终,这个因素在便携式代码中更难以控制.您对数据放置位置的控制通常相当有限.更糟糕的是,从地址到高速缓存的确切映射在其他类似处理器之间变化.但是,在某些情况下,可能值得做一些事情,比如分配一个大缓冲区,然后只使用你分配的部分内容来确保数据共享相同的缓存行(即使你可能需要检测确切的处理器和相应地采取行动).
还有另一个相关项目称为"虚假共享".这出现在多处理器或多核系统中,其中两个(或更多)处理器/核心具有独立的数据,但属于同一高速缓存行.这会强制两个处理器/内核协调对数据的访问,即使每个处理器/内核都有自己独立的数据项.特别是如果两者交替修改数据,这可能导致大量减速,因为数据必须在处理器之间不断地穿梭.通过将缓存组织成更多"方式"或任何类似的方式,这都无法轻易解决.防止它的主要方法是确保两个线程很少(最好是从不)修改可能位于同一缓存行中的数据(对于控制分配数据的地址的难度有相同的警告).
那些熟悉C++的人可能想知道这是否可以通过类似表达模板的方式进行优化.我很确定答案是肯定的,它可以完成,如果是的话,它可能是一个相当可观的胜利.然而,我并不知道有人这样做了,而且由于valarray使用得不多,我至少会对任何人这样做感到惊讶.
如果有人想知道valarray(专门针对性能而设计)是怎么会出现这种严重错误的话,那就归结为一件事:它真的是为像老款Crays这样的机器设计的,它使用了快速的主内存而且没有缓存.对他们来说,这确实是一个近乎理想的设计.
是的,我正在简化:大多数缓存并不能精确地测量最近最少使用的项目,但它们使用了一些旨在接近它的启发式,而无需为每次访问保留完整的时间戳.
Kra*_*lew 22
简单地说:缓存不友好与缓存友好代码的典型例子是矩阵乘法的"缓存阻塞".
朴素矩阵乘法看起来像
for(i=0;i<N;i++) {
for(j=0;j<N;j++) {
dest[i][j] = 0;
for( k==;k<N;i++) {
dest[i][j] += src1[i][k] * src2[k][j];
}
}
}
如果N大,例如,如果N * sizeof(elemType)大于高速缓存大小,则每次访问src2[k][j]将是高速缓存未命中.
有许多不同的方法可以优化缓存.这是一个非常简单的示例:不是在内部循环中每个缓存行读取一个项目,而是使用所有项目:
int itemsPerCacheLine = CacheLineSize / sizeof(elemType);
for(i=0;i<N;i++) {
for(j=0;j<N;j += itemsPerCacheLine ) {
for(jj=0;jj<itemsPerCacheLine; jj+) {
dest[i][j+jj] = 0;
}
for( k=0;k<N;k++) {
for(jj=0;jj<itemsPerCacheLine; jj+) {
dest[i][j+jj] += src1[i][k] * src2[k][j+jj];
}
}
}
}
如果高速缓存行大小为64字节,并且我们在32位(4字节)浮点数上运行,则每个高速缓存行有16个项目.通过这种简单的转换,缓存未命中数减少了大约16倍.
Fancier转换在2D图块上运行,针对多个缓存(L1,L2,TLB)进行优化,等等.
谷歌搜索"缓存阻塞"的一些结果:
http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf
http://software.intel.com/en-us/articles/cache-blocking-techniques
一个优化的缓存阻塞算法的精彩视频动画.
http://www.youtube.com/watch?v=IFWgwGMMrh0
循环平铺非常密切相关:
http://en.wikipedia.org/wiki/Loop_tiling
Raf*_*sta 13
今天的处理器可以处理许多级别的级联存储区域.因此CPU将拥有CPU芯片本身的一堆内存.它可以非常快速地访问这个内存.有一个不同级别的缓存,每个缓存访问(和更大)比下一个更慢,直到你到达不在CPU上的系统内存,并且访问速度相对慢.
从逻辑上讲,对于CPU的指令集,您只需在巨大的虚拟地址空间中引用内存地址即可.当您访问单个内存地址时,CPU将获取它.在过去,它只会获取该地址.但是今天CPU会在你要求的位周围获取一堆内存,并将其复制到缓存中.它假定如果您要求特定地址很可能很快就会要求附近的地址.例如,如果您要复制缓冲区,则可以从连续的地址读取和写入 - 一个接着一个.
所以今天当你获取一个地址时,它会检查第一级缓存以查看它是否已经将该地址读入缓存,如果它没有找到它,那么这是一个缓存未命中,它必须转到下一级别缓存找到它,直到它最终必须进入主内存.
缓存友好代码尝试将访问保持在内存中,以便最大限度地减少缓存未命中.
所以一个例子就是想象你想复制一个巨大的二维表.它在内存中连续排列到达行,后一行紧跟着一行.
如果您从左到右一次一行地复制元素 - 这将是缓存友好的.如果您决定一次将表复制一列,则可以复制完全相同的内存量 - 但这将是缓存不友好的.
需要澄清的是，不仅数据应该是缓存友好的，它对代码也同样重要。这是对分支预测、指令重新排序、避免实际除法和其他技术的补充。
通常，代码越密集，存储它所需的缓存行就越少。这导致更多缓存线可用于数据。
代码不应到处调用函数，因为它们通常需要一个或多个自己的缓存线，从而导致用于数据的缓存线更少。
函数应该从缓存行对齐友好的地址开始。尽管有 (gcc) 编译器开关，但请注意，如果函数非常短，则每个函数占用整个缓存行可能会造成浪费。例如，如果三个最常用的函数适合一个 64 字节的高速缓存行，这比每个函数都有自己的行并导致两个高速缓存行不能用于其他用途时浪费更少。典型的对齐值可能是 32 或 16。
所以花一些额外的时间来使代码密集。测试不同的结构，编译并查看生成的代码大小和配置文件。
| 归档时间： |
|
| 查看次数： |
135811 次 |
| 最近记录： |