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

为啥第一种更快呢？

[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 和并行化还是可以做的。