筆記：Memory Locality 隨筆

之前在出考題的時候，有出過一題走訪一個二維陣列，然後有二段範例程式，一個是 row by row 來繞，一個是 column by column 來繞，然後詢問哪一個效能比較好。

幾乎所有的人都回答 row by row 的比較好，因為記憶體是連續的。但每當再多問為什麼是連續的就會比較好時，就開始有些人答不上來。（猜測那時候還沒有 AI，大家都只是先 google 完就直接回答）

假設我們有一個 10x10 的二維陣列（最上、最左 是 header），用肉眼比較好看的表達方式如下：

底下第一段程式碼是 row by row 的走訪方式，從圖表來看就是 1=>2=>3……10=>11=>12……100 的走訪順序。

// row by row
for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
        sum += matrix[i, j];
    }
}

底下第二段程式碼是 column by column 的走訪方式，從圖表來看就是 1=>11=>21……10=>20=>30……100 的走訪順序。

// column by column
for (int j = 0; j < col; j++) {
    for (int i = 0; i < row; i++) {
        sum += matrix[i, j];
    }
}

Spatial Locality (空間局部性)

之前有一篇文章有提到，cpu 從記憶體拿資料的時候，最小單位都會是 cache line，也就是不會只抓所需要的那個 byte。假設 cpu 是要拿一個int32 的資料，他就會拿一個 cache line，通常就是 64 byte，而這個 cache line 裡面就很有機會含蓋等一下馬上就要使用到的資料。

所以當資料是連續的，並且我們的走訪也是連續的（就像上面提到的 row by row），一個 cache line 讀進來，cpu 等一下需要的資料就有機會在同一個 cache line 裡，然後就能直接使用，不需要再從記憶體拿。

再來是現在的硬體都有預判的功能。也就是程式的寫法如果「可預測性」較高，就像上面的範例程式在走訪陣列，CPU 在從記憶體拿資料的時候，就會再多拿一些後面幾個連續位址的資料，把它們先提前往內移。例：L1 or L2 之類的。如果猜得夠準，也就是這些資料的確是 cpu 等一下就要使用的，那 cpu 就不用再從記憶體拿，而是直接從 L1 or L2 拿，速度就會差很多。

column by column 的走訪方式，很容易讓硬體的預判失效，導致 cpu 找不到資料時，它先從 L1/L2 找，結果還是找不到，就只能每次都從記憶體再一路的往裡面搬。而這每一次的往裡面搬，就是它慢的原因。

這也是之前有提過的，程式如果能又準又快的把 cpu 所需要的資料送給它，整個效能都會有很明顯的提升。

Temporal Locality (時間局部性)

大原則就是剛剛才用到的資料，很有機會在等一下會被再用到。所以就先把它盡量留在靠近 cpu 的地方。像是 L1 or L2。

但各家的機制不同，也就是要留哪些、怎麼留，大家都有各自的演算法。但原則不變，一樣都是猜要留哪些資料，猜中了就能讓 cpu 快點拿到資料。

心得

多理解這些，可能不會讓寫出來的程式突然變得非常快，但至少能讓 IT 在 tune 程式或用資料的時候，可以多一些不同的想法，而不是能動就好……

參考資料
筆記：CPU false sharing