訪問局部性

有幾種不同類型的訪問局部性：

如果在某一點時訪問了存儲器的特定位置，則很可能在不久的將來將再次訪問相同的位置。在對相同存儲器位置的相鄰訪問之間存在時間接近性。在這種情況下，通常努力將訪問過的數據的副本存儲在可以被更快訪問的特殊存儲器中。時間局部性是空間局部性的特殊情況，即當預期位置與當前位置相同時。

如果特定存儲位置在特定時間被訪問，則很可能在不久的將來訪問附近的存儲位置。在這種情況下，通常嘗試猜測當前訪問周圍的區域的大小和形狀，對於該區域，值得準備更快的訪問。

顯式與存儲器相關的空間局部性。

如果在空間-時間座標空間中路徑的預期部分只有幾個可能的替代方案。這是當指令循環具有簡單結構，或者小的條件分支指令系統的可能結果被限制到只有一小部分可能性的情況。分支局部性通常不是空間局部性，因為少數幾個可能性可以彼此遠離。

它處於空間局部性和分支局部性之間。考慮以等距模式訪問位置的循環，即空間 - 時間座標空間中的路徑是虛線。在這種情況下，簡單的線性函數可以預測在不久的將來將訪問哪個位置。

為了受益於非常頻繁出現的時間和空間局部性，大多數信息存儲系統是分級的；見下文。等距局部性通常由處理器的各種不平凡的增量指令支持。對於分支局部性的情況，當代處理器具有複雜的分支預測器，並且在該預測的基礎上，處理器的存儲器管理器嘗試收集和預處理似合理的替換的數據。

局部性有幾個原因。這些原因是某些方面要實現的目標或接受的情況。以下原因不是不相交的；事實上，下面的列表從最一般的情況到特殊情況：

可預測性

事實上，局部性只是計算機系統中一種可預測的行為。

程序結構

局部性通常因為創建計算機程序的方式而發生，用於處理可決定的問題。通常，相關數據存儲在存儲器中的附近位置。計算中常見的一種模式涉及幾個項目的處理，一次一個。這意味着如果進行大量處理，則將訪問單個項目多次，從而導致時間局部性。此外，移動到下一項意味着將讀取下一項，導致空間局部性，因為存儲器位置通常被批量地讀取。

線性數據結構

局部性通常因為代碼包含循環，傾向於通過索引訪問數組或其他數據結構。當相關數據元素被線性地排列和訪問時，發生順序局部性，即空間局部性的特殊情況。例如，從基地址到最高元素的一維數組中的元素的簡單遍歷將利用存儲器中數組的順序局部性。 ^[1]  當線性遍歷在具有相同結構和大小的相鄰數據結構的較長區域上，訪問每個結構的相互對應的元素而不是整個結構時，發生更一般的等距局部性。這是當矩陣被表示為行的順序矩陣並且需要訪問矩陣的單個列時的情況。

內存層次結構的效率

雖然隨機存取存儲器使程序員能夠在任何時間在任何地方讀取或寫入，但在實踐中，等待時間和吞吐量會受到高速緩存的效率的影響，這通過增加訪問局部性來改進。訪問局部性差導致緩存抖動和緩存污染，為了避免它，具有弱局部性的數據元素可以從緩存旁路。 ^[2] 

如果大多數時間大部分的訪問聚集成簇，並且如果該簇系統的形狀可以被良好地預測，則其可以用於性能優化。有幾種方法可以利用優化技術從局部性獲益。常見的技術有：

這通常在軟件方面實現。

這通常在硬件方面實現。時間和空間局部性可以通過分層存儲硬件來資本化。等距局部性可以由處理器的適當專用指令使用，這種可能性不僅是硬件的責任，也是軟件的，其結構是否適於編譯調用所討論的專門指令的二進制程序。分支局部性是一種更復雜的可能性，因此需要更多的開發工作，但是對於這種局部性的未來探索有比其他更大的空間。

分層存儲器是一種硬件優化，它利用空間和時間局部性的優點，並且可以在存儲器層級的幾個級別上使用。分頁顯然受益於時間和空間局部性。高速緩存是利用時間局部性的簡單示例，因為它是特別設計的，更快但是更小的存儲器區域，通常用於保持最近訪問的數據和最近引用的數據接近的數據，這可能導致潛在的性能提高。

高速緩存中的數據元素不一定對應於在空間上接近主存儲器的數據元素；然而，數據元素一次被帶入高速緩存的一個高速緩存行。這意味着空間局部性同樣重要：如果一個元素被引用，幾個相鄰元素也將被帶入高速緩存。最後，時間局部性在最低級別上起作用，因為非常緊密地訪問結果可以保存在機器寄存器中。一些編程語言（例如C）允許程序員建議某些變量保存在寄存器中。

