让CPU非常愤怒的数据访问模式

# 让CPU非常愤怒的数据访问模式 Source: https://blog.weineng.me/posts/slowest_add 给定一个整数数组，求和的**最慢**方式是什么？从左到右依次加？随机加？还是别的什么？在这篇文章中，我们将从头构建一种数据访问模式，通过利用内存陷阱来尽可能慢地求和。 ``` uint32_t* data = ...; // 顺序访问 data[0] + data[1] + data[2] + ... // 随机访问 data[67] + data[69420] + data[42] + ... // 最慢的 data[A] + data[B] + data[C] + ... ``` > **剧透：** 你可以比随机访问模式慢**30%以上**。 --- 一些规则： - 只考虑运行累加函数所花费的时间。生成 `positions` 数组的时间不计入。 - 累加函数固定如下，`data` 是随机填充的，我们只能更改 `positions` 的内容： ```cpp constexpr int ELEMENT_COUNT = (1 << 16) * (PAGE_SIZE / sizeof(uint32_t)); // 2^26 /* * data 包含我们要求和的整数 * positions 是我们用于求和的访问模式 * 溢出是预期的，但我们并不关心实际的和，对吧？ */ uint32_t accumulator(uint32_t const* data, uint32_t const* positions) { uint32_t total = 0; for (uint32_t i = 0; i < ELEMENT_COUNT; ++i) { uint32_t pos = positions[i]; total += data[pos]; } return total; } ``` - 累加器耗时的测量基于 `rdtsc` 周期计数。 一些额外说明： - 共有 2^26 个整数：使用 65536 个页面，每个页面包含 1024 个整数。选择这些数字只是为了在我的机器上运行时间不太长。 - 大页已禁用。 - 所有测量均基于我的机器： 显示机器规格隐藏代码 ``` ❯ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 42 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 8 On-line CPU(s) list: 0-7 Vendor ID: GenuineIntel Model name: Intel® CoreTM Ultra 7 268V CPU family: 6 Model: 189 Thread(s) per core: 1 Core(s) per socket: 8 Socket(s): 1 Stepping: 1 CPU(s) scaling MHz: 50% CPU max MHz: 2200.0000 CPU min MHz: 400.0000 BogoMIPS: 6604.80 Flags: ... Virtualization features: Virtualization: VT-x Caches (sum of all): L1d: 320 KiB (8 instances) L1i: 512 KiB (8 instances) L2: 14 MiB (5 instances) L3: 12 MiB (1 instance) NUMA: ... Vulnerabilities: ... ``` --- 完整代码可以在这里找到（https://github.com/wn/rough_paper/tree/main/slowest），使用 `g++ -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out` 运行。我强烈建议打开 `slowest.cc`（https://github.com/wn/rough_paper/blob/main/slowest/slowest.cc）并运行代码。 我们的任务是找到 `positions` 的排列，使其产生尽可能慢的执行时间。让我们从最简单的访问模式开始： ```cpp void linear(uint32_t const* data, uint32_t* positions) { for (uint32_t i = 0; i < ELEMENT_COUNT; ++i) { positions[i] = i; } } ``` 这可能是最快的排列，耗时 133M（132752394）周期。这在意料之中，因为 CPU 对顺序访问进行了高度优化。 另一方面，我们可以随机化 `positions` 的排列。 ```cpp void fisher_yates_shuffle(uint32_t const* data, uint32_t* positions) { linear(data, positions); uint32_t remaining = ELEMENT_COUNT; for (uint32_t i = 0; i < ELEMENT_COUNT; ++i) { uint32_t random = rand() % remaining; uint32_t tmp = positions[i]; positions[i] = positions[i + random]; positions[i + random] = tmp; --remaining; } } ``` 现在，CPU 无法预测接下来访问哪个数据，因此随机访问需要 1.57B（1572108618）周期，比线性访问慢了 10 倍以上。 我们能做得更差吗？当然。让我们从简单的回归开始，逐步构建最差的排列。首先设置 `positions`，使得每个连续访问的元素之间总是间隔一个缓存行——缓存行是存储在缓存中的数据单位： ```cpp void separated_by_a_cacheline(uint32_t const* data, uint32_t* positions) { constexpr int element_count_per_cacheline = CACHELINE_SIZE / sizeof(uint32_t); constexpr int cacheline_count = ELEMENT_COUNT / element_count_per_cacheline; static_assert(ELEMENT_COUNT % element_count_per_cacheline == 0); int current = 0; for (int element_index = 0; element_index < element_count_per_cacheline; ++element_index) { for (int cacheline_index = 0; cacheline_index < cacheline_count; ++cacheline_index) { positions[current] = cacheline_index * element_count_per_cacheline + element_index; ++current; } } } ``` 这种模式非常糟糕，因为每次访问只使用 64 字节缓存行中的一个 4 字节整数，然后就转向下一个。当我们再次回到同一个缓存行时，有用的重用缓存很可能已被逐出。这导致了可怕的性能，周期数为 719M（718804156），已经是线性扫描的 4 倍长。 当访问间隔一个缓存行的元素时，硬件预取器仍然可以识别 `data` 中的简单流模式，并在加载请求之前开始获取未来的缓存行。然而，许多 Intel 硬件数据预取器不会跨 4 KiB 页面边界预取（https://community.intel.com/t5/Intel-Moderncode-for-Parallel/Multidimensional-Transpose-Prefetching/m-p/1050948#M6795），因此这种帮助不会顺利地从一个页面延续到下一个页面。我的猜测是，跨越页面边界需要另一轮虚拟到物理地址转换，而相邻的虚拟页面不保证映射到相邻的物理页面，因此推测性的跨页预取风险更大且通常用处不大。 因此，我们不只让访问间隔一个缓存行，而是间隔整个页面。每个页面是 4096 字节，代码如下： ```cpp void separated_by_a_page(uint32_t const* data, uint32_t* positions) { constexpr int element_count_per_page = PAGE_SIZE / sizeof(uint32_t); constexpr int page_count = ELEMENT_COUNT / element_count_per_page; static_assert(ELEMENT_COUNT % element_count_per_page == 0); int current = 0; for (int element_index = 0; element_index < element_count_per_page; ++element_index) { for (int page_index = 0; page_index < page_count; ++page_index) { positions[current] = page_index * element_count_per_page + element_index; ++current; } } } ``` 这出现了明显的回归，周期数为 1.41B（1411153154）。上面谈到了阻碍硬件预取器，但这里还有另一个内存效应在起作用。大多数家用机器使用的缓存放置策略是组相联（https://en.wikipedia.org/wiki/Cache_placement_policies#Set-associative_cache）。这意味着给定的缓存行只能放在特定的组中，该组包含多个槽位/路。 ``` ❯ lscpu -C NAME ONE-SIZE ALL-SIZE WAYS TYPE LEVEL SETS PHY-LINE COHERENCY-SIZE L1d 48K 320K 12 Data 1 64 1 64 L1i 64K 512K 16 Instruction 1 64 1 64 L2 2.5M 14M 10 Unified 2 4096 1 64 L3 12M 12M 12 Unified 3 16384 1 64 ``` 在我的机器上，每个 CPU 核心的 L1d 缓存为 48KB，每个组中有 12 个槽位（路），L1d 缓存中有 64 个组。因为有 64 个组，地址 A 和地址 A + 4096 字节（64 组 * 64 字节缓存行）的数据会映射到同一个 L1d 组，它们必须竞争 12 个可用槽位。由于我们按页面（4096 字节）步进，每个内层循环反复命中同一个组，而不是分散到所有 64 个组。这一点很重要，因为那个组只有 12 个槽位。一旦超过 12 个活动的缓存行竞争它，CPU 就必须反复逐出和重新加载缓存行，导致冲突未命中。缓存容量技术上是 48 KB，但对于这种访问模式，可用的 L1d 容量只有 768B（12 路 * 64B）。 现在，让我们退一步，考虑访问模式的更广泛形状： ``` page 0, cacheline 0, elem 0 page 1, cacheline 0, elem 0 page 2, cacheline 0, elem 0 ... page 65534, cacheline 0, elem 0 page 65535, cacheline 0, elem 0 page 0, cacheline 0, elem 1 page 1, cacheline 0, elem 1 page 2, cacheline 0, elem 1 ... ``` 在访问了 65536 个缓存行后，我们又回到同一个缓存行。我们说我们的缓存行重用距离是 65536（在发出 65536 次访问后才再次访问同一个缓存行）。我们可以通过不在访问每个页面后立即再次访问同一个缓存行来做得更差： ```cpp void separated_by_a_page_and_cacheline(uint32_t const* data, uint32_t* positions) { constexpr int elements_per_cacheline = CACHELINE_SIZE / sizeof(uint32_t); constexpr int elements_per_page = PAGE_SIZE / sizeof(uint32_t); constexpr int cacheline_per_page = PAGE_SIZE / CACHELINE_SIZE; constexpr int page_count = ELEMENT_COUNT / elements_per_page; static_assert(ELEMENT_COUNT % elements_per_page == 0); int current = 0; for (int element_index_in_cacheline = 0; element_index_in_cacheline < elements_per_cacheline; ++element_index_in_cacheline) { for (int cacheline_index_in_page = 0; cacheline_index_in_page < cacheline_per_page; ++cacheline_index_in_page) { for (int page_index = 0; page_index < page_count; ++page_index) { positions[current++] = page_index * elements_per_page + cacheline_index_in_page * elements_per_cacheline + element_index_in_cacheline; } } } } ``` 现在我们有了 4B 的缓存行重用距离（65536 页 * 4096 页大小 / 64 缓存行大小），新的访问模式： ``` page 0, cacheline 0, elem 0 page 1, cacheline 0, elem 0 page 2, cacheline 0, elem 0 ... page 65534, cacheline 0, elem 0 page 65535, cacheline 0, elem 0 page 0, cacheline 1, elem 0 page 1, cacheline 1, elem 0 page 2, cacheline 1, elem 0 ... ``` 然而，运行 `separated_by_a_page_and_cacheline`，我们得到了相同的周期数 1.41B（1408519172），这很奇怪，因为我们预期会出现回归。 ``` ❯ lstopo Machine (31GB total) Package L#0 NUMANode L#0 (P#0 31GB) L3 L#0 (12MB) L2 L#0 (2560KB) + L1d L#0 (48KB) + L1i L#0 (64KB) + Core L#0 + PU L#0 (P#0) L2 L#1 (2560KB) + L1d L#1 (48KB) + L1i L#1 (64KB) + Core L#1 + PU L#1 (P#1) L2 L#2 (2560KB) + L1d L#2 (48KB) + L1i L#2 (64KB) + Core L#2 + PU L#2 (P#2) L2 L#3 (2560KB) + L1d L#3 (48KB) + L1i L#3 (64KB) + Core L#3 + PU L#3 (P#3) L2 L#4 (4096KB) L1d L#4 (32KB) + L1i L#4 (64KB) + Core L#4 + PU L#4 (P#4) L1d L#5 (32KB) + L1i L#5 (64KB) + Core L#5 + PU L#5 (P#5) L1d L#6 (32KB) + L1i L#6 (64KB) + Core L#6 + PU L#6 (P#6) L1d L#7 (32KB) + L1i L#7 (64KB) + Core L#7 + PU L#7 (P#7) HostBridge PCI 00:02.0 (VGA) PCI 00:0b.0 (ProcessingAccelerator) PCI 00:14.3 (Network) Net “wlp0s20f3” PCIBridge PCI 04:00.0 (NVMExp) Block(Disk) “nvme0n1” ``` 尽管缓存行重用距离更高了（4M = PAGE_COUNT * PAGE_SIZE / CACHELINE_SIZE），但我们使用的是核心 3，而 `L2 L#3 (2560KB) + L1d L#3 (48KB) + ...` 表明它有 2.5MB 的 L2 缓存和 48KB 的 L1 缓存。在遍历 65536 个页面后，我们已经访问了 4MB 的数据。这大于该核心的私有 L1/L2 容量，因此我们接下来需要的缓存行不太可能还在私有缓存中。它可能还在 L3 中，但 L3 更慢，并且受到其自身的关联性和替换行为的影响。在我们的例子中，只有当缓存行重用距离小于大约 4 万（(2560+48)*1024/64）时，我们才能期望私有缓存重用。我们当前的访问模式是访问连续的页面。与其将访问步长间隔一页，不如将其间隔 N 页。 ```cpp template<int page_stride> void separated_by_stride_pages_and_cacheline(uint32_t const* data, uint32_t* positions) { constexpr int elements_per_cacheline = CACHELINE_SIZE / sizeof(uint32_t); constexpr int elements_per_page = PAGE_SIZE / sizeof(uint32_t); constexpr int cacheline_per_page = PAGE_SIZE / CACHELINE_SIZE; constexpr int page_count = ELEMENT_COUNT / elements_per_page; static_assert(ELEMENT_COUNT % elements_per_page == 0); static_assert(page_stride > 0); int current = 0; for (int element_index_in_cacheline = 0; element_index_in_cacheline < elements_per_cacheline; ++element_index_in_cacheline) { for (int cacheline_index_in_page = 0; cacheline_index_in_page < cacheline_per_page; ++cacheline_index_in_page) { for (int page_start = 0; page_start < page_stride && page_start < page_count; ++page_start) { for (int page_index = page_start; page_index < page_count; page_index += page_stride) { positions[current++] = page_index * elements_per_page + cacheline_index_in_page * elements_per_cacheline + element_index_in_cacheline; } } } } } ``` 现在的访问模式： ``` page 0, cacheline 0, elem 0 page N, cacheline 0, elem 0 page 2N, cacheline 0, elem 0 ... page 0, cacheline 1, elem 0 page N, cacheline 1, elem 0 page 2N, cacheline 1, elem 0 ... page 1, cacheline 0, elem 0 page N + 1, cacheline 0, elem 0 page 2N + 1, cacheline 0, elem 0 ... ``` 而不是只针对特定的 N 运行，我们画一个周期数随页面步长变化的图：  在此扫描中，8 页的访问步长给出了最差的结果，似乎比随机访问更差。单独使用 `-DSTRIDE=8` 运行，我们得到 2.06B（2058425640）周期。图中还有许多其他有趣且不同的内存访问效应，但我们今天不关心它们。步长为 8 时出现峰值的一个可能原因是地址转换：在此步长下，我们也失去了在页表项（page-table entries）中的数据局部性——这些项在页表遍历（page walks）中使用。当访问某个地址的数据时，实际上是在尝试访问虚拟内存地址的数据。内存管理单元（MMU）负责将虚拟内存地址转换为物理内存地址。大多数操作系统入门课程都会涉及这一点，所以我们不在这里解释。我们感兴趣的是 MMU 使用的一个特定数据结构，称为页表项（PTE）。它存储了与虚拟页对应的物理页框号，以及标志和其他元数据。PTE 是 8 字节，意味着一个缓存行容纳 8 个 PTE。对于 8 页的访问步长，**我相信**主导效应是这样的：每次访问时，我们不仅需要获取一个新的缓存行来获取数据，还需要获取另一个缓存行来处理页映射。 我们现在已经成功比随机访问更慢地求和了数字。但我们还没有结束。我们已经饱和了缓存。我们已经破坏了硬件预取器。我们已经停止了缓存行重用。我们还通过使 MMU 在每次访问时都“遍历”而将其推向了边缘。 最后要做的一件事是干扰 DRAM 控制器。商用 DRAM 被组织成通道（channels）、等级（ranks）、芯片（chips）、存储体（banks）、行（rows）和列（columns）。下面的 DIMM 图（将 DIMM 视为内存条）是一个说明性的例子：每个 DIMM 可能包含一个或多个等级，每个等级包含多个芯片。 图 1：DRAM 图片，致谢：sabrent（https://sabrent.com/blogs/memory/channels-ranks-and-sidedness） 上面显示的 DIMM 包含两个等级，每个等级由 8 个 x8 的 DRAM 芯片组成。当内存控制器访问一个等级时，所有八个芯片并行操作：每个芯片向 DIMM 的 64 位数据总线贡献 8 位数据。因此，一个 64 位的字分布在八个芯片上，而不是存储在任何一个芯片中。就本文的目的而言，我们只需要关心一个叫做存储体（banks）的东西。每个芯片包含多个存储体，每个存储体包含多个行，这些行是一连串连续的比特。当访问 DRAM 上特定地址的数据时，DRAM 内存控制器会“激活”包含该数据的特定行，并将该行复制到行缓冲区中。然后，从该缓冲区中，它从我们感兴趣的列中提取 8 位数据。 图 2：访问 DRAM 中的数据，致谢：https://www.mdpi.com/2079-9292/10/4/438 在存储体可以从不同行访问数据之前，它必须先停用当前打开的行并预充电（precharge），然后才能激活新行。这些操作（激活、读取、预充电）需要时间，称为行激活延迟（tRAS）、行预充电时间（tRP）和列地址选通延迟（CL）。 如果访问模式反复敲击同一个存储体中的不同行，内存控制器就会花费大量时间在这些操作上，而不是实际传输数据。这种现象称为行锤（Row Hammer）或更一般地称为行冲突（Row Conflict）。 在我们的情况下，通过精心选择步长，可以确保在同一芯片的同一个存储体中反复发生行冲突。DRAM 的内存地址到物理地址的映射是平台相关的，但通常可以通过系统管理员工具或使用 `dmidecode` 或 RTFM 来推断。 对于我们的步长为 8 的访问模式，由于它已经是除了随机之外最慢的，我们再增加一个存储体级别的冲突，可能会看到额外的减速。 为了做到这一点，我们需要找出哪些页面映射到同一个 DRAM 存储体。我们可以通过测量对同一存储体中不同行的访问延迟来探测映射关系，或者直接查找特定平台上的映射。在我的机器上（Intel Core Ultra 7 268V），我通过实验发现，步长为 8 时已经很大程度上触发了存储体冲突，因此不需要额外更改。 最终结果：步长为 8 的访问模式比随机访问慢约 30%，达到了 2.06B 周期。这比我们开始时快了 15 倍？不对，是慢了 15 倍？原文是慢 10 倍，现在慢更多。 --- 现在，让我们总结一下我们做了什么： 1. **顺序访问**（线性）：133M 周期 - 最快 2. **随机访问**：1.57B 周期 - 比线性慢 10 倍 3. **间隔缓存行**：719M 周期 - 比随机慢？不对，实际上比随机快？719M < 1.57B，所以比随机快。因为缓存行间隔仍允许预取，但页面间隔禁止预取。 4. **间隔页面**：1.41B 周期 - 比随机稍快 5. **间隔页面和缓存行**：1.41B 周期 - 相同 6. **间隔 8 页（带缓存行）**：2.06B 周期 - 比随机慢 30% 所以，最终的最慢访问模式是通过步长为 8 的页面间隔，结合缓存行内的元素顺序，并依赖 TLB 未命中和 DRAM 行冲突。 这就是我们如何让 CPU 非常愤怒的方法。 --- 完整代码和实验细节在 GitHub 仓库中。建议你自己运行代码，并尝试调整参数，看看是否能找到更慢的模式。 （完）