CPU

初识 CPU Cache 之 False Sharing | Bottom Up

俗话说得好“三天不读书、智商变成猪”，如今做业务太久、浮于表面而不了解底层原理，最近时间充裕了一些就开始读计算机基础的文章和论文。正好在工作交流群中有人问了一个结构体为什么加 Padding 的问题，也就因此开始追求极致的探索之路。

故事的开始来自于「Go 讨论群」，有一天有同学问到 RWLock - Codebase 为什么会有一个 Cache Line 长度的 Padding，虽然各位大佬都说为了解决 False Sharing 问题、但还是想追求极致地把这个原理给搞明白。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

const (
	cacheLineSize = 64
)

type RWLock []rwmutexShard

type rwmutexShard struct {
	_ [cacheLineSize]byte 	// 这个的用途是什么
	sync.RWMutex
}

func New() RWLock {
	return RWLock(make([]rwmutexShard, shardsLen))
}

什么是 CPU Cache

CPU Cache 我想对于在座的各位都已经老生常谈了，无非就是 L1 / L2 / L3 这三级缓存，但其实深入了解还是很有意思的。接下来就开始浅谈自己的见解，希望大家积极批评斧正。

图源 CPU Caches and Why You Care

上图是一个 4 核 8 线程的一个 CPU 缓存结构示例，显然 T 代表 Thread（线程）、I 代表 Instruction（指令）、D 代表 Data（数据）。

每一个 Core 有自己的 L1 和 L2 缓存，其中 L1 分 Instruction Cache（指令集缓存）和 Data Cache（数据集缓存），L2 就包罗万象了。

每个 Core 会共享 L3 缓存，其中 L3 和 L2 一样包罗万象，也有 CPU 架构是多核共享 L2 和 L3 的，也不影响咱后续的理解。

除此之外，CPU Cache 从左至右的容量越来越大（Capacity: L1 < L2 < L3），与之对应的，从左到右读取数据的速度依次递减（Speed: L1 > L2 > L3）。

图源 关于 CPU Cache

从上图也可以明显的看到 CPU 获取数据所需要的时钟周期（Clock Cycle），如果有搞弱电的同学应该就很明确知道 Cycle 的含义了，简言之可以看做另一种时间计量单位—— Cycle 越少速度越快。

  • L1 响应时延：4 个 CPU 时钟周期
  • L2 响应时延： 11 个 CPU 时钟周期
  • L3 响应时延：39 个 CPU 时钟周期
  • Main Memory 响应时延：107 个 CPU 时钟周期

数据源 CPU Caches and Why You Care

如何理解 Cache Line

讲了那么多 CPU 缓存的架构，回到今天的主题 Cache Line，那么这是什么东西呢？

The cache is made up of small chunks of mirrored main memory.The size of these chunks is called the line size, and is typically something like 32 or 64 bytes. When talking about cache, it is very common to talk about the line size, or a cache line, which refers to one chunk of mirrored main memory.

Source: Computer Science from the Bottom Up

CPU Cache 是由多块从内存「镜像」过来的数据组成，每组大小我们称之为 Line Size 一般大小为 32 或者 64 Bytes，因此我们也把这些 小块（Chunk） 叫做 Cache Line 。

知道了这是什么，但这怎么用呢？

相信大家在大一学 C 语言的时候做过一个小实验，关于行优先遍历（Row Major）和列优先遍历（Column Major）的实验，我们再次温故而知新、运行下述代码。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

const (
   limitOfMetrics  = 8000
   limitOfParallel = 8
)

func initMetrics() {
   // to guarantee the same metrics
   rand.NewSource(314159265359)
   // gen the metrics
   for i := 0; i < limitOfMetrics; i++ {
      rows := make([]int, 0, limitOfMetrics)
      for j := 0; j < limitOfMetrics; j++ {
         rows = append(rows, rand.Int())
      }
      metrics = append(metrics, rows)
   }
}

// BenchmarkRowTraversal Row Major
func BenchmarkRowTraversal(b *testing.B) {
   o.Do(initMetrics)
   numRow := len(metrics)
   numCol := len(metrics[0])
   b.ResetTimer()
   for i := 0; i < numRow; i++ {
      for j := 0; j < numCol; j++ {
         gg := metrics[i][j]
         gg++
      }
   }
}

// BenchmarkColTraversal Col Major
func BenchmarkColTraversal(b *testing.B) {
   o.Do(initMetrics)
   numRow := len(metrics)
   numCol := len(metrics[0])
   b.ResetTimer()

   for j := 0; j < numCol; j++ {
      for i := 0; i < numRow; i++ {
         gg := metrics[i][j]
         gg++
      }
   }
}

笔者的运行环境是公司的开发机，CPU 是 8 核的 Intel(R) Xeon(R) Platinum 8260 CPU @ 2.40GHz，Go 的版本是 go1.14.2 linux/amd64，那么我们开始跑个 Benchmark 吧。

从上图不难看出看出 Row Major 会比 Col Major 的速度略快一些，差距约为 50 ns/op，结论是行优先遍历会比列优先遍历快。

在大学时，老师对此的解释是局部性原理，但时至今日才真正理解问题的本质——一切都是 Cache Line。

我们声明 metrics 时，这是一块紧密相连的内存块，数据就会紧密的存在一起。 在 Go 里面的二维 Slice 其实是 SliceHeader 嵌套 SliceHeader，具体可以看 Go Slices: usage and internals 和 Arrays, slices (and strings): The mechanics of ‘append’。

