Go 开发者必读：CPU 高速缓存原理和应用

据三届世界冠军F1赛车手杰基·斯图尔特(Jackie Stewart)称，他对汽车的工作原理有所了解，使他成为一名更好的飞行员。

“您不必成为一名工程师就可以成为赛车手，但是您必须具有机械同情心（可以理解为机械之心，这个短语源于赛车驾驶,它反映了驾驶员对于汽车有一种天生的感觉，所以他们对于如何最佳的驾御它非常有感觉。）”

Martin Thompson(LMAX Disruptor的设计师)将机械同情的概念应用于编程。简而言之，了解底层硬件将使我们在设计算法，数据结构等方面成为更好的开发人员。

在本文中，我们将深入研究处理器，并了解在优化解决方案时理解其某些概念可以如何帮助我们。

基础知识

现代处理器是基于多重处理器的概念（SMP）。在多重处理器系统中，处理器的设计使两个或多个内核连接到共享内存（也称为主内存或RAM）。另外，为了加快内存访问速度，处理器具有三个不同的缓存级别，分别为L1，L2和L3。精确的架构可能会非常依赖于提供商，处理器型号等。然而，最常见的模型是让L1和L2 本地到一个核，而L3 在所有核之间共享：

缓存离CPU内核越近，其访问延迟和大小越小：

缓存	延迟	CPU 周期	大小
L1 访问	~1.2 ns	~4	32 KB - 512 KB
L2 访问	~3 ns	~10	128 KB - 24 MB
L3 访问	~12 ns	~40	2 MB - 32 MB

同样，这些确切数字取决于处理器型号。但是，粗略估算一下：如果我们认为访问主内存需要60 ns，则访问L1的速度大约快50倍。

在处理器世界中，有一个重要的概念称为``引用位置**''。当处理器访问特定的内存位置时，很有可能：

它将在不久的将来访问相同的位置：这是“时间位置”原则。
它将访问附近的存储位置：这是“空间位置”原则。

时间局部性是拥有CPU缓存的原因之一。但是，我们如何利用空间局部性？解决方案不是复制单个内存位置到CPU缓存，而是复制缓存行。高速缓存行是内存的“连续”段。

高速缓存行的大小取决于高速缓存级别（以及处理器型号）。例如，这是我的机器上的L1高速缓存行的大小：

$ sysctl -a | grep cacheline
hw.cachelinesize: 64

处理器将复制64个字节的连续段，而不是将单个变量复制到L1高速缓存。例如，它不会复制Go切片的单个int64元素，而是会复制该元素以及七个int64元素。

缓存行在Go中的具体应用

让我们来看一个具体的例子，它将会向我们展示CPU缓存的好处。在下面的代码中，我们将合并两个int64元素的平方矩阵：


func BenchmarkMatrixCombination(b *testing.B) {
    matrixA := createMatrix(matrixLength)
    matrixB := createMatrix(matrixLength)

    for n := 0; n < b.N; n++ {
        for i := 0; i < matrixLength; i++ {
            for j := 0; j < matrixLength; j++ {
                matrixA[i][j] = matrixA[i][j] + matrixB[i][j]
            }
        }
    }
}

将 matrixLength 设置为64k, 将导致以下结果：

BenchmarkMatrixSimpleCombination-64000 8
130724158 ns/op

现在, 我们将添加 matrixB[i][j] 而不是添加 matrixB[j][i]:

func BenchmarkMatrixReversedCombination(b *testing.B) {
    matrixA := createMatrix(matrixLength)
    matrixB := createMatrix(matrixLength)

    for n := 0; n < b.N; n++ {
        for i := 0; i < matrixLength; i++ {
            for j := 0; j < matrixLength; j++ {
                matrixA[i][j] = matrixA[i][j] + matrixB[j][i]
            }
        }
    }
}

它会影响结果吗？

BenchmarkMatrixCombination-64000 8
130724158 ns/op
BenchmarkMatrixReversedCombination-64000 2
573121540 ns/op

相当彻底！我们如何解释呢？

让我们尝试绘制正在发生的事情。蓝色圆圈是第一个矩阵上的指针，粉色圆圈是第二个矩阵上的指针。因为我们必须设置 matrixA[i][j] = matrixA[i][j] + matrixB[j][i], 所以当蓝色指针位于位置(4,0)时，粉红色一个在位置(0,4)：

在这幅图中，我们用横坐标和纵坐标表示矩阵，(0,0) 位于正方形左上方。在内存中，矩阵所有不同行是连续分配的。但是，为了清楚，我们坚持用数学表示法。

