考虑在一个大小为$n＝2 ^ { 21 }的数组上的一个步长递增循环，其固定步长为256：
哪一个更快完成？我想到了几点考虑：
一开始，您认为应该没有太大的差异，或者第二个循环的速度是$\frac{257}{256}$倍左右，因为它总共进行了较少的迭代。
然后你会想起256是一个很好的整数，这可能与SIMD或内存系统有关，所以第一个可能更快。
但正确的答案是非常违反直觉的：第二个循环更快，而且速度是10倍。
这不仅仅是一个糟糕的步长。如果所有指数都是2的大幂的倍数，则性能会下降：
没有矢量化或任何东西，两个循环产生相同的集合，除了步长。这种影响只归因于内存系统，尤其是一种称为缓存关联性的功能，它是CPU缓存在硬件中实现方式的一种特殊产物。
当我们从理论上研究内存系统时，我们讨论了在软件中实现缓存逐出策略的不同方法。我们关注的一个特定策略是最近最少使用（LRU）策略，它简单有效，但仍然需要一些非平凡的数据操作。
在硬件环境中，这样的方案被称为完全关联缓存：我们有$M$个单元，每个单元都能够容纳一条缓存线，对应于总内存为$N$的任何位置，在发生争用的情况下，最长未被访问的单元将被踢出并替换为新的单元。
完全关联缓存的问题是，在软件中实现“在数百万个缓存线中查找最古老的缓存线”操作非常困难，在硬件中则不可行。您可以创建一个具有16个条目左右的完全关联缓存，但管理数百条缓存线已经变得非常昂贵，或者速度太慢，不值得这么做。
我们可以求助于另一种更简单的方法：只需将RAM中64字节的每个块映射到它可以占用的单个缓存线。比方说，如果我们在内存中有4096个块和64个缓存线，那么每个缓存线在任何时候都存储$\frac{4096}{64}=64$不同块中的一个块的内容。
直接映射缓存很容易实现，除了标记（缓存块的实际内存位置）之外，它不需要存储与缓存线相关的任何附加元信息。缺点是，条目可能被踢出得太快——例如，在映射到同一缓存线的两个地址之间跳转时——导致整体缓存利用率降低。
因此，我们满足于直接映射缓存和完全关联缓存之间的某种东西：集合关联缓存。它将地址空间分成相等的组，这些组分别充当小型全关联缓存。
关联性是这些集合的大小，或者换句话说，每个数据块可以映射到多少不同的缓存线。较高的关联性允许更有效地利用缓存，但也会增加成本。
例如，在我的CPU上，L3缓存是16路集关联的，单个内核有4MB可用空间。这意味着总共有$\frac{2^{22}}{2^{6}}}=2^{16}$缓存线，这些缓存线被分割成$\frac{2^{16}{16}=2^{12}$组，每个组充当它们自己的第$（\frac{1}{2^{12}}}）部分的完全关联缓存。
大多数其他CPU缓存也设置为关联，包括非数据缓存，如指令缓存和TLB。例外情况是只有64个或更少条目的小型专用缓存——它们通常是完全关联的。
如果我们在软件中实现set关联缓存，我们将计算内存块地址的一些哈希函数，然后使用其值作为缓存线索引。在硬件方面，我们不能真正做到这一点，因为它太慢了：例如，对于一级缓存，延迟要求是4或5个周期，甚至取模也需要10-15个周期，更不用说更复杂的东西了。
相反，硬件使用惰性方法。它获取需要访问的内存地址，并将其分为三部分——从低位到高位：
偏移量——64B缓存线内的字索引（$\log_2 64=6$位）；
index-缓存线集的索引（接下来的$12$位，因为三级缓存中有$2^{12}$缓存线）；
标记-内存地址的其余部分，用于区分存储在缓存线中的内存块。
换句话说，所有具有相同“中间”部分的内存地址都映射到同一个集合。
这使得缓存系统实现起来更简单、更便宜，但也容易受到某些不良访问模式的影响。
现在，我们在哪里？哦，是的：为什么256步的迭代会导致如此严重的减速。
当我们跳过256个整数时，指针总是增加$1024=2^{10}$，最后10位保持不变。由于缓存系统使用较低的6位作为偏移量，使用下一个12位作为缓存线索引，因此我们在三级缓存中基本上只使用$2^{12-（10-6）}=2^8$不同的集合，而不是$2^{12}$，这会将三级缓存缩小一倍$2^4=16$。阵列停止装入L3缓存（$N=2^{21}$），并溢出到数量级较慢的RAM中，这会导致性能降低。
缓存关联性效应导致的性能问题在算法中出现的频率非常高，因为出于多种原因，程序员喜欢在索引数组时使用二的幂：
如果最后一个维度是2的幂，则更容易计算多维数组访问的地址，因为它只需要二进制移位而不是乘法。
计算二次幂的模更容易，因为它可以用一个按位的“and”来完成。
在分治算法中，使用两个问题大小的幂是方便的，甚至经常是必要的。
它是最小的整数指数，因此在对内存限制算法进行基准测试时，使用二次幂递增序列作为问题大小是一种流行的选择。
此外，更自然的十次幂可以通过传递性被稍微低一点的二次幂整除。
这尤其适用于使用固定内存布局的隐式数据结构。例如，在大小为$2^{20}$的数组上进行二进制搜索，每次查询大约需要约360ns，而在大小为$（2^{20}+123）$的数组上进行搜索则需要约300ns。当数组大小是2的大幂的倍数时，“最热”元素的索引（我们可能在前十几次迭代中请求的元素）也将被一些大的2幂整除，并映射到同一缓存线——相互踢出，导致性能降低约20%。
幸运的是，这些问题更多的是反常现象，而不是严重问题。解决方案通常很简单：避免以二的幂进行迭代，使多维数组的最后一个维度的大小略有不同，或者使用任何其他方法在内存布局中插入“孔”，或者在数组索引和实际存储数据的位置之间创建一些看似随机的双射。