我们用 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。