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 问下 看有没有大牛解答一下

[inframe]

内存地址是一维连续分布的，读取时一般 cpu 都使用了各级 SRAM 缓存即 L123Cache, 而真实数据都是来自于 DRAM 系列的内存

现在 size 明显大于了缓存容量，for 循环外侧地址导致缓存命中失效，每次都到主存里去载入，自然慢了。

参考计算机体系结构

[kljsandjb]

局部性原理 了解一下存储器体系就懂了哦

[wangyzj]

CPU 缓存问题？
厉害了
我还以为是切片不固定数据结构导致连续内存段不断拷贝移动和增加的问题

[zhs227]

@FutherAll 惭愧，没认真审题。我以为方法 1 和 2 在内存分配上有区别

[lewinlan]

解答肯定就是缓存的时空连续性问题。看操作系统的书就懂了。
不过大胆猜测一下可能也有编译优化的问题。

[CEBBCAT]

@aapeli 这个问题似乎还上不了官方仓库 issue 的台面吧😹

[lithbitren]

不止 golang 吧，我机子上 cpython 的比值大约是 1.8，pypy 大约是 5.1，go 大约是 3.2，顺便验证发现，pypy 除了单层死循环，竟然都比 go 快。

[Vegetable]

@zhs227 #15 搞笑呢哥们，人家问的就是为什么 ij 比 ji 快，你换回来问题都没了

[Vegetable]

@lithbitren #27 jit 嘛，这种代码用 pypy 效果非常明显。

[lostpg]

循环向量化一下可能能更快一些（大概

[xiadong1994]

CSAPP 第六章，再把配套的课后练习 cache lab 做了，你就懂了

[lithbitren]

我用 g++编译循环 vector，cpp 的时间基本和 go 一致，20000*20000 的行序循环都是 1.5 秒左右，pypy 的行序则是 0.9 秒，顺便 cpp 的比值为 4.1，即 cpp 的列序循环时行序循环的 4.1 倍。cpython 的行序循环 19 秒，列序 33 秒。
不过 pypy 比 cpp 快怎么都不科学啊，不过 pypy 是扔到子进程同时运行的，go 是放进 goruntine，cpp 放进了 thread，cpp 不放 thread 也就是 1.29 秒，还是没 pypy 快，懵圈了。
循环计数十亿，cpp 稳定 0.13 秒，go 也差不多，但 pypy 就得 0.3 秒，cpython6 秒，感觉 jit 还是太黑箱了。

[CismonX]

对于连续的内存的操作，编译器还可以借助 SIMD 指令进行优化

比如例子里面的方法一，就可以像如下这样做（伪代码）：

a := _mm512_set_epi64(0, 1, 2, 3, 4, 5, 6, 7)
for i := 0; i < size; i++ {
for j := 0; j < size; j+=8 {
_mm512_store_epi64(matrix[i][j], _mm512_add_epi64(a, _mm512_set1_epi64(i + j)))
}
}

这样相当于将循环执行次数缩减到八分之一

[chronusshi]

现在大部分语言存储方式都是 row major order，第一种方法 cache miss 就会少很多。你要是写 Fortran 那种用 column major order 的远古语言，第二种就会快。

[hankai17]

pre read

[ljpCN]

以后有人问本科的计算机理论课有什么用，把这个帖子丢给他就好了

[yingxiangyu]

这不是深入了解计算机系统封面那个问题吗，一般操作系统内存管理也会讲到

[qwertyegg]

我认为原因在于第一种办法相当于在[]int 上找到头指针 pi，然后 pi++遍历

第二种办法是每次寻找[]int 的 pi，然后寻找 pi+j

很显然第一种更效率

[sagaxu]

科班非科班区别的一个典型例子。

csapp 书很厚，但科班专业教材至少有 3 个 csapp 那么厚。

[lewis89]

