首页 [译] 并不总是 iCache
文章
取消

[译] 并不总是 iCache

发表于 2022/02/17 更新于 2022/12/30
作者 Aleksey Kladov
16 分钟阅读

免责声明

本文是对原博文《It’s Not Always ICache》的无授权翻译转载，不享受任何著作权利，不用于任何商业目的，不以任何许可证进行授权，不对任何转载行为尤其是商业转载行为负责。一切权利均由原作者 Aleksey Kladov 保有。

本文中出现的所有第一人称均指代 Aleksey Kladov 而非译者本人。本文中对一些术语会额外附加英文原文注释，以帮助读者搜索相关概念。

正文

这是上一篇关于 Rust 中 #[inline] 的文章的后续。这个帖子有一点笼统，而且有一点啰嗦。读者请小心！

在讨论内联优化时，几乎总是会提到以下内容：“内联也会使代码变慢，因为内联会增加代码大小，增大指令缓存（ICache，Instruction Cache）大小并导致缓存未命中（Miss）”。

我自己已经多次看到这种说法以各种形式复述。我还看到在很多基准（Benchmark）中明智地移除了内联标记确实提高了性能。但是，我从未看到过针对 ICache 的性能改进。至少对我来说，这种解释似乎没有根据——人们知道指责 ICache 是因为别人都这么说，而不是因为每个人都能指出一个基准。这并不意味着 ICache 的解释是错误的——只是我个人而言没有证据表明它比任何其他解释都更好。

不管如何，我决定先看一个我所知道的 #[inline] 会显著降低速度的具体案例，并理解它为什么会发生。请注意，这里的目的不是为了解释 #[inline] 的实际影响，基准是人为定义的。我们的首要目标是更多地了解用于解释结果的工具。次要目标是，要么在实践中观察 ICacha 的效果，或者给为什么移除内联可以加速提供备选的假设。

基准测试基于我的 once_cell Rust 库，该库提供了一个原语（Primitive），类似于双重检查锁定（Double-Checked Locking）。有这么一个函数：

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

fn get_or_try_init<F, E>(&self, f: F) -> Result<&T, E>
where
 F: FnOnce() -> Result<T, E>,
{
  if let Some(value) = self.get() {
    // 快速分支
    return Ok(value);
  }

  // 慢速分支
  self.0.initialize(f)?;
  Ok(unsafe { self.get_unchecked() })
}

我知道当 initialize 函数没有内联时性能会显着提高。在这个例子中比较明显（这就是为什么基准是人造的——现实世界的例子尽是我们不知道是否需要 inline 的情况）。但不知为何，确切的说，内联 initialize 会使代码变慢。

作为实验，我编写了一个简单的高级基准测试循环调用 get_or_try_init：

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

const N_LOOPS: usize = 8;
static CELL: OnceCell<usize> = OnceCell::new();

fn main() {
  for i in 0..N_LOOPS {
    go(i)
  }
}

fn go(i: usize) {
  for _ in 0..100_000_000 {
    let &value = CELL.get_or_init(|| i);
    assert!(value < N_LOOPS);
  }
}

我还添加了编译开关来强制或禁止内联：

1
2
3

#[cfg_attr(feature = "inline_always", inline(always))]
#[cfg_attr(feature = "inline_never", inline(never))]
fn initialize() { ... }

您可以在此提交中找到完整的基准测试：matklad/once_cell@a741d5f。

运行这两个版本表明 #[inline(never)] 确实更快：

1
2
3
4
5

$ cargo run -q --example bench  --release --features inline_always
330ms

$ cargo run -q --example bench  --release --features inline_never
259ms

请注意，在这里我们不使用花哨的统计数据。/usr/bin/time 已经足够用肉眼看出差距，即使我们所寻找的效果非常低级。因此，一个普适性提示：如果您要对相对差异（而不是绝对性能）进行基准测试，请不要费心测量纳秒级精度的时间。取而代之的是，循环该基准足够多次以使其变为人类可感知。

我们如何解释差异？第一步是从测试语句中移除 cargo 并制作两个二进制文件进行比较：

1
2
3
4

$ cargo build --example bench --release --features inline_never
$ cp ./target/release/examples/bench never
$ cargo build --example bench --release --features inline_always
$ cp ./target/release/examples/bench always

在 Linux 上，能够快速访问任何程序性能的最佳工具是 perf stat。它运行程序并显示大量 CPU 级别的性能计数器，这可以解释发生了什么。由于我们怀疑 ICache 可能是罪魁祸首，让我们包含缓存的计数器：

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

$ perf stat -e instructions,cycles,\
> L1-dcache-loads,L1-dcache-load-misses,L1-dcache-prefetches,\
> L1-icache-loads,L1-icache-load-misses,cache-misses \
> ./always
348ms

 6,396,754,995      instructions:u
 1,601,314,994      cycles:u
 1,600,621,170      L1-dcache-loads:u
         4,806      L1-dcache-load-misses:u
         4,402      L1-dcache-prefetches:u
        69,594      L1-icache-loads:u
           461      L1-icache-load-misses:u
         1,928      cache-misses:u

