关于golang:为什么这段代码对CPU不友好

问题起源

问题出自再看 bilibili 视频时候，（地址 https://www.bilibili.com/video/BV12p4y1W7Dz），发现一道对于 CPU 问题从未思考过，所以就产生了趣味，具体问题是这样的：

上面两段代码 fnc1 和 fnc2(这里我给简化了，成果都一样)，哪段的执行速度更快：

const N = 2000
var arr2D [N][N]int

func fnc1()  {
  for i := 0; i < N; i++ {
    for j := 0; j < N; j++ {arr2D[i][j] = 0
    }
  }
}

func fnc2()  {
  for i := 0; i < N; i++ {
    for j := 0; j < N; j++ {arr2D[j][i] = 0
    }
  }
}

最终答案是 fnc1 要比 fnc2 快，这里我把他俩合并用一段代码调试下：

const N = 2000

func main() {
  // 为了避免专用一个二维数组造成影响，这里用两个二维数组，每个办法别离用一个
  var arr2D1 [N][N]int
  var arr2D2 [N][N]int
  // 模仿 fnc1
  start1 := time.Now().UnixNano()
  for i := 0; i < N; i++ {
    for j := 0; j < N; j++ {arr2D1[i][j] = 0
    }
  }
  ct1 := time.Now().UnixNano() - start1
  // 模仿 fnc2
  start2 := time.Now().UnixNano()
  for i := 0; i < N; i++ {
    for j := 0; j < N; j++ {arr2D2[j][i] = 0
    }
  }
  ct2 := time.Now().UnixNano() - start2
  // 输入工夫
  fmt.Println("fnc1 time :",ct1)
  fmt.Println("fnc2 time :",ct2)
}

输入后果绝大多数 fnc1 的工夫要小于 fnc2 的工夫，(偶然偶然会呈现 fnc1 大于 fnc2，猜想起因是过后 CPU 忙于其余的过程)

$ go run main.go
fnc1 time : 3499675
fnc2 time : 10823762
$ go run main.go
fnc1 time : 3475027
fnc2 time : 307537210
......

过后纳闷这种景象是怎么造成的，毕竟两个办法的工夫复杂度都是雷同的。这就引出了明天的主题，CPU 缓存。

CPU 架构介绍

咱们在个别买电脑时候都是会先理解下内存 (RAM) 多大等信息，咱们还晓得 Redis 为什么快起因之一是基于内存的数据库。好像 CPU 就是在间接操作内存，内存就是最快的货色。然而对于比内存，还有比他快得多的存储介质，CPU 高速缓存。

首先让咱们看下图计算机存储器的层次结构，图片取自《深刻了解计算机系统》。

所有的古代计算机都应用了这种存储构造，越凑近下面，造价越高，容量越小。古代计算机中，最快的就是寄存器存取了，寄存器间隔 CPU 外围最近，然而可存储数据起码，往往用来放一些函数参数；接下来别离是 L1-L3 三级缓存，也是明天的重点，他们作为 CPU 的缓存充当了 CPU 与主存之间的垫片；而后就是最相熟的主存，就是咱们常说的内存；再次就是磁盘和近程文件存储系统了。

接下来把视角拉近，次要看下 CPU 的存储架构，上面是一个通用的双核 CPU 架构图：

简要介绍下各个 CPU 部件：

管制单元(CU)：是 CPU 的指挥核心，他依据用户编译好的程序，从存储器中取出各种指令，用来指挥 CPU 工作

计算单元(ALU)：用于执行算术运算与逻辑运算，全副操作服从由管制单元指挥

寄存器：紧挨着管制单元与计算单元，速度是最快的，然而容量也是最小，32 位 CPU 大多数寄存器能够存储 4 个字节,64 位大多数为 8 字节。

L1-Cache：每个 CPU 都有一个 L1-Cache，实际上 L1-Cache 又分为两个，一个指令缓存(i-cache)，一个数据缓存(d-cache)，这是因为两个缓存的更新策略不同，所以离开，通常 L1-Cache 大小在几十 Kb 到几百 Kb 之间，Linux 下能够通过上面命令获取，一次拜访须要须要 2~4 个时钟周期。

# 数据缓存 d-cache
$ cat /sys/devices/system/cpu/cpu0/cache/index0/size
# 指令缓存 i-cache
$ cat /sys/devices/system/cpu/cpu0/cache/index1/size

L2-Cache：每个 CPU 也有一个 L2-Cache，大小要大于 L1-Cache，因为地位比 L1-Cache 间隔 CPU 外围更远，所以速度稍慢于 L1-Cache，须要10~20 个时钟周期。

$ cat /sys/devices/system/cpu/cpu0/cache/index2/size

L3-Cache：L3-Cache 是被所有 CPU 共享的，大小也更大，访问速度也稍慢与 L2-cache，须要20~60 个时钟周期。

$ cat /sys/devices/system/cpu/cpu0/cache/index3/size

CPU 取数据过程

当 CPU 须要读取某些数据时候，如果寄存器中有，就间接用寄存器数据；如果没有，就去 L1-cache 中读取，L1-cache 中没有，就去 L2-cache，L2 没有查问 L3，L3 没有去主存获取，获取到后顺次填充三级缓存。

CPU 缓存上的数据就是主存上的数据，读取数据的规定并不是依照单个元素来读取，它是一块一块读取数据的，比方当我取出一个很小的数据时，他会把所在的那块内存块加载到缓存上。这样，当咱们拜访这个数据相邻的数据时候，也就能够间接通过 CPU Cache 来获取了，这样大小的内存块被称为Cache Line。在 Linux 上能够通过上面命令看到：

# cpu0 的 L1-d-cache 的 cache Line，我的机器是 64 字节
$ cat /sys/devices/system/cpu/cpu0/cache/index1/coherency_line_size
64

案例联合

咱们回到下面的案例，咱们首先定义了二维数组，在内存中的存储的间断形式是这样的：

var arr [2][2]int

在内存中是间断散布的，程序是 0_0, 0_1, 1_0, 1_1，每个元素占用 8 个字节

咱们能够通过取地址得出这个论断

func main() {var arr [2][2]int
  fmt.Println(uintptr(unsafe.Pointer(&arr[0][0])))
  fmt.Println(uintptr(unsafe.Pointer(&arr[0][1])))
  fmt.Println(uintptr(unsafe.Pointer(&arr[1][0])))
  fmt.Println(uintptr(unsafe.Pointer(&arr[1][1])))
}
-----------
// 能够看到内存地址顺次加 8
824634298096
824634298104
824634298112
824634298120

所以，对应到咱们的案例，当咱们应用 i_j 形式赋值时候，取出第一个元素 0_0 的时候，就会从内存中取出一块 64 字节的 Cache Line，也就是取出了 0_0 到 0_7 放到了 CPU 缓存中，当下次迭代到 0_1 时候，就会间接应用 CPU 缓存中的数据，这充分利用了 CPU 缓存。

const N = 2000
var arr2D [N][N]int

func fnc1() {
  for i := 0; i < N; i++ {
    for j := 0; j < N; j++ {arr2D[i][j] = 0
    }
  }
}

然而当应用 j_i 形式赋值时候，第二次迭代要取用 1_0 的数据，这时候 CPU 要从新去主存加载数据到缓存，造成了 CPU缓存穿透，天然也就影响了性能。所以造成了 fnc2 的工夫长于 fnc1 的工夫。

延长浏览

• 《如何写出让 CPU 执行更快的代码》链接
• 《开发内功修炼》链接
• 《深刻了解计算机系统》第六章：存储器层次结构