数据结构大小和缓存行访问

在许多系统上，内存是在称为“高速缓存行”的固定块中访问的。在 Intel 系统上，高速缓存行跨越 64 个字节。也就是说，如果您访问字节地址为 64、65……直到 127……的内存，它们都在同一个高速缓存行上。下一个高速缓存行从地址 128 开始，依此类推。

反过来，软件中的数据通常以具有固定大小（以字节为单位）的数据结构进行组织。我们经常将这些数据结构组织成数组。一般来说，一个数据结构可以驻留在不止一个高速缓存行上。例如，如果我在字节地址 127 处放置一个 5 字节的数据结构，那么它将占用一个缓存行的最后一个字节，并在下一个缓存行中占用四个字节。

从内存中加载数据结构时，一个简单的成本模型是访问的缓存行数。如果您的数据结构跨越 32 字节或 64 字节，并且您已对齐数组的第一个元素，那么您每次加载数据结构时只需要访问一个缓存行。

如果我的数据结构有 5 个字节怎么办？假设我将它们打包成一个数组，每个实例仅使用 5 个字节。如果我随机选择一个……我会接触多少缓存行？不出所料，答案平均不超过 1 个缓存行。

让我们概括一下。

假设我的数据结构跨越 z 个字节。设 g 为 z 和 64 之间的最大公约数。假设您从一个大数组中随机加载数据结构的一个实例。一般来说，额外的高速缓存行访问的预期数量是 (z – g)/64。预期的高速缓存行访问总数是 1 + (z – g)/64。您可以检查它是否适用于 z = 32，因为 g 是 32，而 (z – g)/64 是 (32-32)/64 或零。

我为所有不大于缓存行的数据结构创建了下表。最坏的情况是跨越 63 字节的数据结构：然后您几乎总是会触及两个缓存行。

我发现有趣的是，对于大小为 17、20、24 的数据结构，您具有相同的预期缓存行访问次数。这并不意味着跨越 24 字节的数据结构的计算成本与跨越数据结构的成本相同17 个字节。其他一切都相同，较小的数据结构应该会更好，因为它可以更容易地适应 CPU 缓存。

原文： https://lemire.me/blog/2022/06/06/data-structure-size-and-cache-line-accesses/