每次 CPU 从 Main Memory 拿一块（Chunk）数据时，我们会从内存中取紧密相连的 64 Bytes 数据，换言之如果一行的大小正好是 64 Bytes，有一定概率将这整一行读进 Cache Line 中（即使读一部分进去也会提高效率）。

因此，如果我们按「行优先」的方式进行线性读的时候，接下来的数据将会大概率命中当前在 L1 的 Cache Line，其需要的时钟周期将会大大减少。

换言之，如果我们以「列优先」的方式进行线性读的时候，每次读数据有极大概率 Miss 当前在 L1 的 Cache Line，导致不断地从 Main Memory 读取数据，其需要的时钟周期将会成倍的增长。

这就是 CPU Cache 组成的形式以及运行的简要原理，了解这么多之后、我们就可以看看真实世界的问题了。

什么是 False Sharing

讲清楚了 Cache Line 后，我们回到开头的那个问题「为什么我们要补上一个 Padding」。

这就涉及了一个比较有意思的问题——Cache Coherency，缓存间的协同与一致性。还是原来的配方，我们再举个栗子。

如上图所示，假设 Core #0 和 Core #1 都命中了这一行 Cache Line，如果大家都是读则没有问题、但一旦涉及到跨核的写问题，则需要保证多核中读取相同地址数据的一致性，这就会变得比较复杂。具体过程可以看看 Cache Coherency，基于 MOESI Protocol 使用五个状态对每个 Cache Line 进行维护。

即任一 Core 对同一个 Cache Line 进行操作，凡是有这个 Cache Line 的 Core 需要重新从 L3 / Main Memory 读取回来保证多核下访问数据的一致性。

一言以蔽之，“两霸相争必有一伤”。这里的“伤”是不停地回写和置换 Cache Line 以及损失大量 Clock Cycles。

让我们再次实践出真知，同样功能的代码、修改三行，看看差异在哪？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

func BenchmarkOddTraversal(b *testing.B) {
   var wg sync.WaitGroup
   o.Do(initMetrics)
   ret := make([]int, limitOfParallel)

   b.ResetTimer()
   for tID := 0; tID < limitOfParallel; tID++ {
      wg.Add(1)
      go func(threadNo int) {
         defer wg.Done()
         for i, row := range metrics {
            if i%limitOfParallel != 0 {
               continue
            }
            for _, v := range row {
               if v%2 != 0 {
                  ret[threadNo]++ // here
               }
            }
         }
      }(tID)
   }
   wg.Wait()

   numOdds := 0
   for _, r := range ret {
      numOdds += r
   }
}

func BenchmarkOddTraversalOpt(b *testing.B) {
   var wg sync.WaitGroup
   o.Do(initMetrics)
   ret := make([]int, limitOfParallel)

   b.ResetTimer()
   for tID := 0; tID < limitOfParallel; tID++ {
      wg.Add(1)
      go func(threadNo int) {
         defer wg.Done()
         for i, row := range metrics {
            if i%limitOfParallel != 0 {
               continue
            }
            cnt := 0 // here
            for _, v := range row {
               if v%2 != 0 {
                  cnt++ // here
               }
            }
            ret[threadNo] += cnt // here
         }
      }(tID)
   }
   wg.Wait()

   numOdds := 0
   for _, r := range ret {
      numOdds += r
   }
}

从上图我们可以明显的看出，这三行改造带来的效率提升约为 10 倍（不同设备和环境带来的提升不同）。

我们的改动很简单，把「每次找到一个解就更新数组」变成「每次找完一组解才更新数组」，运用的原理就是我们之前说的 Cache Line 和 False Sharing。

我们声明了一个长度为 8 的 Slice，那么这 8 个数据在内存中是紧密相邻的、一同进入 64 Bytes 大的 Cache Line 概率将会非常高，每次对 Slice 的更新就会触发一次 Cache Line 的回写和置换。

但如果我们减少对同一个 Cache Line 的操作，那就会大大减少回写和置换的次数，从而减少 Clock Cycle 达到提效的效果。

回到最开始的问题「为什么我们要补上一个 Padding」，原因是我们会创建一个基于 rwmutexShard 的 Slice，如果不加上 Padding 的话、这几个 rwmutexShard 很大概率会命中同一个 Cache Line ，然后出现上面 10 倍效率之差的问题。

P.S. 其实这里不需要补 64 Bytes 那么多，将总长度补到 64 Bytes 即可。

总结

  1. 如果能按照 CPU 喜欢的姿势来，我们就尽量满足他、尽量使用一维数组去遍历。无论什么设计模式、结构体，我只知道一维数组百战百胜。
  2. 尽可能利用好 Cache Line，不仅要避免 False Sharing 问题、也要提升代码效率。
  3. 有时间一定要听听 Scott Meyers - CPU Caches and Why You care，温故而知新。

参考资料

  1. Eliminate False Sharing - Dr.Dobb’s
  2. Scott Meyers - CPU Caches and Why You care
  3. Why software developers should care about CPU caches - medium.com
  4. 关于 CPU Cache - 程序猿需要知道的那些事
  5. 与程序员相关的 CPU 缓存知识 - 酷壳
  6. What’s false sharing and how to solve it - medium.com
© 2015 - 2026 Dave's Blog
使用 Hugo 构建
主题 Stack 由 Jimmy 设计