計算機基礎(chǔ): 什么樣的代碼能讓CPU運行的更快踊赠？
眾所周知，程序在計算機里運行時每庆，程序的指令和數(shù)據(jù)存儲在 內(nèi)存 中筐带。當程序進程獲得CPU時間片時，CPU將會從 內(nèi)存 中"恢復(fù)執(zhí)行現(xiàn)場"缤灵，然后繼續(xù)循環(huán)執(zhí)行程序的指令知道程序進程結(jié)束伦籍。
CPU的執(zhí)行速度 與 內(nèi)存的讀寫速度 不在同一個層級蓝晒，通常一次內(nèi)存訪問需要 200~300 個時鐘周期，而CPU一個時鐘周期可以執(zhí)行 3~9 條指令帖鸦。而一個程序中芝薇，訪問內(nèi)存的指令通常占25%左右，如果不能以某種方式降低訪問內(nèi)存時延的話作儿，那對CPU執(zhí)行來說就是個災(zāi)難剩燥！
因此為了盡可能降低內(nèi)存與CPU之間讀寫差異，CPU內(nèi)部加入了 CPU Cache立倍，也被稱為高速緩存灭红。它體積小但訪問速度極快，根據(jù)數(shù)據(jù)局部性原則口注，常用的數(shù)據(jù)可以復(fù)制到 CPU Cache 從減少CPU對內(nèi)存的訪問变擒。
CPU Cache 分為3層：L1, L2, L3。其中 L1 高速緩存的訪問速度幾乎與寄存器一樣快寝志，只需要 2~4 個時鐘周期娇斑。L2 則為 10~20 個時鐘周期，L3 則為 20~60 個時鐘周期材部。
我們的代碼只有讓 CPU Cache 更多命中緩存毫缆，減少CPU直接從內(nèi)存中讀取數(shù)據(jù)，這樣才能讓CPU跑得更快乐导！
-
CPU Cache是如何存儲數(shù)據(jù)的苦丁？
CPU Cache是由很多個連續(xù)的內(nèi)存塊組成，每個內(nèi)存塊被稱為Cache Line物臂。Cache Line的數(shù)量是限定的旺拉，例如在一個64KB的CPU Cache中， 如果Cache Line的大小為64字節(jié), 那么就只有 1024 條Cache Line棵磷。常見的
CPU Line大小為32蛾狗、64和128字節(jié)。這是一個經(jīng)驗值仪媒，如果CPU Line過大沉桌，局部性空間也越大，但是對應(yīng)緩存行數(shù)就會越少算吩。
-
CPU Line是如何被替換的留凭？
通常有
LRU 最近最少使用策略和隨機替換策略兩種。當CPU訪問新數(shù)據(jù)且未命中
CPU Cache時赌莺，那么則需要選擇一條CPU Line來被新數(shù)據(jù)替換
-
如何查看
CPU Cache和CPU Line的大斜馈？
# 查看 L1 Cache 「數(shù)據(jù)」緩存的容量大小 cat /sys/devices/system/cpu/cpu0/cache/index0/size # 查看 L1 Cache 「指令」緩存的容量大小 cat /sys/devices/system/cpu/cpu0/cache/index1/size # 查看 L2 Cache 的容量大小 cat /sys/devices/system/cpu/cpu0/cache/index1/size # 查看 L3 Cache 的容量大小 cat /sys/devices/system/cpu/cpu0/cache/index1/size # 查看 Cache Line 的容量大小 (單位：字節(jié)) cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
-
什么樣的代碼能讓
CPU Cache更頻繁的命中緩存艘狭？
我們使用go benchmark測試以下代碼:
func arrayTravelIj(n int) { arr := make([][]int, n) for i, _ := range arr { arr[i] = make([]int, n) } for i := 0; i < n; i++ { for j := 0; j < n; j++ { arr[i][j] = 0 } } } func arrayTravelJi(n int) { arr := make([][]int, n) for i, _ := range arr { arr[i] = make([]int, n) } for i := 0; i < n; i++ { for j := 0; j < n; j++ { arr[j][i] = 0 } } } const N = 128 func BenchmarkArrayTravelIj(b *testing.B) { for i := 0; i < b.N; i++ { arrayTravelIj(N) } } func BenchmarkArrayTravelJi(b *testing.B) { for i := 0; i < b.N; i++ { arrayTravelJi(N) } } # 執(zhí)行: go test -bench=^BenchmarkArrayTravel -benchmem . # 結(jié)果: # cpu: Intel(R) Xeon(R) Gold 6278C CPU @ 2.60GHz # BenchmarkArrayTravelIj-8 33397 35933 ns/op 134144 B/op 129 allocs/op # BenchmarkArrayTravelJi-8 18099 66487 ns/op 134144 B/op 129 allocs/op # PASS可以看到，明明
內(nèi)存分配次數(shù)和運行時的內(nèi)存大小是一樣的, 但是BenchmarkArrayTravelIj比BenchmarkArrayTravelJi快了近一倍！原因就是
BenchmarkArrayTravelIj訪問數(shù)據(jù)順序是連續(xù)的巢音，而BenchmarkArrayTravelJi訪問數(shù)據(jù)順序是跳躍的遵倦。假如
N=2，那么arr在內(nèi)存中的存儲順序為arr[0][0],arr[0][1],arr[1][0],arr[1][1]官撼。當N越來越大時梧躺，由BenchmarkArrayTravelJi訪問數(shù)據(jù)順序是跳躍的，那么CPU Cache命中率則會越來越低傲绣！我的測試機器
L1大小是32K掠哥，Cache Line大小是64字節(jié)，那么意味著單個Cache Line能保存的int元素的數(shù)量是8個秃诵，整個L1 CPU Cache能保存的Cache Line條數(shù)是 512條续搀。換算一下就是整個
L1 CPU Cache能保存的int元素是4096個，所以當N超過64時菠净，隨著N增大禁舷，兩個函數(shù)的執(zhí)行效率也會被越拉越大。當然毅往，64這個數(shù)字并不嚴謹牵咙，因為除了
CPU Cache不僅只有L1, 還有L2,L3, 而且不同CPU的底層還會有各種硬件的加速內(nèi)存預(yù)取策略
