这是一个创建于 1957 天前的主题，其中的信息可能已经有所发展或是发生改变。
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 为啥第一种更快呢？
 | 1 reus 2020-06-02 20:59:30 +08:00 cpu 会缓存连续的一部分内存，第一种连续操作一片内存，所以快，而第二种跳来跳去，缓存都不命中 |
 | 3 Jirajine 2020-06-02 21:26:05 +08:00 via Android |
 | 4 frozenshadow 2020-06-02 21:26:24 +08:00 via Android  9 |
 | 5 jworg 2020-06-02 21:27:53 +08:00 |
 | 6 /div> qq316107934 2020-06-02 21:35:09 +08:00 @frozenshadow #4 这篇文章太棒了。 不过刚进来第一反应是考虑二维 slice 有一个二次寻址的过程，反复在 slice 间切换会不会在这个过程也有一定的时间浪费？ |
| 7 frozenshadow 2020-06-02 21:42:26 +08:00 via Android 1 @qq316107934 golang 的数组排布方式具体没确认过。如果是 c 的话二维数组在内存其实也是一维的，寻址是用 ptr+(i)*n+j 这样来找的 |
 | 8 ManjusakaL 2020-06-02 21:42:56 +08:00 CPU 缓存问题 |
 | 9 xmge OP |
| 10 xmge OP 吾生也有涯，而知也无涯，以有涯随无涯，需 v 站也。 |
 | 11 CEBBCAT 2020-06-02 22:26:35 +08:00 via Android 粗粗看了一下，是空间局部性吗？记得前几天有人讨论排序算法，快排纸面上看起来没简并快，实际却跑赢了好像就是这个原因。CPU 会把邻近的内存区块一并读入缓存 |
 | 12 seaswalker 2020-06-02 22:27:10 +08:00 via iPhone CPU 缓存是按行来的吧，我记得《深入理解计算机系统》里面有详细讲解… |
 | 13 arjen 2020-06-02 22:28:51 +08:00 via Android cache line |
 | 14 FutherAll 2020-06-02 22:36:01 +08:00 via iPhone c 语言的话，数组是优先行存储，方法一的访问方式是按照存储顺序来访问的，空间局部性好。 可以看 csapp 的存储器层次结构，讲局部性的那部分。 |
 | 15 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 放在前面。 |
 | 16 fighterlyt 2020-06-02 23:07:58 +08:00 @zhs227 你这个回答太逗了，内存虽然是 Random 访问，但不代表 Random 没有成本。就像 CPU 的乱序执行以下，分支预测失败之后成本太高了 |
 | 18 qieqie 2020-06-02 23:17:28 +08:00 via Android 可以再加一问：对于现在主流 x86 cpu，size 取多少的时候两者相差最大？ |
 | 19 tslling 2020-06-02 23:34:50 +08:00 via Android @qieqie 这要看缓存行一行能装多少个元素，就是缓存行和元素各是多大，如果缓存一行能装 n 个元素的话，在 size 是 n 的倍数时，方法一每 n 次有一次不命中，方法二总是不命中。我觉得这种情况下差距是最大的。 这也不是 golang 问题呀，是体系结构相关的。 |
 | 20 aapeli 2020-06-02 23:47:31 +08:00 via iPhone 兄弟们 可以尝试给 golang 官方仓库提 issue 问下 看有没有大牛解答一下 |
 | 21 inframe 2020-06-03 00:05:14 +08:00 内存地址是一维连续分布的，读取时一般 cpu 都使用了各级 SRAM 缓存即 L123Cache, 而真实数据都是来自于 DRAM 系列的内存 现在 size 明显大于了缓存容量，for 循环外侧地址导致缓存命中失效，每次都到主存里去载入，自然慢了。 参考计算机体系结构 |
 | 22 kljsandjb 2020-06-03 00:18:48 +08:00 via iPhone 局部性原理 了解一下存储器体系就懂了哦 |
 | 23 wangyzj 2020-06-03 00:19:56 +08:00 CPU 缓存问题？ 厉害了 我还以为是切片不固定数据结构导致连续内存段不断拷贝移动和增加的问题 |
 | 25 lewinlan 2020-06-03 00:37:28 +08:00 via Android 解答肯定就是缓存的时空连续性问题。看操作系统的书就懂了。 不过大胆猜测一下可能也有编译优化的问题。 |
 | 27 lithbitren 2020-06-03 00:44:15 +08:00 不止 golang 吧，我机子上 cpython 的比值大约是 1.8，pypy 大约是 5.1，go 大约是 3.2，顺便验证发现，pypy 除了单层死循环，竟然都比 go 快。 |
 | 29 Vegetable 2020-06-03 00:46:19 +08:00 @lithbitren #27 jit 嘛，这种代码用 pypy 效果非常明显。 |
 | 30 lostpg 2020-06-03 01:23:16 +08:00 via Android 循环向量化一下可能能更快一些（大概 |
 | 31 trn4 2020-06-03 02:16:26 +08:00 CSAPP 第六章，再把配套的课后练习 cache lab 做了，你就懂了 |
