12.1 基于 CPU 缓存的优化

机械同情（Mechanical sympathy）是三届 F1 世界冠军 Jackie Steward 创造的一个术语：

要想成为一名赛车手,你不必成为一名工程师,但你必须有机械同理心。

-- Sir Jackie Stewart

简而言之，当您了解系统的设计用途时，无论是 F1 赛车、飞机还是计算机，您都可以与设计保持一致以获得最佳性能。在本节中，我们将深入研究具体示例，说明对 CPU 缓存如何工作的机械同情可以帮助我们优化 Go 应用程序。

12.1.1 CPU 架构

首先，让我们了解 CPU 架构的基础知识以及为什么 CPU 缓存很重要。我们将以 Intel Core i5‑7300 为例。

现代 CPU 依靠缓存来加速内存访问。在大多数情况下，通过三个不同的缓存级别：L1、L2 和 L3。在 i5‑7300 上，这些缓存的大小如下：

L1：64 KB
L2：256 KB
L3：4 MB

i5‑7300 有两个物理核心，但总共有四个逻辑核心（也称为虚拟核心或线程）。将一个物理内核划分为多个逻辑内核在 Intel 家族中被称为超线程。

以下是 Intel Core i5‑7300 的概述（Tn 代表线程 n）：

每个物理核心（核心 0 和核心 1）分为两个逻辑核心（线程 0 和线程 1）。关于 L1 缓存，它分为两个子缓存：用于数据的 L1D 和用于指令的 L1I（每个 32 KB）。事实上，缓存不仅仅与数据有关。当 CPU 执行应用程序时，它还可以缓存一些指令，其原理相同：加快整体执行速度。

内存越接近逻辑核心，访问速度就越快：

L1：大约一纳秒
L2：大约比 L1 慢四倍
L3：比 L1 慢十倍左右

CPU 缓存的物理位置也可以解释这些差异。L1 和 L2 被称为片内，这意味着它们与处理器的其余部分属于同一块硅片。相反，L3 是片外，这部分解释了与 L1 和 L2 相比的延迟差异。

关于主内存（或 RAM），平均访问速度比 L1 慢 50 到 100 倍。我们可以访问存储在 L1 上的多达 100 个变量，而代价是一次访问主存。因此，作为 Go 开发人员，改进的一个途径是确保我们的应用程序利用 CPU 缓存。

12.1.2 缓存行

缓存行的概念是理解的关键。但在介绍它是什么之前，让我们了解为什么我们需要它。

当访问特定的内存位置（例如，读取变量）时，很可能在不久的将来：

将再次引用相同的位置
将引用附近的内存位置

前者指时间局部性，后者指空间局部性。两者都是称为局部性的原则的一部分。例如，让我们看一下计算 int64 切片之和的以下函数：

func sum(s []int64) int64 {
    var total int64
    length := len(s)
    for i := 0; i < length; i++ {
        total += s[i]
    }
    return total
}

在此示例中，时间局部性适用于多个变量：i、length 和 total。事实上，在整个迭代过程中，我们一直在访问这些变量。此外，空间局部性适用于代码指令和切片 s。实际上，由于切片由内存中连续分配的数组支持，因此在此示例中，访问 s[0] 也意味着访问 s[1]、s[2] 等。

时间局部性是我们需要 CPU 缓存的部分原因：加速对相同变量的重复访问。但是，由于空间局部性，CPU 会复制我们所说的缓存行，而不是将单个变量从主存复制到缓存中。

高速缓存行是固定大小的连续内存段，通常为 64 字节（8 个 int64 变量）。每当 CPU 决定缓存 RAM 中的内存块时，它都会将其复制到缓存行。然后，由于内存是一个层次结构，当 CPU 想要访问特定的内存位置时，它将首先检查 L1，然后检查 L2，然后检查 L3，最后，如果这些缓存中不存在，则检查主内存。

