CPU缓存：两个地址之间的距离是否需要小于8字节才能有缓存优势？
CPU cache: does the distance between two address needs to be smaller than 8 bytes to have cache advantage?
这个问题看起来很奇怪..
假设缓存行的大小是 64 字节。此外，假设 L1、L2、L3 具有相同的缓存行大小（this post 表示英特尔酷睿 i7 就是这种情况）。
内存中有两个对象A、B，其（物理）地址相隔N字节。为了简单起见，我们假设A在缓存边界上，即它的地址是64的整数倍。
1) 如果N < 64，当A被CPU取到时，B也会被读入缓存。因此，如果需要 B，并且缓存行尚未被驱逐，CPU 会在很短的时间内获取 B。大家都很开心。
2) 如果N >> 64（即比64大很多），当A被[=77=取到]时，B不会读入缓存连同 A。所以我们说 "CPU doesn't like chase pointers around"，这是避免堆分配的基于节点的数据结构的原因之一，例如 std::list.
我的问题是，如果N > 64但还是很小，比如说N = 70，换句话说，A和 B 不适合一个缓存行但相距不太远，当 A 由 CPU 加载时，获取 B 是否需要相同数量的时钟周期当 N 比 64 大得多时需要什么？
换句话说，当A加载时，让t表示获取B的时间经过，就是t(N=70) 远小于或几乎等于 t(N= 9999999)?
我问这个问题是因为我怀疑 t(N=70) 比 t(N=9999999)，因为 CPU 缓存是 分层的 .
如果有量化研究就更好了
至少有三个因素可以使 A 未命中后更快地获取 B。首先，处理器可以推测性地获取下一个块（独立于任何基于步幅的预取引擎，这将取决于在时间和位置上彼此靠近的两个未命中以确定步幅；单元步幅预取不需要确定步幅值 [它是一个] 并且可以在第一次未命中后开始）。由于这种预取会消耗内存带宽和片上存储，因此它通常具有节流机制（可以简单到具有适度大小的预取缓冲区，并且仅在内存接口足够空闲时才进行高度推测的预取）。
其次，由于 DRAM 被组织成行并且更改行（在单个存储区内）会增加延迟，如果 B 与 A 在同一 DRAM 行中，则对 B 的访问可以避免行预充电的延迟（以关闭先前打开的行）并激活（以打开新行）。 （这也可以提高内存带宽利用率。）
第三，如果B和A在同一个地址转换页，可以避免TLB。 （在许多设计中，分层页面 table 遍历在附近区域也更快，因为可以缓存分页结构。例如，在 x86-64 中，如果 B 与 A 在同一个 2MiB 区域中，则 TLB 未命中可能只需要执行一次内存访问，因为页面目录可能仍被缓存；此外，如果 B 的转换与 A 的转换在同一个 64 字节缓存行中，并且 A 的 TLB 未命中最近，缓存行可能仍然是目前。）
在某些情况下，还可以通过以固定、有序的步幅排列可能丢失的对象来利用基于步幅的预取引擎。这似乎是一个相当困难和有限的上下文优化。
步长可以增加延迟的一个明显方法是引入冲突未命中。大多数缓存使用简单的模二次幂索引和有限的关联性，因此二次幂（或到同一缓存集的其他映射）可以将不成比例的数据量放置在有限数量的集合中。一旦超过结合性，就会发生冲突未命中。 （已提出倾斜关联性和非二次幂模索引来减少此问题，但这些技术尚未被广泛采用。）
(顺便说一句，指针追逐特别慢的原因不仅是空间局部性低，而且在对A的访问完成之后才能开始对B的访问，因为存在数据依赖性，即获取 B 的延迟不能与获取 A 的延迟重叠。）
如果 B 的地址比 A 低，即使它们相邻，也不会在同一缓存行中。所以你的 N < 64 案例命名错误：它实际上是 "same cache line" 案例。
既然你提到了 Intel i7：Sandybridge 系列在 L2 中有一个 "spatial" 预取器，它（如果已经没有很多未完成的未命中）预取成对的另一个缓存行以完成一个自然对齐的 128B 对线。
来自 Intel 的优化手册，在第 2.3 节 SANDY BRIDGE 中：
... Some prefetchers fetch into L1.
Spatial Prefetcher: This prefetcher strives to complete every cache line fetched to the L2 cache with
the pair line that completes it to a 128-byte aligned chunk.
... several other prefetchers try to prefetch into L2
IDK 多快会这样做；如果它在第一个缓存行到达之前不发出请求，那么对于指针追逐的情况就没有多大帮助。依赖加载在缓存行到达 L1D 后只能执行几个周期，如果它真的只是指针追逐而没有一堆计算延迟的话。但是如果它在第一次未命中（包含第二次加载的地址）后立即发出预取，第二次加载可能会发现它的数据已经在 L1D 缓存中，在第一次请求加载后一两个周期到达。
无论如何，这使得 128B 边界与 Intel CPU 中的预取相关。
有关其他因素，请参阅 Paul 的出色回答。
这个问题看起来很奇怪..
假设缓存行的大小是 64 字节。此外，假设 L1、L2、L3 具有相同的缓存行大小（this post 表示英特尔酷睿 i7 就是这种情况）。
内存中有两个对象A、B，其（物理）地址相隔N字节。为了简单起见，我们假设A在缓存边界上，即它的地址是64的整数倍。
1) 如果N < 64，当A被CPU取到时，B也会被读入缓存。因此，如果需要 B，并且缓存行尚未被驱逐，CPU 会在很短的时间内获取 B。大家都很开心。
2) 如果N >> 64（即比64大很多），当A被[=77=取到]时，B不会读入缓存连同 A。所以我们说 "CPU doesn't like chase pointers around"，这是避免堆分配的基于节点的数据结构的原因之一，例如 std::list.
我的问题是，如果N > 64但还是很小，比如说N = 70，换句话说，A和 B 不适合一个缓存行但相距不太远，当 A 由 CPU 加载时，获取 B 是否需要相同数量的时钟周期当 N 比 64 大得多时需要什么？
换句话说，当A加载时，让t表示获取B的时间经过，就是t(N=70) 远小于或几乎等于 t(N= 9999999)?
我问这个问题是因为我怀疑 t(N=70) 比 t(N=9999999)，因为 CPU 缓存是 分层的 .
如果有量化研究就更好了
至少有三个因素可以使 A 未命中后更快地获取 B。首先，处理器可以推测性地获取下一个块（独立于任何基于步幅的预取引擎，这将取决于在时间和位置上彼此靠近的两个未命中以确定步幅；单元步幅预取不需要确定步幅值 [它是一个] 并且可以在第一次未命中后开始）。由于这种预取会消耗内存带宽和片上存储，因此它通常具有节流机制（可以简单到具有适度大小的预取缓冲区，并且仅在内存接口足够空闲时才进行高度推测的预取）。
其次，由于 DRAM 被组织成行并且更改行（在单个存储区内）会增加延迟，如果 B 与 A 在同一 DRAM 行中，则对 B 的访问可以避免行预充电的延迟（以关闭先前打开的行）并激活（以打开新行）。 （这也可以提高内存带宽利用率。）
第三，如果B和A在同一个地址转换页，可以避免TLB。 （在许多设计中，分层页面 table 遍历在附近区域也更快，因为可以缓存分页结构。例如，在 x86-64 中，如果 B 与 A 在同一个 2MiB 区域中，则 TLB 未命中可能只需要执行一次内存访问，因为页面目录可能仍被缓存；此外，如果 B 的转换与 A 的转换在同一个 64 字节缓存行中，并且 A 的 TLB 未命中最近，缓存行可能仍然是目前。）
在某些情况下，还可以通过以固定、有序的步幅排列可能丢失的对象来利用基于步幅的预取引擎。这似乎是一个相当困难和有限的上下文优化。
步长可以增加延迟的一个明显方法是引入冲突未命中。大多数缓存使用简单的模二次幂索引和有限的关联性，因此二次幂（或到同一缓存集的其他映射）可以将不成比例的数据量放置在有限数量的集合中。一旦超过结合性，就会发生冲突未命中。 （已提出倾斜关联性和非二次幂模索引来减少此问题，但这些技术尚未被广泛采用。）
(顺便说一句，指针追逐特别慢的原因不仅是空间局部性低，而且在对A的访问完成之后才能开始对B的访问，因为存在数据依赖性，即获取 B 的延迟不能与获取 A 的延迟重叠。）
如果 B 的地址比 A 低，即使它们相邻，也不会在同一缓存行中。所以你的 N < 64 案例命名错误：它实际上是 "same cache line" 案例。
既然你提到了 Intel i7：Sandybridge 系列在 L2 中有一个 "spatial" 预取器，它（如果已经没有很多未完成的未命中）预取成对的另一个缓存行以完成一个自然对齐的 128B 对线。
来自 Intel 的优化手册，在第 2.3 节 SANDY BRIDGE 中：
... Some prefetchers fetch into L1.
Spatial Prefetcher: This prefetcher strives to complete every cache line fetched to the L2 cache with the pair line that completes it to a 128-byte aligned chunk.
... several other prefetchers try to prefetch into L2
IDK 多快会这样做；如果它在第一个缓存行到达之前不发出请求，那么对于指针追逐的情况就没有多大帮助。依赖加载在缓存行到达 L1D 后只能执行几个周期，如果它真的只是指针追逐而没有一堆计算延迟的话。但是如果它在第一次未命中（包含第二次加载的地址）后立即发出预取，第二次加载可能会发现它的数据已经在 L1D 缓存中，在第一次请求加载后一两个周期到达。
无论如何，这使得 128B 边界与 Intel CPU 中的预取相关。
有关其他因素，请参阅 Paul 的出色回答。