《深入理解计算机系统》P431
冲突不命中在真实的程序中很常见,会导致令人困惑的性能问题。当程序访问大小为2的幂的数组时,直接映射高速缓存中通常会发生冲突不命中。例如,考虑一个计算两个向量点积的函数:
对于 x 和 y 来说,这个函数有良好的空间局部性,因此我们期望它的命中率会比较高。不幸的是,并不总是如此。假设浮点数是4个字节,×被加载到从地址0开始的32字节连续内存中,而 y 紧跟在 x 之后,从地址32开始。为了简便,假设一个块是16个字节(足够容纳4个浮点数),高速缓存由两个组组成,高速缓存的整个大小为32字节。我们会假设变量 sum 实际上存放在一个 CPU 寄存器中,因此不需要内存引用。根据这些假设每个 x[i]和 y[i]会映射到相同的高速缓存组:
在运行时,循环的第一次迭代引用 x[0],缓存不命中会导致包含 x[0] ~ x[3]的块被加载到组0。接下来是对 y[0]的引用,又一次缓存不命中,导致包含 y[O]~ y[3]的块被复制到组0,覆盖前一次引用复制进来的 x 的值。在下一次迭代中,对 x[1]的引用不命中,导致 x[O] ~ x[3]的块被加载回组0,覆盖掉 y[0]~ y[3]的块。因而现在我们就有了一个冲突不命中,而且实际上后面每次对×和 y 的引用都会导致冲突不命中,因为我们在 x 和 y 的块之间抖动( thrash )。术语“抖动”描述的是这样一种情况,即高速缓存反复地加载和驱逐相同的高速缓存块的组。
