《深入理解計算機系統(tǒng)》P431

沖突不命中在真實的程序中很常見,會導(dǎo)致令人困惑的性能問題。當程序訪問大小為2的冪的數(shù)組時,直接映射高速緩存中通常會發(fā)生沖突不命中。例如,考慮一個計算兩個向量點積的函數(shù):

對于 x 和 y 來說,這個函數(shù)有良好的空間局部性,因此我們期望它的命中率會比較高。不幸的是,并不總是如此。假設(shè)浮點數(shù)是4個字節(jié),×被加載到從地址0開始的32字節(jié)連續(xù)內(nèi)存中,而 y 緊跟在 x 之后,從地址32開始。為了簡便,假設(shè)一個塊是16個字節(jié)(足夠容納4個浮點數(shù)),高速緩存由兩個組組成,高速緩存的整個大小為32字節(jié)。我們會假設(shè)變量 sum 實際上存放在一個 CPU 寄存器中,因此不需要內(nèi)存引用。根據(jù)這些假設(shè)每個 x[i]和 y[i]會映射到相同的高速緩存組:

在運行時,循環(huán)的第一次迭代引用 x[0],緩存不命中會導(dǎo)致包含 x[0] ~ x[3]的塊被加載到組0。接下來是對 y[0]的引用,又一次緩存不命中,導(dǎo)致包含 y[O]~ y[3]的塊被復(fù)制到組0,覆蓋前一次引用復(fù)制進來的 x 的值。在下一次迭代中,對 x[1]的引用不命中,導(dǎo)致 x[O] ~ x[3]的塊被加載回組0,覆蓋掉 y[0]~ y[3]的塊。因而現(xiàn)在我們就有了一個沖突不命中,而且實際上后面每次對×和 y 的引用都會導(dǎo)致沖突不命中,因為我們在 x 和 y 的塊之間抖動( thrash )。術(shù)語“抖動”描述的是這樣一種情況,即高速緩存反復(fù)地加載和驅(qū)逐相同的高速緩存塊的組。