让我们用一个具体的例子来说明内存块的获取。我们第一次用 16 个 int64 元素的切片调用 sum 函数。当 sum 访问 s[0] 时，这个内存地址还不会出现在缓存中。如果 CPU 决定缓存它（我们还将在以后的部分讨论这个决定），它将复制整个内存块：

首先，访问 s[0] 会导致缓存未命中，因为该地址尚未出现在缓存中。这种错过被称为强制错过。但是，如果 CPU 获取 0x000 内存块，访问从 1 到 7 的元素将导致缓存命中。然后，当 sum 访问 s[8] 时，将应用相同的逻辑：

同样，访问 s8 会导致强制未命中。然而，如果将 0x100 内存块复制到缓存行中，它也会加快对元素 9 到 15 的访问。

最后，迭代 16 个元素导致两次强制缓存未命中和 14 次缓存命中。

Note 我们可能想知道 CPU 复制内存块时的确切策略。例如，它会将一个块复制到所有级别吗？只有 L1？在这种情况下，L2 和 L3 呢？

我们必须知道存在不同的策略。有时，缓存是包容性的（例如， L2 数据也存在于 L3 中），有时缓存是独占的（例如，L3 被称为牺牲缓存，因为它仅包含从 L2 驱逐的数据）。

通常，这些策略被 CPU 供应商隐藏起来，并且知道起来并不是特别有用。因此，我们不要深入研究这些问题。

让我们讨论一个具体的例子来说明 CPU 缓存有多快。我们将实现两个函数，在迭代 int64 元素切片时计算总数。在一种情况下，我们将每两个元素迭代一次，而在另一种情况下，每八个元素迭代一次：

func sum2(s []int64) int64 {
    var total int64
    for i := 0; i < len(s); i+=2 {
        total += s[i]
    }
    return total
}

func sum8(s []int64) int64 {
    var total int64
    for i := 0; i < len(s); i += 8 {
        total += s[i]
    }
    return total
}

除了迭代之外，这两个函数是相同的。如果我们对这两个函数进行基准测试，我们的直觉可能是第二个版本将快四倍左右，因为我们必须增加四倍以上的元素。然而，运行基准测试表明 sum8 在我的机器上只快了大约 10%。更快，是的，但只有 10%。

原因与缓存行有关。我们讨论过缓存行通常为 64 字节，最多包含八个 int64 变量。在这里，这些循环的运行时间主要由内存访问决定，而不是由增量指令决定。在第一种情况下，四分之三的访问会导致缓存命中。因此，这两个函数的执行时间差异并不大。

这个例子演示了为什么缓存行很重要，如果我们缺乏机械同情，很容易被我们的直觉所愚弄，在这种情况下，CPU 是如何缓存数据的。

让我们继续讨论参考的局部性，并查看利用空间局部性的具体示例。

12.1.3 结构切片与切片结构

本节将讨论一个比较两个函数的执行时间的示例。第一个将结构切片作为参数，并对所有 a 字段求和：

type Foo struct {
    a int64
    b int64
}

func sumFoo(foos []Foo) int64 {
    var total int64
    for i := 0; i < len(foos); i++ {
        total += foos[i].a
    }
    return total
}

sumFoo 接收一个 Foo 切片类型参数，并通过读取每个 a 字段来递增 total。

第二个函数也将计算一个总和。然而，这一次参数是一个包含切片的结构：

type Bar struct {
    a []int64
    b []int64
}

func sumBar(bar Bar) int64 {
    var total int64
    for i := 0; i < len(bar.a); i++ {
        total += bar.a[i]
    }
    return total
}

sumBar 接收一个包含两个切片的 Bar 结构：a 和 b。它遍历 a 的每个元素以递增 total。

我们是否期望这两个功能在速度方面有任何差异？