此外，在以下例子中，矩阵大小是缓存行大小的数倍。所以，一个缓存行不会在下一行“超载”。

我们如何对两个矩阵进行迭代呢？蓝色指针向右移动，直到到达最后一列，然后移动到 (5,0) 的下一行，以此类推。相反地，红色指针向下移动，然后到达下一列。

当粉红色指针访问位置(0,4)时，处理器将缓存整行(在我们的示例中，缓存行大小为4个元素)。因此，当粉红色指针到达位置(0,5)时，我们可以假定变量已经存在于L1中，不是吗？

答案取决于 matrix size:

如果矩阵与 L1 的大小相比足够小，则可以，元素(0,5)已被缓存。
否则，缓存行将在指针到达位置(0,5)之前从 L1 退出。因此，它将生成高速缓存未命中，处理器将不得不以不同的方式访问变量(例如，使用 L2 )。我们将处于这样的状态：

矩阵应从L1中受益多少？让我们做一些数学运算。首先，我们需要知道L1缓存的大小是多少：

$ sysctl hw.l1dcachesize
hw.l1icachesize: 32768

在我的机器上，L1缓存为32768字节，而L1缓存行为64字节。因此，我可以在L1上存储多达512条缓存行。如果我们使用由512个元素组成的矩阵运行相同的基准测试，该怎么办？

BenchmarkMatrixCombination-512 1404 718594 ns/op
BenchmarkMatrixReversedCombination-512 1363 850141 ns/opp

尽管我们缩小了差距(使用64k矩阵，它的速度要慢约300％)，但我们仍然可以看到微小的差异。有什么事吗在基准测试中，我们处理两个矩阵。因此，CPU必须为两者存储高速缓存行。在理想环境中(无需运行其他应用程序等)，由于第一个矩阵，L1高速缓存已满，而由于第二个矩阵，L1高速缓存已满。如果再次将矩阵大小除以2以处理256个元素怎么办：

BenchmarkMatrixCombination-256 5712 176415 ns/op
BenchmarkMatrixReversedCombination-256 6470 164720 ns/op

现在，我们终于到达了两个结果(几乎)相等的地步。

为什么第二个基准比第一个基准稍快？差异看起来非常微妙，并且与Go产生的汇编代码有关。在第二种情况下，使用LEA(加载有效地址)指令对第二矩阵上的指针进行不同的管理。当处理器需要访问内存位置时，存在从虚拟内存到物理内存的转换。使用LEA可以计算内存地址，而无需执行此转换。例如，如果我们管理一片int64元素，并且在第一个元素地址上已经有一个指针，则可以通过简单地将指针移至8个字节来使用LEA加载第二个元素地址。在我们的示例中，这可能是第二次测试更快的潜在原因。但是，我不是装配专家，请随时挑战此分析。如果您想看一下，我上传了第一个函数的汇编代码和第二个函数的汇编代码(反向)。

现在，在矩阵较大的情况下，如何限制处理器高速缓存未命中的影响？有一种技术叫做 loop nest optimization。我们只需要在给定的块内进行迭代，以尽可能多地受益于高速缓存行。

让我们在示例中将一个块定义为4个元素的正方形。在第一个矩阵上，我们从(4,0)迭代到(4,3)。然后我们切换到下一行。因此，在切换到下一列之前，我们仅在第二矩阵上从(0,4)迭代到(3,4)。

当粉红色指针遍历第一列时，处理器将存储相应的缓存行。因此，对块的其余部分进行迭代意味着可以从L1中受益：

让我们编写该算法的Go实现，但首先，我们必须仔细选择块大小。在前面的示例中，它等于高速缓存行。它不应较小，否则，我们将存储将不被访问的元素。在Go基准测试中，我们存储int64元素(8个字节)。高速缓存行为64字节，因此可以存储8个元素。然后，块大小值应至少为8：

func BenchmarkMatrixReversedCombinationPerBlock(b *testing.B) {
    matrixA := createMatrix(matrixLength)
    matrixB := createMatrix(matrixLength)
    blockSize := 8

    for n := 0; n < b.N; n++ {
        for i := 0; i < matrixLength; i += blockSize {
            for j := 0; j < matrixLength; j += blockSize {
                for ii := i; ii < i+blockSize; ii++ {
                    for jj := j; jj < j+blockSize; jj++ {
                        matrixA[ii][jj] = matrixA[ii][jj] + matrixB[jj][ii]
                    }
                }
            }
        }
    }
}

现在，与遍历整个行/列时相比，我们的实现要快67％以上：