@ljpCN #36 然后有什么卵用？我算是读完了 CSAPP，然后发现大部分场景根本没什么卵用，市面上大部分面试无非是程序员自己在卷自己，真正需要优化根本就不存在互联网这个场景，你就算把 GC 吞吐 /延迟做到极致能有什么用？用户根本就感受不到那丁点的延迟，除了少部分规模极大的公司有实力去折腾这个，其余大部分场景都是能加机器就加机器扩容了。

[lewis89]

题主这个明显就是根本不了解现代计算机的 存储结构体系
实际上细化分 应该是

L1 L2 L3 Cache 这几 Cache 还要根据 CPU 的设计结构来区分 有些是设计成多核心共享的 有的是设计成单个核心的独占的，独占的缓存在 多线程编程中 又要涉及到 MESI 协议的缓存同步

然后才是主存，主存还要分一致性架构跟非一致性架构（例如 AMD 新款就是非一致性内存架构）一致性架构是所有核心都在一个总线上竞争，非一致性架构是每个核心分管自己的主存，如果一个核心要去访问另外一个核心的分管内存就需要通过通讯总线去进行核心通信

主存之后才是 外部低速设备 低速设备又分为 快速随机读写设备 以及 高速连续读写设备 分别对应 SSD 跟 HDD 两种存储设备

[lewis89]

现代计算机的存储体系结构是一个非常复杂跟细分的东西 连 SSD 里面都有算法 去计算每个块的擦写次数

[mapleray]

https://medium.com/@teivah/go-and-cpu-caches-af5d32cc5592

[limboMu]

@sagaxu 可以说是非常真实了，我本科的数据结构科班跟 csapp 一样厚

[limboMu]

@limboMu 科班 -> 课本

[DelayNoMay]

@zhs227 你真是骚

[reus]

@aapeli issue 是提 bug 之类用的，不是给你解答问题的

[no1xsyzy]

@zhs227 #15 方法一和方法二的差别不就是 i j 顺序吗？其实就是问：为什么变化快的数字应该做低维下标？

[yutou527]

所以这种问题 编译器是不是可以做到帮忙优化？

[PonysDad]

@lewis89 说得在理。如果我们学这些专业课只是为了在编码是做一下这些优化，那真的完全是鸡肋。但是其中的精髓应该是解决这些问题方式，这个是我们应该去领悟到的。好比缺页导致系统颠簸，阿姆达尔定律等等，这些知识点对我们排查故障或者大型系统优化时时很有用的。

[asAnotherJack]

非科班，还真遇到过这个面试题，当时虽然蒙对了，回答原因的时候也只是猜测和磁盘按页加载可能类似

[lewis89]

@yutou527 #49 不可以，编译器无法预测代码运行时的行为，强行预测又太勉强，这种只能程序员自己提升对计算机系统的理解。

[tt67wq]

谷歌下 cacheline

[lewis89]

@tt67wq #53 关键还是要理解一些设计的思想 例如 计算机经常提到的一个 谚语， 如果一个内存区域的数据会被用到，那么他旁边的数据可能很快就会被用到

[GaoYL]

我记得《深入理解计算机系统》里面有非常详细讲解，虽然我也不太懂。

[daryl]

@xmge csapp

[bowser1701]

@xmge csapp 第三章讲到过

[Kilerd]

CSAPP 里面讲得很清楚。

[xhxhx]

所以其实是 CPU 读取缓存逻辑导致的快慢，不是 Golang 独有，在其他语言上也存在嘛

[msg7086]

@yutou527 @lewis89
也不算完全不行吧，编译器也可以静态分析行为然后重写代码的。
我之前有些代码写完以后，用 clang 编译完发现出来的汇编和我写的完全不是一码事，而且性能还快得多。
就算没有这种重写级别的优化，基本的 unrolling 和并行化还是可以做的。

[qq316107934]

@frozenshadow #7 这个在 golang 里体现的是 array，slice 是变长的，所以我才怀疑。抱歉你给我的回复 v 站没有提醒，今天帖子被顶上来我才看到。

[lewis89]

@msg7086 我说的是运行时 你没法预测 内存访问是否为顺序访问..

[Huelse]

我记得大学操作系统课上的时候教过