記憶體階層與快取

時間區域性(temporal locality)

想想桌上那只咖啡杯。如果你一分鐘前喝過它,你很可能很快又會再喝——所以你把它留在桌上,而不是每啜一口就放回櫥櫃。時間區域性就是把這個想法套用到資料上:若程式剛用過某塊記憶體,它很可能不久又會用同一塊,因此把它留在手邊是划算的。

具體來說,時間區域性正是把最近存取過的資料留在快取裡值得做的原因。最經典的來源是迴圈:一個計數變數、一個累加總和、或一個被頻繁呼叫的輔助函式,會在各次迭代間一再被觸碰。硬體不需要事先知道哪些資料是熱的;它只要把最近用過的留著,區域性就讓這成為好的猜測。反面則是淘汰資料的規則——最近最少使用(LRU)替換策略就是直接押注時間區域性,把最久沒被碰過的項目丟出去,因為它最不可能很快又被需要。

時間區域性是支撐整個快取概念的兩根支柱之一(另一根是空間區域性)。它也指導良好的程式設計:若你必須以多種方式處理同一塊資料,就在它還在快取裡時把所有處理都做完,而不是每種處理都把整份資料集串流一遍。誠實的界限是:「最近用過能預測即將用到」是統計傾向,不是必然——對一份從不回頭的資料只掃過一次(純串流工作負載)幾乎沒有時間區域性,用過後把資料快取起來毫無收穫。

在「for i in 0..1000: sum = sum + a[i]」裡,變數 sum 每一次迭代都被讀又被寫。第一次使用後它就待在快取(或暫存器)裡,之後每次使用都是即時命中——這種隨時間的重用,就是時間區域性。

最近用過的資料很可能很快又被用到,所以把它留在身邊是划算的。

時間區域性講的是隨時間的「重用」,不是位址上的接近。別把它和空間區域性混淆:一個被重用數小時的迴圈計數器有強時間區域性、卻幾乎沒有空間區域性;對一個巨大陣列只掃一遍則有強空間區域性、卻弱時間區域性。

又称
locality in time時間上的區域性