在运行基准测试之前，让我们直观地看到下图中内存的差异。切片结构更紧凑；因此，需要更少的缓存行来迭代。在这两种情况下，数据量相同：切片中有 16 个 Foo 元素，Bar 切片中有 16 个元素。每个黑色条代表一个将被读取以计算总和的 int64，而每个灰色条代表一个将被跳过的 int64。

在 sumFoo 的例子中，我们接收到包含两个字段 a 和 b 的结构片段。因此，我们将在内存中有连续的 a 和 b。相反，在 sumBar 的情况下，我们收到一个包含两个切片的结构，a 和 b。因此，a 的所有元素将被连续分配。

这种差异不会导致任何内存压缩优化。然而，由于这两个函数的目标都是迭代每个 a，在一种情况下，它需要四个缓存行，而在另一种情况下只需要两个缓存行。

如果我们对这两个函数进行基准测试，sumBar 会更快（在我的机器上大约快 20%）。主要原因是更好的空间局部性使得 CPU 从内存中获取更少的缓存行。

此示例演示了空间局部性如何对性能产生重大影响。为了优化应用程序，我们应该组织数据以从每个单独的缓存行中获得最大价值。

然而，利用空间局部性是否足以帮助 CPU 摆脱困境？我们仍然遗漏了一个关键特征：可预测性。

12.1.4 可预测性

可预测性是指 CPU 预测应用程序将做什么以加速其执行的能力。让我们看一个具体的例子，缺乏可预测性会对我们的应用程序性能产生负面影响。

同样，让我们看一下对元素列表求和的两个函数。第一个将遍历链表并对所有值求和：

type node struct {
    value int64
    next  *node
}

func linkedList(n *node) int64 {
    var total int64
    for n != nil {
        total += n.value
        n = n.next
    }
    return total
}

这个函数接收一个链表，遍历它，并增加一个总数。

另一方面，让我们再次使用我们之前讨论过的 sum2 函数，它迭代一个切片，两个元素中的一个：

func sum2(s []int64) int64 {
    var total int64
    for i := 0; i < len(s); i+=2 {
        total += s[i]
    }
    return total
}

假设链表是连续分配的，例如，由单个函数连续分配一次。在 64 位架构上，一个字的长度为 64 位。因此，如果我们比较函数接收的两个数据结构（链表或切片），我们将得到以下结果（较暗的条表示我们用来增加总数的 int64 元素）：

在这两个示例中，我们都面临类似的压缩。由于链表是一系列值和 64 位指针元素，因此我们使用两个元素中的一个来增加总和。同时，sum2示例仅读取两个元素中的一个。

在这两个示例中，两个数据结构具有相同的空间局部性。在这里，我们可能期望这两个函数的执行时间相似。然而，在切片上迭代的第二个会明显更快（在我的机器上大约是 70%）。那么是什么原因呢？

要理解它，我们必须深入研究跨步的概念。跨步与 CPU 如何处理我们的数据有关。有三种不同类型的步长：

单位步长是指我们要访问的所有值都是连续分配的；例如，一个 int64 切片类型的元素。这个步长对于 CPU 来说是可预测的并且是最有效的，因为它需要最少数量的缓存行来遍历元素。
CPU 仍然可以预测恒定的步长；例如，每两个元素迭代一次的切片。但是，它需要更多的缓存行来遍历数据，因此它的效率低于单位步长。
非单位步长是 CPU 无法预测遍历数据的步长；例如，一个指针切片的链表。由于 CPU 不知道数据是否连续分配，因此它不会获取任何缓存行。

对于 sum2，我们面临着一个恒定的步长。然而，对于链表，我们面临的是非单位步长。尽管我们自己知道数据是连续分配的，但 CPU 并不知道。因此，它无法预测如何遍历链表。

由于不同的步长和相似的空间局部性，迭代链表比值的切片要慢得多。由于更好的空间局部性，我们通常应该支持单位步长而不是恒定步长。然而，无论数据如何分配，非单位步长都无法被 CPU 预测，因此会对性能产生负面影响。

