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

为啥第一种更快呢？

[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 吞吐 /延迟做到极致能有什么用？用户根本就感受不到那丁点的延迟，除了少部分规模极大的公司有实力去折腾这个，其余大部分场景都是能加机器就加机器扩容了。