[TOC] 我們用 Go 寫兩個遍歷兩層 slice 的算法。 ~~~ var items = make([][]int32, 1000) func init() { for i := 0; i < 1000; i++ { items[i] = make([]int32, 1000) for j := 0; j < 1000; j++ { items[i][j] = rand.Int31n(2) } } } // 橫向遍歷 func sumRows() int { var sum = 0 for i := 0; i < 1000; i++ { for j := 0; j < 1000; j++ { sum += int(items[i][j]) } } return sum } // 縱向遍歷 func sumCols() int { var sum = 0 for i := 0; i < 1000; i++ { for j := 0; j < 1000; j++ { sum += int(items[j][i]) } } return sum } ~~~ sumRows() 函數橫向遍歷數組，sumCols() 函數縱向遍歷數組，每個數組計算的次數都是一樣的，所以按道理說兩者的消耗時間也是一樣的。 我們寫兩個基準測試 ~~~ func BenchmarkRows(b *testing.B) { for i := 0; i < b.N; i++ { sumRows() } } func BenchmarkCols(b *testing.B) { for i := 0; i < b.N; i++ { sumCols() } } ~~~ 跑基準測試 ~~~ > $ go test -bench=.s -run=^1 -benchmem goos: darwin goarch: amd64 pkg: github.com/yushuailiu/go-algorithm/golang BenchmarkRows-4 1000 1210319 ns/op 0 B/op 0 allocs/op BenchmarkCols-4 100 13451343 ns/op 0 B/op 0 allocs/op PASS ok github.com/yushuailiu/go-algorithm/golang 2.746s ~~~ 我們可以看到縱向遍歷的時間是橫向遍歷的10幾倍。 CPU高速緩存 CPU是執行所有的運算和程序，內存是存放數據和代碼，當CPU 需要數據的時候會去內存取，CPU 做了一個緩存架構，當 CPU 需要數據的時候需要先從緩存中取，取不到再去內存取。  CPU 高速緩存分為3層L1、L2、L3，L1 最快最小 L3 最大最慢。 各級緩存大小及速度 | CPU訪問 | 消耗的CPU時鐘周期 | 大約需要的時間 | 大小 | | --- | --- | --- | --- | | 主存 | | 約60~80ns | | | QPI總線傳輸 | | 約20ns | | | L3 cache | 約40-45 cycles | 約15ns | 3MB | | L2 cache | 約10 cycles | 約3ns | 256KB | | L1 cache | 約3-4 cycles | 約1ns | 32KB | | 寄存器 | 1cycles | | | 根據表格可以看出如果命中L1 cache那么會比到內存取數據快近兩個數量級。 # 緩存行 高速緩存是由很多 Cache Line 組成的。Cache Line 是 cache 和 RAM（內存）最小數據交換單元，一般大小為 64byte。當 CPU 把內存中的數據載入 cache 時，會把臨近的 64byte 的數據一同寫入 Cache line（空間局限性原則：臨近的數據將來被訪問的可能性很大）。 # 揭秘 大家看了上面段的說明應該有所明白了，是的 橫向遍歷為什么會比縱向遍歷快就是因為橫向遍歷會大量中高速緩存，因為我們知道 Go 中 slice 底層是數組，而數組所有數據是類型相同大小相同連續的內存空間，所以當我們依次訪問一個 slice 的各個元素的時候就會中Cache Line，因為當我們訪問位置為 0 的元素的時候，包括該元素在內以及往后的 64 byte的數據都會載入 Cache Line。 **第一層先訪問,那就把第一層先載入緩存** Cpu 緩存主要是用來緩存代碼的,數據也是補充. 代碼大部分時候是順序執行的，很多編譯優化也是把條件跳轉，循環跳轉，函數跳轉變成順序代碼