golang 面试题之 为什么这种更快呢?

[xmge]

package main

import (
    "fmt"
    "time"
)

func main() {
    size := 20000
    matrix1 := make([][]int, size)
    for i := 0; i < size; i++ {
        matrix1[i] = make([]int, size)
    }

    start1 := time.Now()
    // 方法 1
    for i := 0; i < size; i++ {
        for j := 0; j < size; j++ {
            matrix1[i][j] = i + j
        }
    }

    fmt.Println(time.Since(start1))

    matrix2 := make([][]int, size)
    for i := 0; i < size; i++ {
        matrix2[i] = make([]int, size)
    }

    // 方法 2
    start2 := time.Now()
    for i := 0; i < size; i++ {
        for j := 0; j < size; j++ {
            matrix2[j][i] = i + j
        }
    }
    fmt.Println(time.Since(start2))
}

// 1.1769527s
// 8.5584257s

为啥第一种更快呢？

[reus]

cpu 会缓存连续的一部分内存，第一种连续操作一片内存，所以快，而第二种跳来跳去，缓存都不命中

[xmge]

@reus 这方面的书面解释到哪里去看呢?

[Jirajine]

https://en.m.wikipedia.org/wiki/Cache_prefetching

[frozenshadow]

@xmge https://mp.weixin.qq.com/s/viQp36FeMZSqUoFy3VrBNw

[jworg]

https://www.cnblogs.com/jokerjason/p/10711022.html

[qq316107934]

@frozenshadow #4 这篇文章太棒了。
不过刚进来第一反应是考虑二维 slice 有一个二次寻址的过程，反复在 slice 间切换会不会在这个过程也有一定的时间浪费？

[frozenshadow]

@qq316107934 golang 的数组排布方式具体没确认过。如果是 c 的话二维数组在内存其实也是一维的，寻址是用 ptr+(i)*n+j 这样来找的

[ManjusakaL]

CPU 缓存问题

[xmge]

@Jirajine @ManjusakaL @frozenshadow @qq316107934 @reus 感谢各位大佬...

[xmge]

吾生也有涯，而知也无涯，以有涯随无涯，需 v 站也。

[CEBBCAT]

粗粗看了一下，是空间局部性吗？记得前几天有人讨论排序算法，快排纸面上看起来没简并快，实际却跑赢了好像就是这个原因。CPU 会把邻近的内存区块一并读入缓存

[seaswalker]

CPU 缓存是按行来的吧，我记得《深入理解计算机系统》里面有详细讲解…

[arjen]

cache line

[FutherAll]

c 语言的话，数组是优先行存储，方法一的访问方式是按照存储顺序来访问的，空间局部性好。
可以看 csapp 的存储器层次结构，讲局部性的那部分。

[zhs227]

我并不觉得这两种方式存在本质的区别， 好奇心让我试了一下，发现上面答案提的并不是最主要的因素，是代码写的有问题，只需要把方法 2 中的`matrix2[j][i]`中的 i 和 j 对换一下，能跑到比方法一更快。

没改之前：
go run test.go
2.103482788s
8.669886344s

改之后：
1.69951775s
1.543304649s

尝试把方法 1 中的 i 和 j 位置也换一下:
go run test.go
9.274899793s
1.484341903s

结论：变化快的数字应该做低维下标，如果 i 是外层循环变量，应该把 i 放在前面。

[fighterlyt]

@zhs227 你这个回答太逗了，内存虽然是 Random 访问，但不代表 Random 没有成本。就像 CPU 的乱序执行以下，分支预测失败之后成本太高了

[FutherAll]

@zhs227 ij 换位置就和方法一一样了，你不是认真的吧😂

[qieqie]

可以再加一问：对于现在主流 x86 cpu，size 取多少的时候两者相差最大？

[tslling]

@qieqie 这要看缓存行一行能装多少个元素，就是缓存行和元素各是多大，如果缓存一行能装 n 个元素的话，在 size 是 n 的倍数时，方法一每 n 次有一次不命中，方法二总是不命中。我觉得这种情况下差距是最大的。

这也不是 golang 问题呀，是体系结构相关的。

[aapeli]

兄弟们 可以尝试给 golang 官方仓库提 issue 问下 看有没有大牛解答一下