“缓存不友好代码”和“缓存友好”代码之间有什么区别？

如何确保编写高效缓存代码？

解决方法:

预赛

在现代计算机上,只有最低级别的存储器结构(寄存器)可以在单个时钟周期内移动数据.然而,寄存器非常昂贵,并且大多数计算机核心具有少于几十个寄存器(总数为几百到几千字节).在存储器频谱(DRAM)的另一端,存储器非常便宜(即,便宜几百万倍),但在接收数据的请求之后需要数百个周期.为了弥合超快速和昂贵以及超慢速和廉价之间的这种差距,缓存存储器,称为L1,L2,L3,速度和成本降低.我们的想法是,大多数执行代码经常会遇到一小组变量,其余的(很多变量集)很少.如果处理器无法在L1缓存中找到数据,那么它将在L2缓存中查找.如果不存在,则L3缓存,如果不存在,则为主存.这些“未命中”中的每一个都是昂贵的.

(类比是缓存是系统内存,因为系统内存太硬盘存储.硬盘存储超级便宜但速度很慢).

缓存是减少延迟影响的主要方法之一.用Herb Sutter解释(参见下面的链接)：增加带宽很容易,但我们无法摆脱延迟.

始终通过内存层次结构检索数据(最小==最快到最慢).缓存命中/未命中通常是指CPU中*缓存中的命中/未命中 – *别I表示最大==最慢.缓存命中率对性能至关重要,因为每次缓存未命中都会导致从RAM中获取数据(或者更糟糕……),这需要花费大量时间(RAM需要数百个周期,HDD需要数千万个周期).相比之下,从(*别)高速缓存读取数据通常只需要少量的周期.

在现代计算机体系结构中,性能瓶颈是使CPU死亡(例如访问RAM或更高).这只会随着时间的推移而变得更糟.处理器频率的增加目前不再与提高性能相关.问题是内存访问.因此,CPU中的硬件设计工作目前主要集中在优化高速缓存,预取,流水线和并发性上.例如,现代CPU在高速缓存上花费大约85％的死亡,在存储/移动数据时花费高达99％！

关于这个问题有很多话要说.以下是有关缓存,内存层次结构和正确编程的一些很好的参考：

> Agner Fog’s page.在他的优秀文件中,您可以找到涵盖从装配到C语言的详细示例.
>如果您正在观看视频,我强烈建议您查看Herb Sutter’s talk on machine architecture (youtube)(特别是检查12:00及以后！).
> Slides about memory optimization by Christer Ericson(索尼技术总监)
> LWN.net的文章“What every programmer should know about memory“

缓存友好代码的主要概念

缓存友好代码的一个非常重要的方面是关于the principle of locality,其目标是将相关数据放在内存中以允许有效的缓存.就CPU缓存而言,了解缓存行以了解其工作原理非常重要：How do cache lines work?

以下特定方面对优化缓存非常重要：

>时间局部性：当访问给定的内存位置时,很可能在不久的将来再次访问相同的位置.理想情况下,此信息仍将在此时缓存.
>空间局部性：这是指将相关数据放在彼此靠近的位置.缓存发生在许多层面,而不仅仅是在CPU中.例如,当您从RAM读取时,通常会获取比特别要求的更大的内存块,因为程序通常很快就会需要这些数据. HDD缓存遵循相同的思路.特别是对于CPU缓存,缓存行的概念很重要.

使用适当的c++容器

缓存友好与缓存不友好的一个简单示例是c++的std :: vector与std :: list. std :: vector的元素存储在连续的内存中,因此访问它们比访问std :: list中的元素更加缓存,后者将其内容存储在整个地方.这是由于空间局部性.

Bjarne Stroustrup在this youtube clip给出了一个非常好的例证(感谢@Mohammad Ali Baydoun的链接！).

不要忽视数据结构和算法设计中的缓存

尽可能尝试以允许最大程度地使用缓存的方式调整数据结构和计算顺序.这方面的常用技术是cache blocking (Archive.org version),其在高性能计算中非常重要(例如,ATLAS).

了解并利用隐含的数据结构

该领域的许多人有时会忘记的另一个简单示例是用于存储二维阵列的列主要(例如,fortran,matlab)与行主要排序(例如,c,c++).例如,请考虑以下矩阵：

1 2
3 4

在行主要排序中,它作为1 2 3 4存储在存储器中;在列主要排序中,这将被存储为1 3 2 4.很容易看出,不利用此排序的实现将很快遇到(容易避免！)缓存问题.不幸的是,我经常在我的领域(机器学习)看到这样的东西. @MatteoItalia在他的回答中更详细地展示了这个例子.

当从存储器中获取矩阵的某个元素时,它附近的元素也将被提取并存储在高速缓存行中.如果利用排序,这将导致更少的内存访问(因为后续计算所需的接下来的几个值已经在高速缓存行中).

为简单起见,假设高速缓存包括单个高速缓存行,该高速缓存行可以包含2个矩阵元素,并且当从存储器中取出给定元素时,下一个也是如此.假设我们想要对上面的示例2×2矩阵中的所有元素求和(让我们称之为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的链接)：Why is processing a sorted array faster than processing an unsorted array?

避免使用虚函数

在c++的上下文中,虚拟方法代表了关于缓存未命中的一个有争议的问题(存在普遍的共识,即在性能方面应该尽可能避免它们).虚拟函数在查找过程中可能会导致缓存未命中,但只有在不经常调用特定函数时才会发生这种情况(否则它可能会被缓存),所以这被一些人视为非问题.有关此问题的参考,请查看：What is the performance cost of having a virtual method in a C++ class?

常见问题

具有多处理器高速缓存的现代体系结构中的常见问题称为false sharing.当每个单独的处理器试图在另一个存储器区域中使用数据并尝试将其存储在同一高速缓存行中时,会发生这种情况.这会导致缓存行 – 包含另一个处理器可以使用的数据 – 一次又一次地被覆盖.实际上,在这种情况下,不同的线程会通过引发缓存未命中而使彼此等待.
另见(感谢@Matt的链接)：How and when to align to cache line size?

RAM内存中缓存不良的一个极端症状(这可能不是你在这种情况下的意思)就是所谓的thrashing.当进程连续生成页面错误(例如访问不在当前页面中的内存)时会发生这种情况磁盘访问.