到目前为止，我们讨论了 CPU 缓存速度很快，但比主内存小得多。因此，CPU 需要一种将内存块获取到高速缓存行的策略。此策略称为缓存放置策略，会显着影响性能。

12.1.5 缓存放置策略

在 编写不准确的基准 中，我们讨论了一个带有矩阵的示例，我们必须在其中计算前八列的总和。那时，我们没有解释为什么更改总列数会影响基准测试结果。这听起来可能违反直觉：由于我们只需要读取前八列，为什么更改总列数会影响执行时间？让我们在本节中了解它。

提醒一下，实现如下：

func calculateSum512(s [][512]int64) int64 {
    var sum int64
    for i := 0; i < len(s); i++ {
        for j := 0; j < 8; j++ {
            sum += s[i][j]
        }
    }
    return sum
}

func calculateSum513(s [][513]int64) int64 {
    // Same implementation as calculateSum512
}

我们遍历每一行，每次对前八列求和。当这两个函数每次都对新矩阵进行基准测试时，我们没有观察到任何差异。但是，如果我们继续重复使用同一个矩阵，calculateSum513 在我的机器上的速度大约快 50%。原因在于 CPU 缓存以及如何将内存块复制到缓存行。让我们深入研究它以了解这种差异。

当 CPU 决定复制一个内存块并将其放入缓存时，它必须遵循特定的策略。假设一个 32KB 的 L1D 缓存和一个 64 字节的缓存行，如果一个块被随机放入 L1D，CPU 在最坏的情况下将不得不迭代 512 个缓存行来读取一个变量。这种缓存称为全关联。

为了提高从 CPU 缓存访问地址的速度，设计人员制定了有关缓存放置的不同策略。让我们跳过历史，讨论当今使用最广泛的选项：集合相联缓存，它依赖于缓存分区。

为了使下图更清晰，我们将处理该问题的简化版本：

我们假设一个 512 字节的 L1D 缓存（8 个缓存行）
同时，矩阵将由 4 行和 32 列组成，我们将继续阅读前八列

让我们看看如何将这个矩阵存储在内存中。我们将使用二进制表示来表示内存块地址。此外，灰色块代表我们要迭代的前八个 int64 元素。剩余的块将是迭代期间跳过的块：

每个内存块包含 64 个字节；因此可以存储八个 int64 类型的元素。第一个内存块从 0x0000000000000 开始，而第二个内存块从 0001000000000（二进制为 512）开始，依此类推。我们还代表了可以容纳八行的缓存。

Note 我们将在 不知道数据对齐 中看到切片不一定从块的开头开始。

使用 set-associate 缓存策略，缓存被划分为多个集合。我们假设缓存是 2 向集合关联的，这意味着每个集合包含两行。一个内存块只能属于一个集合，其放置位置由其内存地址决定。要理解它，我们必须将内存块地址分解为三个部分，块偏移量、集合索引和标记位：

块偏移量基于块大小。这里的块大小是 512 字节，512 等于 2^9。因此，地址的前 9 位代表块偏移量 (bo)。
集合索引指示地址属于哪个集合。由于缓存是 2 路集合关联的并且包含八行，所以我们有 8 / 2 = 4 个集合。此外，4 等于 2^2；因此，接下来的两位代表集合索引 (si)。
地址的其余部分是标记位 (tb)。在上图中，为简单起见，我们使用 13 位表示地址。要计算 tb，我们执行 13 - bo - si。在这里，这意味着剩下的两个位代表标记位。

假设函数启动并尝试读取属于地址 0000000000000的 s[0][0]。由于该地址尚不存在于缓存中，因此 CPU 将计算其集合索引并将其复制到相应的缓存集合：

如前所述，九位表示块偏移：它是每个内存块地址的最小公共前缀。然后，两位代表设置的索引。地址为 0000000000000 时，si 等于 00。因此，该内存块将被复制到设置 0。