$ perf stat -e instructions,cycles,\
> L1-dcache-loads,L1-dcache-load-misses,L1-dcache-prefetches,\
> L1-icache-loads,L1-icache-load-misses,cache-misses \
> ./never
261ms

 Performance counter stats for './never':

 5,597,215,493      instructions:u
 1,199,960,402      cycles:u
 1,599,404,303      L1-dcache-loads:u
         4,612      L1-dcache-load-misses:u
         4,290      L1-dcache-prefetches:u
        62,268      L1-icache-loads:u
           603      L1-icache-load-misses:u
         1,675      cache-misses:u

L1-icache-load-misses 存在一些差异，但 instructions 也存在令人惊讶的差异。再者，L1-icache-load-misses 上的差异难以估量，因为不清楚 L1-icache-loads 是什么。作为一个健全的检测，dcache 的统计数据是相同的，正如我们所期望的那样。

在 perf 从 CPU 获取真实数据的同时，另一种备选方案是在模拟环境中运行程序。这就是 cachegrind 工具的作用。有趣的事实：cachegrind 的主要作者是 @nnethercote，我们在上一篇文章中看到了他的 Rust performance book。让我们看看 cachegrind 对基准的看法。

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

$ valgrind --tool=cachegrind ./always
10s
 I   refs:      6,400,577,147
 I1  misses:            1,560
 LLi misses:            1,524
 I1  miss rate:          0.00%
 LLi miss rate:          0.00%

 D   refs:      1,600,196,336
 D1  misses:            5,549
 LLd misses:            4,024
 D1  miss rate:           0.0%
 LLd miss rate:           0.0%

 LL refs:               7,109
 LL misses:             5,548
 LL miss rate:            0.0%

$ valgrind --tool=cachegrind ./never
9s
 I   refs:      5,600,577,226
 I1  misses:            1,572
 LLi misses:            1,529
 I1  miss rate:          0.00%
 LLi miss rate:          0.00%

 D   refs:      1,600,196,330
 D1  misses:            5,553
 LLd misses:            4,024
 D1  miss rate:           0.0%
 LLd miss rate:           0.0%

 LL refs:               7,125
 LL misses:             5,553
 LL miss rate:            0.0%

请注意，因为 cachegrind 模拟运行程序，所以运行速度要慢得多。此处我们并没有看到在缓存未命中（I1——一级指令缓存，LLi——最后一级指令缓存）上的巨大差异。请注意，CPU 引用 ICache 的次数应与其执行的指令数量相对应。用 perf 交叉检查数量，我们可以看到 perf 和 cachegrind 二者皆同意执行指令的数量。仍然很难说明 perf 的 sL1-icache-loads 是什么。从名称来看，它应该对应 cachegrind 的 I refs，但事实并非如此。

无论如何，似乎有一件事需要进一步调查——为什么内联会改变执行的指令数量？内联实际上不会改变 CPU 运行的代码，因此指令的数量应该保持不变。那我们来看看汇编吧！此处正确工具是 cargo-asm。

同样，我们将目光锁定在这个函数：

1
2
3
4
5
6

fn go(tid: usize) {
  for _ in 0..100_000_000 {
    let &value = CELL.get_or_init(|| tid);
    assert!(value < N_THREADS);
  }
}

调用 get_or_init 将被内联，嵌套调用 initialize 将根据标志内联。

我们先来看一下 inline_never 版本：

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

  push    r14 ;
  push    rbx ; prologue
  push    rax ;
  mov     qword, ptr, [rsp], rdi
  mov     ebx, 100000001 ; loop counter
  mov     r14, rsp
  jmp     .LBB14_1
 .loop:
  cmp     qword, ptr, [rip, +, CELL+16], 8
  jae     .assert_failure
 .LBB14_1:
  add     rbx, -1
  je      .normal_exit
  mov     rax, qword, ptr, [rip, +, CELL]
  cmp     rax, 2
  je      .loop
  mov     rdi, r14
  call    once_cell::imp::OnceCell<T>::initialize
  jmp     .loop
 .normal_exit:
  add     rsp, 8 ;
  pop     rbx    ; epilogue
  pop     r14a   ;
  ret            ;
 .assert_failure:
  lea     rdi, [rip, +, .L__unnamed_12]
  lea     rdx, [rip, +, .L__unnamed_13]
  mov     esi, 35
  call    qword, ptr, [rip, +, core::panicking::panic@GOTPCREL]
  ud2