BenchmarkMatrixReversedCombination-64000 2 573121540 ns/op
BenchmarkMatrixReversedCombinationPerBlock-64000 6 185375690 ns/op

这是第一个示例，说明了解CPU缓存的工作方式可能有助于我们设计更高效的算法。

错误分享

现在，我们应该对处理器如何管理其内部缓存有很好的了解。快速回顾一下：

由于空间局部性原则，处理器不会将简单的内存地址放在缓存行中。
L1缓存对于给定的CPU内核是本地的。

现在，让我们通过一个示例来讨论L1缓存的一致性。主存储器中存储了两个变量var1和var2。一个核心上的一个线程访问var1，而另一个核心上的另一个线程访问var2。假设两个变量是连续的(或几乎是连续的)，我们最终会遇到两个缓存中都存在var2的情况：

如果第一个线程更新其缓存行会怎样？它可能会更新其行的任何位置，包括var2。然后，当第二个线程读取var2时，该值可能不再一致。

处理器如何维护缓存一致性？如果两条高速缓存行共享一些公共地址，则处理器会将它们标记为 Shared。如果一个线程修改了 Shared 行，它将都标记为 Modified 。为了保证高速缓存的一致性，它需要内核之间的协调，这可能会大大降低应用程序的性能。此问题称为false sharing。

让我们看看Go中的具体应用。在此示例中，我们一个接一个地实例化两个结构。因此，这些结构应在内存中连续分配。然后，我们创建两个goroutine，其中每个goroutine都访问其结构(M是等于1百万的常数)：

type SimpleStruct struct {
    n int
}

func BenchmarkStructureFalseSharing(b *testing.B) {
    structA := SimpleStruct{}
    structB := SimpleStruct{}
    wg := sync.WaitGroup{}

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        wg.Add(2)
        go func() {
            for j := 0; j < M; j++ {
                structA.n += j
            }
            wg.Done()
        }()
        go func() {
            for j := 0; j < M; j++ {
                structB.n += j
            }
            wg.Done()
        }()
        wg.Wait()
    }
}

在此示例中，第二个结构的变量n仅由第二个goroutine访问。但是，由于结构在内存中是连续的，因此它会出现在两条高速缓存行中(假设两个goroutine都安排在位于单独内核上的线程上进行了调度，不一定是这种情况)。这是基准测试结果：

BenchmarkStructureFalseSharing 514 2641990 ns/op

我们如何防止虚假共享？一种解决方案是使用memory padding。目的是确保两个变量之间有足够的空间，以便它们属于不同的缓存行。

首先，让我们在变量声明后填充内存，以创建先前结构的替代方案：


type PaddedStruct struct {
    n int
    _ CacheLinePad
}

type CacheLinePad struct {
    _ [CacheLinePadSize]byte
}

const CacheLinePadSize = 64

然后，我们实例化这两个结构，并在单独的 goroutine 中访问这两个变量：

func BenchmarkStructurePadding(b *testing.B) {
    structA := PaddedStruct{}
    structB := SimpleStruct{}
    wg := sync.WaitGroup{}

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        wg.Add(2)
        go func() {
            for j := 0; j < M; j++ {
                structA.n += j
            }
            wg.Done()
        }()
        go func() {
            for j := 0; j < M; j++ {
                structB.n += j
            }
            wg.Done()
        }()
        wg.Wait()
    }
}

内存方面，这个例子应该是这样的，两个变量是不同缓存行的一部分：

让我们看看结果：

BenchmarkStructureFalseSharing 514 2641990 ns/op
BenchmarkStructurePadding 735 1622886 ns/op

我们使用填充的第二个示例比最初的实现快 40% 左右🎉. 不过，这是一个折衷方案。为了加快执行时间，内存填充需要分配更多内存。

机械同情是应用程序优化中的一个重要概念。在本文中，我们看到了一些示例，这些示例表明了解CPU处理器的工作方式有助于我们减少执行时间。

golang

本文中的所有译文仅用于学习和交流目的，转载请务必注明文章译者、出处、和本文链接
我们的翻译工作遵照 CC 协议，如果我们的工作有侵犯到您的权益，请及时联系我们。

原文地址：https://medium.com/@teivah/go-and-cpu-ca...

译文地址：https://learnku.com/go/t/45683

Go 开发者必读：CPU 高速缓存原理和应用

基础知识

缓存行在Go中的具体应用

错误分享

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

Go 开发者必读：CPU 高速缓存原理和应用

基础知识

缓存行在Go中的具体应用

错误分享

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录