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

  1. 🐶❤️🦀
  2. Rust笔记
  3. Rust译文:02-代码内联运行变慢iCache原因
4.5 EricZhou Rust笔记
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的栈中局部变量和流程控制语句增多,编译器的优化反而使得热路径执行效率降低.

原文地址

类别和标签

TCP/IP notes CPP CheatSheet 快速入门 快速查询 Jekyll Github Python Golang Shell Bash docker 教程 container nginx dockerfile golang Spider 钉钉 PhantomJS RPC protobuf gRPC 文件 操作 GUI reflect 网络请求 代理 http chromedp Go进阶 工具 Vim Javascript seaweedfs Raft raft Git Nginx RESTful gitbook node npm github pages toml lumen laravel cors markdown 日志 log mysql 定时任务 php 程序员 Python教程 redis Dockerhub Docker OSS 网络协议 python 运维开发 kali linux 树莓派 raspberryPi algorithm 算法 黑客 hack ssh xtermjs shell context gcc g++ jekyll 破解 LDAP Linux CSS ES6 OAuth2 Prometheus Grafana Nes Game HTTP3 Java 动手 Gateway 网关 Rust笔记 fullstack

Chinese Tech Blog | Golang Captcha Open Source Project | Youtube Channel | Bilibli Channel | neochau@gmail.com  |  Github Account Mojocn | 鄂ICP备16006181号-4

目录