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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1621 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

为啥第一种更快呢？

63 条回复 • 2020-06-03 16:41:18 +08:00

reus

2020-06-02 20:59:30 +08:00

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

xmge

2020-06-02 21:18:03 +08:00

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

Jirajine

2020-06-02 21:26:05 +08:00 via Android

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

frozenshadow

2020-06-02 21:26:24 +08:00 via Android

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

jworg

2020-06-02 21:27:53 +08:00

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

qq316107934

2020-06-02 21:35:09 +08:00

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

frozenshadow

2020-06-02 21:42:26 +08:00 via Android

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

ManjusakaL

2020-06-02 21:42:56 +08:00

CPU 缓存问题

xmge

2020-06-02 21:50:41 +08:00

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

xmge

2020-06-02 22:06:34 +08:00

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

CEBBCAT

2020-06-02 22:26:35 +08:00 via Android

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

seaswalker

2020-06-02 22:27:10 +08:00 via iPhone

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

arjen

2020-06-02 22:28:51 +08:00 via Android

cache line

FutherAll

2020-06-02 22:36:01 +08:00 via iPhone

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

zhs227

2020-06-02 23:01:07 +08:00

我并不觉得这两种方式存在本质的区别，好奇心让我试了一下，发现上面答案提的并不是最主要的因素，是代码写的有问题，只需要把方法 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

2020-06-02 23:07:58 +08:00

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

FutherAll

2020-06-02 23:13:07 +08:00 via iPhone

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

qieqie

2020-06-02 23:17:28 +08:00 via Android

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

tslling

2020-06-02 23:34:50 +08:00 via Android

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

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

aapeli

2020-06-02 23:47:31 +08:00 via iPhone

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

inframe

2020-06-03 00:05:14 +08:00

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

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

参考计算机体系结构

kljsandjb

2020-06-03 00:18:48 +08:00 via iPhone

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

wangyzj

2020-06-03 00:19:56 +08:00

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

zhs227

2020-06-03 00:33:04 +08:00

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

lewinlan

2020-06-03 00:37:28 +08:00 via Android

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

CEBBCAT

2020-06-03 00:39:44 +08:00 via Android

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

lithbitren

2020-06-03 00:44:15 +08:00

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

Vegetable

2020-06-03 00:44:59 +08:00

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

Vegetable

2020-06-03 00:46:19 +08:00

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

lostpg

2020-06-03 01:23:16 +08:00 via Android

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

xiadong1994

2020-06-03 02:16:26 +08:00

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

lithbitren

2020-06-03 02:26:38 +08:00

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

2020-06-03 02:27:10 +08:00

对于连续的内存的操作，编译器还可以借助 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

2020-06-03 06:31:08 +08:00 via iPhone

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

hankai17

2020-06-03 07:29:47 +08:00 via Android

pre read

ljpCN

2020-06-03 08:49:21 +08:00 via Android

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

yingxiangyu

2020-06-03 08:53:04 +08:00 via iPhone

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

qwertyegg

2020-06-03 09:04:58 +08:00

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

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

很显然第一种更效率

sagaxu

2020-06-03 09:24:23 +08:00 via Android

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

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

lewis89

2020-06-03 09:44:46 +08:00

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

lewis89

2020-06-03 09:51:25 +08:00

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

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

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

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

lewis89

2020-06-03 09:52:42 +08:00

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