然后，当函数从 s[0][1] 读取到 s[0][7] 时，数据将已经存在于缓存中。CPU 如何知道它？它将计算内存块的起始地址，计算集合索引和标记位，然后检查集合 0 中是否已经存在 00。

现在，函数读取 s[0][8]，这个地址还没有被缓存。因此，复制内存块 0100000000000 时也会发生相同的操作：

该内存也有一个等于 00 的集合索引，因此它也属于集合 0。缓存行被复制到集合 0 中的下一个可用行。然后，再次从 s[1][1] 读取到 s[1][7] 将导致缓存命中。

现在事情开始变得有趣了。该函数读取 s[2][0]，并且该地址不存在于缓存中。因此，将执行相同的操作：

在这里，set index 又等于 00。但是 set 0 已经满了，那么 CPU 会怎么做呢？复制到另一组？不，不会的。CPU 将替换现有缓存线之一以复制内存块 1000000000000。

缓存替换策略取决于 CPU，但通常是伪 LRU 策略（真正的 LRU 太复杂而无法处理）。在这种情况下，假设它替换了我们的第一个缓存行：0000000000000。

这种情况在第三行迭代时会重复：内存地址 1100000000000 也将有一个等于 00 的设置索引，导致再次替换现有的缓存行。

现在，假设基准测试再次执行函数，其中一个切片指向从地址 0000000000000 开始的相同矩阵。当函数读取 s[0][0] 时，该地址不会出现在缓存中。实际上，这个块已经被替换了。

因此，与其利用 CPU 缓存从一个执行到另一个执行，它会导致更多的缓存未命中。这种类型的缓存未命中称为冲突未命中：如果未对缓存进行分区，则不会发生未命中。我们迭代的所有变量都属于集合索引为 00 的内存块。因此，我们只使用一个缓存集，而不是在所有缓存中进行适当的分布。

之前我们讨论了跨步的概念，我们将其定义为 CPU 如何遍历我们的数据。在这个例子中，这个步长被称为临界步长：一个导致访问具有相同集索引的内存地址，因此存储到相同的缓存集。

让我们回到带有两个函数 calculateSum512 和 calculateSum513 的真实示例。基准测试在 32KB 的 8 路组关联 L1D 缓存上执行；因此总共有 64 套。由于缓存行为 64 字节，因此关键步长等于 64 * 64 字节 = 4 KB。 4 KB 的 int64 类型代表 512 个元素。因此，我们达到了 512 列矩阵的关键一步，因此缓存分布不佳。同时，如果矩阵包含 513 列，则不会导致临界步长。这就是为什么我们观察到两个基准之间存在如此巨大差异的原因。

总之，我们必须意识到现代缓存是分区的。根据跨步，我们可以达到只使用一组的情况，这可能会损害应用程序性能并导致许多冲突未命中。这种特殊的步长称为临界步长。对于性能密集型应用程序，我们应该避免它们以充分利用 CPU 缓存。

Note 这样的例子也可以强调为什么微基准测试的结果在与生产不同的系统上执行时应该小心。实际上，如果生产系统具有不同的缓存架构，则可能会导致性能方面的显着差异。

让我们继续讨论 CPU 缓存的影响，但这一次，我们将在编写并发代码时看到具体的影响。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

12-1-Not-understanding-CPU-caches.md

12-1-Not-understanding-CPU-caches.md

12.1 基于 CPU 缓存的优化

12.1.1 CPU 架构

12.1.2 缓存行

12.1.3 结构切片与切片结构

12.1.4 可预测性

12.1.5 缓存放置策略

Files

12-1-Not-understanding-CPU-caches.md

Latest commit

History

12-1-Not-understanding-CPU-caches.md

File metadata and controls

12.1 基于 CPU 缓存的优化

12.1.1 CPU 架构

12.1.2 缓存行

12.1.3 结构切片与切片结构

12.1.4 可预测性

12.1.5 缓存放置策略