然后在 inline_always 版本中：

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
62
63
64
65
66
67
68
69
70
71
72

  push    rbp  ;
  push    r15  ;
  push    r14  ;
  push    r13  ; prologue
  push    r12  ;
  push    rbx  ;
  sub     rsp, 24
  mov     r12, rdi
  xor     ebx, ebx
  mov     r13d, 1
  lea     r14, [rip, +, CELL]
  mov     rbp, qword, ptr, [rip, +, WaiterQueue::drop@GOTPCREL]
  mov     r15, qword, ptr, [rip, +, once_cell::imp::wait@GOTPCREL]
  jmp     .LBB10_1
 .LBB10_10:
  mov     qword, ptr, [rsp, +, 8], r14
  mov     qword, ptr, [rip, +, CELL+8], 1
  mov     qword, ptr, [rip, +, CELL+16], r12
  mov     qword, ptr, [rsp, +, 16], 2
  lea     rdi, [rsp, +, 8]
  call    rbp
 .loop:
  add     rbx, 1
  cmp     qword, ptr, [rip, +, CELL+16], 8
  jae     .assert_failure
 .LBB10_1:
  cmp     rbx, 100000000
  je      .normal_exit
  mov     rax, qword, ptr, [rip, +, CELL]
  cmp     rax, 2
  je      .loop
 .LBB10_3:
  mov     rax, qword, ptr, [rip, +, CELL]
 .LBB10_4:
  test    rax, rax
  jne     .LBB10_5
  xor     eax, eax
  lock    cmpxchg, qword, ptr, [rip, +, CELL], r13
  jne     .LBB10_4
  jmp     .LBB10_10
 .LBB10_5:
  cmp     rax, 2
  je      .loop
  mov     ecx, eax
  and     ecx, 3
  cmp     ecx, 1
  jne     .LBB10_8
  mov     rdi, r14
  mov     rsi, rax
  call    r15
  jmp     .LBB10_3
 .normal_exit:
  add     rsp, 24 ;
  pop     rbx     ;
  pop     r12     ;
  pop     r13     ; epilogue
  pop     r14     ;
  pop     r15     ;
  pop     rbp     ;
  ret
 .assert_failure:
  lea     rdi, [rip, +, .L__unnamed_9]
  lea     rdx, [rip, +, .L__unnamed_10]
  mov     esi, 35
  call    qword, ptr, [rip, +, core::panicking::panic@GOTPCREL]
  ud2
 .LBB10_8:
  lea     rdi, [rip, +, .L__unnamed_11]
  lea     rdx, [rip, +, .L__unnamed_12]
  mov     esi, 57
  call    qword, ptr, [rip, +, core::panicking::panic@GOTPCREL]
  ud2

我稍微编辑了一下代码，并且突出显示构成基准测试主体的热循环。

查看汇编，我们可以看到以下内容：

  • 代码要大得多——内联发生了！
  • 函数序言（Prologue）更大，编译器将更多被调用者保存的寄存器转移到堆栈
  • 函数收尾（Epilogue）较大，编译器需要恢复更多寄存器
  • 堆栈帧（Stack Frame）更大
  • 编译器将一些 initialize 代码提到循环之前
  • 在这两种情况下，核心循环都非常紧凑，只有少量指令
  • 核心循环向上而不是向下计数，增加了一条额外的 cmp 指令

请注意，ICache 不太可能影响正在运行的代码，因为它是内存中彼此相邻的一小部分指令。另一方面，带有大立即数的额外 cmp 指令正好说明了我们观察到的额外指令的数量（循环运行了 800_000_000 次）。

结论

很难提出一个基准来证明两种选择之间的差异。解释差异甚至更难——可能有很多现成的解释，但它们不一定是对的。尽管如此，现今我们拥有大量有用的工具。两个值得注意的例子是 perf 和 valgrind。工具并不总是正确的——最好对不同的工具彼此之间，以及对问题的常识性理解进行健全性检查。

尤其是对于内联，我们发现内联 S 到 C 可能会导致速度变慢的原因如下：

  1. 内联可能会导致 C 使用更多寄存器。这意味着序言（Prologue）和收尾（Epilogue）增加了额外的 push/pop 指令，这些指令也使用堆栈内存。在没有内联的情况下，这些指令被隐藏在 S 中并且仅在 C 实际调用 S 时才耗费，而不是每次调用 C 本身时。
  2. 从第一点概括，如果 S 在循环中或在 if 中被调用，编译器可能会将一些 S 的指令提到分支之前，将它们从冷路径移动到热路径。
  3. 由于堆栈帧中有更多的局部变量和控制流需要处理，编译器可能会意外地对热循环持悲观态度。

如果您对 ICache 在哪些情况下会成为问题感到好奇，请参阅这篇关于此类案例的优秀文章。

翻译, Rust
rust 翻译
最近更新
文章内容

[译] Rust 中的内联

高通平台自定义按键进入 fastboot/recovery/edl 模式