| 32 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 还是太黑箱了。 |
 | 33 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))) } } 这样相当于将循环执行次数缩减到八分之一 |
 | 34 chronusshi 2020-06-03 06:31:08 +08:00 via iPhone 现在大部分语言存储方式都是 row major order，第一种方法 cache miss 就会少很多。你要是写 Fortran 那种用 column major order 的远古语言，第二种就会快。 |
 | 36 ljpCN 2020-06-03 08:49:21 +08:00 via Android 以后有人问本科的计算机理论课有什么用，把这个帖子丢给他就好了 |
 | 37 yingxiangyu 2020-06-03 08:53:04 +08:00 via iPhone 这不是深入了解计算机系统封面那个问题吗，一般操作系统内存管理也会讲到 |
 | 38 qwertyegg 2020-06-03 09:04:58 +08:00 我认为原因在于第一种办法相当于在[]int 上找到头指针 pi，然后 pi++遍历 第二种办法是每次寻找[]int 的 pi，然后寻找 pi+j 很显然第一种更效率 |
 | 39 sagaxu 2020-06-03 09:24:23 +08:00 via Android 科班非科班区别的一个典型例子。 csapp 书很厚，但科班专业教材至少有 3 个 csapp 那么厚。 |
 | 40 lewis89 2020-06-03 09:44:46 +08:00 @ljpCN #36 然后有什么卵用？我算是读完了 CSAPP，然后发现大部分场景根本没什么卵用，市面上大部分面试无非是程序员自己在卷自己，真正需要优化根本就不存在互联网这个场景，你就算把 GC 吞吐 /延迟做到极致能有什么用？用户根本就感受不到那丁点的延迟，除了少部分规模极大的公司有实力去折腾这个，其余大部分场景都是能加机器就加机器扩容了。 |
| 41 lewis89 2020-06-03 09:51:25 +08:00 题主这个明显就是根本不了解现代计算机的 存储结构体系 实际上细化分 应该是 L1 L2 L3 Cache 这几 Cache 还要根据 CPU 的设计结构来区分 有些是设计成多核心共享的 有的是设计成单个核心的独占的，独占的缓存在 多线程编程中 又要涉及到 MESI 协议的缓存同步 然后才是主存，主存还要分一致性架构跟非一致性架构（例如 AMD 新款就是非一致性内存架构）一致性架构是所有核心都在一个总线上竞争，非一致性架构是每个核心分管自己的主存，如果一个核心要去访问另外一个核心的分管内存就需要通过通讯总线去进行核心通信 主存之后才是 外部低速设备 低速设备又分为 快速随机读写设备 以及 高速连续读写设备 分别对应 SSD 跟 HDD 两种存储设备 |
| 42 lewis89 2020-06-03 09:52:42 +08:00 现代计算机的存储体系结构是一个非常复杂跟细分的东西 连 SSD 里面都有算法 去计算每个块的擦写次数 |
 | 43 mapleray 2020-06-03 10:09:28 +08:00 |
 | 46 DelayNoMay 2020-06-03 10:54:14 +08:00 @zhs227 你真是骚 |
 | 49 yutou527 2020-06-03 11:19:37 +08:00 所以这种问题 编译器是不是可以做到帮忙优化？ |
 | 50 PonysDad 2020-06-03 11:23:45 +08:00 @lewis89 说得在理。如果我们学这些专业课只是为了在编码是做一下这些优化，那真的完全是鸡肋。但是其中的精髓应该是解决这些问题方式，这个是我们应该去领悟到的。好比缺页导致系统颠簸，阿姆达尔定律等等，这些知识点对我们排查故障或者大型系统优化时时很有用的。 |
 | 51 asAnotherJack 2020-06-03 12:01:54 +08:00 非科班，还真遇到过这个面试题，当时虽然蒙对了，回答原因的时候也只是猜测和磁盘按页加载可能类似 |
| 52 lewis89 2020-06-03 12:51:54 +08:00 @yutou527 #49 不可以，编译器无法预测代码运行时的行为，强行预测又太勉强，这种只能程序员自己提升对计算机系统的理解。 |
 | 53 tt67wq 2020-06-03 12:53:07 +08:00 谷歌下 cacheline |
| 54 lewis89 2020-06-03 12:55:54 +08:00 @tt67wq #53 关键还是要理解一些设计的思想 例如 计算机经常提到的一个 谚语， 如果一个内存区域的数据会被用到，那么他旁边的数据可能很快就会被用到 |
 | 55 GaoYL 2020-06-03 13:43:24 +08:00 我记得《深入理解计算机系统》里面有非常详细讲解，虽然我也不太懂。 |
 | 57 bowser1701 2020-06-03 14:01:30 +08:00 via iPhone @xmge csapp 第三章讲到过 |
 | 58 Kilerd 2020-06-03 14:15:40 +08:00 CSAPP 里面讲得很清楚。 |
 | 59 xhxhx 2020-06-03 14:26:29 +08:00 所以其实是 CPU 读取缓存逻辑导致的快慢，不是 Golang 独有，在其他语言上也存在嘛 |
 | 60 msg7086 2020-06-03 14:29:33 +08:00 |
| 61 qq316107934 2020-06-03 14:33:16 +08:00 @frozenshadow #7 这个在 golang 里体现的是 array，slice 是变长的，所以我才怀疑。抱歉你给我的回复 v 站没有提醒，今天帖子被顶上来我才看到。 |
 | 63 Huelse 2020-06-03 16:41:18 +08:00 我记得大学操作系统课上的时候教过 |
Select Language