數據局部性是常規程序的典型存儲器訪問特徵（儘管存在許多不規則的存儲器訪問模式）。它使分層存儲器佈局有利可圖。在計算機中，存儲器被劃分為層次結構以便加速數據訪問。存儲器層級的較低級別傾向於較慢，但是較大。因此，如果程序使用存儲器，同時它被緩存在存儲器層級的上層級中，則程序將實現更大的性能，並且避免將其他數據帶入層級的上層，這將置換將來即將使用的數據。這是一個理想，有時不能實現。

典型的存儲器層次結構（訪問時間和緩存大小是用於討論的2013年使用的典型值的近似值；層次結構中的實際值和實際數量級別不同）：

·CPU寄存器（8-256個寄存器） - 立即訪問，具有處理器最內核的速度

·L1 CPU caches（32 KiB到512 KiB） - 快速訪問，每個內核專有的最內存總線的速度

·L2 CPU caches（128 KiB到24 MiB） - 稍慢的訪問速度，內核總線之間共享的內存總線速度

·L3 CPU caches（2 MiB至32 MiB） - 甚至更慢的訪問速度，同一處理器的更多內核之間共享的內存總線速度

·主要物理內存（RAM）（256 MiB到64 GiB） - 慢速訪問，速度受到主板上處理器和內存模塊之間的空間距離和通用硬件接口的限制

·磁盤（虛擬內存，文件系統）（1 GiB到256 TiB） - 速度非常慢，由於計算機主板和磁盤設備之間的數據通道較窄，外部軟件協議需要在慢硬件接口的頂部

·遠程內存（如其他計算機或互聯網）（實際上無限制） - 速度從非常慢到極慢

現代機器傾向於將較低存儲器的塊讀取到存儲器層級的下一級中。如果這取代了所使用的存儲器，則操作系統嘗試預測哪些數據將被訪問最少（或最近）並將其向下移動到存儲器層級。預測算法傾向於簡單地降低硬件複雜性，儘管它們變得更復雜。

一個常見的例子是矩陣乘法：

for i in 0..n

for j in 0..m

for k in 0..p

C[i][j] = C[i][j] + A[i][k] * B[k][j];

通過切換j和k的循環順序，大矩陣乘法中的加速變得顯着，至少對於在最後一維中放置連續數組元素的語言。這不會改變數學結果，但它提高了效率。在這種情況下，“大”意味着大約每個矩陣中多於100,000個元件，或足夠的可尋址存儲器，使得矩陣將不適合L1和L2高速緩存。

for i in 0..n

for k in 0..p

for j in 0..m

C[i][j] = C[i][j] + A[i][k] * B[k][j];

這種加速的原因是在第一種情況下，A [i] [k]的讀取在高速緩存中（因為k索引是連續的，最後一維），但是B [k] [j]所以在B [k] [j]上存在高速緩存未命中懲罰。 C [i] [j]是不相關的，因為它可以從內部循環中析出。在第二種情況下，C [i] [j]的讀取和寫入都在高速緩存中，B [k] [j]的讀取在高速緩存中，並且A [i] [k]出內循環。因此，第二示例在內部循環中沒有高速緩存未命中懲罰，而第一示例具有高速緩存懲罰。

在2014年的處理器上，第二種情況比第一種情況快五倍，當用C編寫並用gcc -O3編譯時。 （仔細檢查反彙編代碼顯示，在第一種情況下，gcc使用SIMD指令，而在第二種情況下，它不會，但是緩存代價比SIMD增益差得多）

在上述示例中，也可以通過使用稱為阻塞的技術來改進時間局部性。較大的矩陣可以被劃分為均勻大小的子矩陣，使得較小的塊可以在存儲器中被參考（乘法）幾次。

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE)

for (kk = 0; kk < SIZE; kk += BLOCK_SIZE)

for (jj = 0; jj < SIZE; jj += BLOCK_SIZE)

for (i = ii; i < ii + BLOCK_SIZE && i < SIZE; i++)

for (k = kk; k < kk + BLOCK_SIZE && k < SIZE; k++)

for (j = jj; j < jj + BLOCK_SIZE && j < SIZE; j++)

C[i][j] = C[i][j] + A[i][k] * B[k][j];

提供上述解決方案的時間局部性是因為塊在移動之前可以被使用多次，使得其更少地移入和移出存儲器。改進了空間局部性，因為具有連續存儲器地址的元件趨向於一起被拉到存儲器層級。

· P.J. Denning, The Locality Principle, Communications of the ACM, Volume 48, Issue 7, (2005), Pages 19–24

· P.J. Denning, S.C. Schwartz, Properties of the working-set model, Communications of the ACM, Volume 15, Issue 3 (March 1972), Pages 191-198