计算机基础: 什么样的代码能让CPU运行的更快？

众所周知，程序在计算机里运行时，程序的指令和数据存储在 内存 中。当程序进程获得CPU时间片时，CPU将会从 内存 中"恢复执行现场"，然后继续循环执行程序的指令知道程序进程结束。

CPU的执行速度与内存的读写速度不在同一个层级，通常一次内存访问需要 200~300 个时钟周期，而CPU一个时钟周期可以执行 3~9 条指令。而一个程序中，访问内存的指令通常占25%左右，如果不能以某种方式降低访问内存时延的话，那对CPU执行来说就是个灾难！

因此为了尽可能降低内存与CPU之间读写差异，CPU内部加入了 CPU Cache，也被称为高速缓存。它体积小但访问速度极快，根据数据局部性原则，常用的数据可以复制到 CPU Cache 从减少CPU对内存的访问。

CPU Cache 分为3层：L1, L2, L3。其中 L1 高速缓存的访问速度几乎与寄存器一样快，只需要 2~4 个时钟周期。L2 则为 10~20 个时钟周期，L3 则为 20~60 个时钟周期。

我们的代码只有让 CPU Cache 更多命中缓存，减少CPU直接从内存中读取数据，这样才能让CPU跑得更快！

CPU Cache 是如何存储数据的？

CPU Cache 是由很多个连续的内存块组成，每个内存块被称为 Cache Line。Cache Line 的数量是限定的，例如在一个64KB的 CPU Cache 中，如果 Cache Line 的大小为 64字节, 那么就只有 1024 条Cache Line。

常见的 CPU Line 大小为 32、64 和 128 字节。这是一个经验值，如果 CPU Line 过大，局部性空间也越大，但是对应缓存行数就会越少。

CPU Line 是如何被替换的？

通常有 LRU 最近最少使用策略 和 随机替换策略 两种。

当CPU访问新数据且未命中 CPU Cache 时，那么则需要选择一条 CPU Line 来被新数据替换

如何查看 CPU Cache 和 CPU Line 的大小？

# 查看 L1 Cache 「数据」缓存的容量大小
cat /sys/devices/system/cpu/cpu0/cache/index0/size

# 查看 L1 Cache 「指令」缓存的容量大小
cat /sys/devices/system/cpu/cpu0/cache/index1/size

# 查看 L2 Cache 的容量大小
cat /sys/devices/system/cpu/cpu0/cache/index1/size

# 查看 L3 Cache 的容量大小
cat /sys/devices/system/cpu/cpu0/cache/index1/size

# 查看 Cache Line 的容量大小 (单位：字节)
cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size

什么样的代码能让 CPU Cache 更频繁的命中缓存？

我们使用go benchmark测试以下代码:
func arrayTravelIj(n int) {
  arr := make([][]int, n)
  for i, _ := range arr {
      arr[i] = make([]int, n)
  }

  for i := 0; i < n; i++ {
      for j := 0; j < n; j++ {
          arr[i][j] = 0
      }
  }
}

func arrayTravelJi(n int) {
  arr := make([][]int, n)
  for i, _ := range arr {
      arr[i] = make([]int, n)
  }

  for i := 0; i < n; i++ {
      for j := 0; j < n; j++ {
          arr[j][i] = 0
      }
  }
}

const N = 128

func BenchmarkArrayTravelIj(b *testing.B) {
  for i := 0; i < b.N; i++ {
      arrayTravelIj(N)
  }
}

func BenchmarkArrayTravelJi(b *testing.B) {
  for i := 0; i < b.N; i++ {
      arrayTravelJi(N)
  }
}

# 执行: go test -bench=^BenchmarkArrayTravel -benchmem .
# 结果: 
# cpu: Intel(R) Xeon(R) Gold 6278C CPU @ 2.60GHz
# BenchmarkArrayTravelIj-8           33397             35933 ns/op          134144 B/op        129 allocs/op
# BenchmarkArrayTravelJi-8           18099             66487 ns/op          134144 B/op        129 allocs/op
# PASS
可以看到，明明 内存分配次数 和 运行时的内存大小 是一样的, 但是 BenchmarkArrayTravelIj 比 BenchmarkArrayTravelJi 快了近一倍！

原因就是 BenchmarkArrayTravelIj 访问数据顺序是连续的，而 BenchmarkArrayTravelJi 访问数据顺序是跳跃的。

假如 N=2 ，那么 arr 在内存中的存储顺序为 arr[0][0],arr[0][1],arr[1][0],arr[1][1]。当N越来越大时，由 BenchmarkArrayTravelJi 访问数据顺序是跳跃的，那么 CPU Cache 命中率则会越来越低！

我的测试机器 L1 大小是32K，Cache Line 大小是64字节，那么意味着单个 Cache Line 能保存的int元素的数量是8个，整个 L1 CPU Cache 能保存的 Cache Line 条数是 512条。

换算一下就是整个 L1 CPU Cache 能保存的int元素是4096个，所以当N超过64时，随着N增大，两个函数的执行效率也会被越拉越大。

当然，64这个数字并不严谨，因为除了 CPU Cache 不仅只有 L1, 还有 L2, L3, 而且不同CPU的底层还会有各种硬件的加速内存预取策略

计算机基础: 什么样的代码能让CPU运行的更快？