Rust译文:02-代码内联运行变慢iCache原因

Rust译文:02-代码内联运行变慢iCache原因

1. 什么是iCache

CPU和主存之间也存在多级高速缓存,一般分为3级,分别是L1, L2和L3. 另外,我们的代码都是由2部分组成:指令和数据.L1 Cache比较特殊,每个CPU会有2个L1 Cache.分别为指令高速缓存(Instruction Cache,简称iCache)和数据高速缓存(Data Cache,简称dCache). L2和L3一般不区分指令和数据,可以同时缓存指令和数据.下图举例一个只有L1 Cache的系统.我们可以看到每个CPU都有自己私有的L1 iCache和L1 dCache.

2. 前言

这是上一篇关于 Rust 中 #inline 的文章的后续文章. 这篇文章比较笼统,也比较啰嗦. 读者,当心! 在讨论内联编译优化时,几乎总是提到以下内容:

内联也会使代码变慢,因为内联会增加代码的大小,使指令缓存变大并导致缓存未命中

我自己已经多次看到以上情形以各种形式重复出现.我还看到了很多基准测试,其中明智地删除内联注释确实提高了性能. 然而,我从来没有看到性能改进能够追溯到 iCache.至少对我来说,这个解释似乎没有根据. 人们认为 iCache 是慢benchmark罪魁祸首,因为其他人这么说,而不是因为这里有一个benchmark大家都认可以证明iCache是罪魁祸首.

这并不意味着 iCache这个答案就是错误的, 只是我个人没有证据证明它比任何其他解释更好. 无论如何,我决定看一个我知道 inline 会导致可观察到的运行慢的特定案例,并并高清楚到底发生了什么. 请注意,这里的目标不是解释 inline 对现实世界的影响,benchmark是人为的.

  • 首先,我们的目标是更多地了解用于解释结果的工具.
  • 第二个目标是在实践中观察 iCache 的效果,或者为为什么删除内联可以加快编译速度提供替代假设.

3. Benchmark

Benchmark测试基于我的 once_cell Rust 库. 该库提供了一种原语,类似于双重检查锁定.

有一个看起来像这样的函数:

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() {
    // Fast path.
    return Ok(value);
  }

  // Slow path.
  self.0.initialize(f)?;
  Ok(unsafe { self.get_unchecked() })
}

我知道当 initialize 函数没有内联时,性能会显着提高. 事实确实如此(这就是为什么benchmark是综合的,现实世界的例子是关于我们不知道是否需要内联的情况).

但目前还不清楚为什么内联初始化会导致代码变慢. 对于实验,我编写了一个简单的高级benchmark测试,在循环中调用 get_or_try_init:

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);
  }
}

我还添加了编译时切换来强制或禁止内联:

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

您可以在此提交中看到完整的基准测试

运行这两个版本表明 inline(never) 确实要快得多:

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

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

请注意,我们在这里不使用花哨的统计数据. /usr/bin/time 足以用肉眼看到差异,尽管我们正在寻找的效果非常低级. 因此,一般提示:如果您正在对相对差异(而不是绝对性能)进行基准测试,请不要费心测量纳秒级精度的时间. 取而代之的是,循环基准足以使人类可察觉的变化.

我们如何解释这种差异? 第一步是从等式中删除货物并制作两个二进制文件进行比较:

$ 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 可能是罪魁祸首,让我们包括缓存的计数器:

$ 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

4. 细节

L1-icache-load-misses 有一些差异,但指令也有惊人的差异. 更重要的是,L1-icache-load-misses 的差异很难估计,因为不清楚 L1-icache-loads 是什么. 作为健全性检查,dcache 的统计数据与我们预期的一样. 虽然 perf 从 CPU 获取真实数据,但另一种方法是在模拟环境中运行程序.

这就是 cachegrind 工具所做的. 有趣的事实:cachegrind 的主要作者是@nnethercote,我们在上一篇文章中看到了他的 Rust Performance Book. 让我们看看 cachegrind 对基准测试的看法.

$ 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 模拟程序,因此运行速度要慢得多. 在这里,我们没有看到 iCache 未命中(I1 — 一级指令缓存,LLi — 末级指令缓存)的大差异. 我们确实看到了 iCache 引用的不同. 请注意,CPU 引用 iCache 的次数应与其执行的指令数相对应. 用 perf 交叉检查数量,我们看到 perf 和 cachegrind 都同意执行的指令数量. 他们也同意 inline_always 版本执行更少的指令.

仍然很难说 perf 的 sL1-icache-loads 是什么意思. 从名字上看,它应该与 cachegrind 的 I refs 相对应,但事实并非如此. 不管怎样,似乎有一件事需要进一步调查 —— 为什么内联会改变执行的指令数量?内联实际上并没有改变 CPU 运行的代码,所以指令的数量应该保持不变. 那我们来看看asm吧!这里正确的工具是cargo-asm. 同样,这是我们将锁定的函数:

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 版本:

  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 版本:

  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


我稍微编辑了代码,并突出显示了构成基准测试的大部分的热循环. 查看程序集,我们可以看到以下内容:代码要大得多 — 发生了内联! 函数序言更大,编译器将更多被调用者保存的寄存器压入堆栈 函数尾声更大,编译器需要恢复更多寄存器堆栈帧更大 编译器将一些初始化代码提升到循环之前 两种情况下的核心循环都非常紧凑, 只有少数指令核心循环向上计数而不是向下计数,添加额外的 cmp 指令请注意,iCache 不太可能影响正在运行的代码,因为它是内存中彼此相邻的一小部分指令.

另一方面,具有大立即数的额外 cmp 正好说明了我们观察到的额外指令数量(循环运行了 800_000_000 次).

5. 结论

想出一个基准来证明两种替代方案之间的差异已经够难的了. 更难解释差异 — 可能有很多现成的解释,但它们不一定是真的. 尽管如此,今天我们拥有大量有用的工具. 两个值得注意的例子是 perf 和 valgrind. 工具并不总是正确的 — 根据对问题的常识性理解,对不同的工具进行理智的检查是一个好主意.

试考虑内联技术将函数S内联展开于函数C中:

  • 内联使得C占用了更多的寄存器.由于函数S的代码直接在函数C的函数体中展开,造成函数C在程序上下文切换过程中加入了更多的push/pop指令,并且函数C的运行时栈的空间进一步膨胀.与内联版本中每次调用函数C都意味着这些新增的push/pop指令都会运行不同,未内联版本的push/pop指令只存在于函数S的上下文中,并且只有当函数C确实调用函数S时,这些指令才会被运行;
  • 基于第一点的基本认识,现在设想函数S在流程控制语句中被调用(循环或条件分支等),编译器可能会提升函数S中的某些指令到条件分支之外,造成这些指令从冷路径变为热路径(冷热路径:因为条件分支可能不会执行,但是位于条件分支之外的代码总会执行,是为热路径);
  • 在上述场景中,随着外层函数C的栈中局部变量和流程控制语句增多,编译器的优化反而使得热路径执行效率降低.

原文地址

The End

线上交流工具: 在你的terminal中输入 ssh $用户@mojotv.cn

在你的terminal中输入 ssh mojotv.cn hn 查看最新 hacknews

目录