[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 缓存主要是用来缓存代码的,数据也是补充. 代码大部分时候是顺序执行的，很多编译优化也是把条件跳转，循环跳转，函数跳转变成顺序代码