Yanyan's Wiki 软件工程研究入门 (2022)

Lab3: 性能调优

小实验说明

小实验 (Labs) 是 ICS 这门课程里的一些综合编程题,旨在结合课堂知识解决一些实际中的问题。因为问题来自实际,所以有时候未必能立即在课本上找到相关知识的答案,而是需要 “活学活用”。因此,大家需要利用互联网上的知识解决这些问题,但不要试图直接搜索这些问题的答案,即便有也不要点进去 (也请自觉不要公开发布答案)。

Soft deadline: 2021 年 12 月 12 日 23:59:59。

1. 背景

性能调优是系统编程的一个重要组成部分。例如同学们在遇到 “Online Judge 提交 TLE” 以后,如果排除了死循环等逻辑问题,并且坚持算法/数据结构没有选错,就要开始性能调优。根据我们的了解,大部分同学先前性能调优的方法是 “随机调优法”:

  1. 观察程序,看到一些可能的性能优化点 (例如找到一个 i *= 2);
  2. 对程序进行一些功能等价的修改 (例如改成 i <<= 1);
  3. 运行程序,观察是否有显著的性能提升。

但这种方式显然是不科学、不合理的,例如上面的修改以很大的概率不会对程序的性能有可见的影响。在这个实验中,写出更快的代码不是目的,而是帮助大家熟悉性能分析的工具,然后做出针对性的优化。正如 D. E. Knuth 所说,“Premature optimization is the root of all evil”。

这个实验给大家轻松一下,比大家想象得要简单。但请大家抑制住使用 “随机调优法” 的冲动 (尽管它很可能能 work),而是使用工具分析程序的性能,并做出针对性的优化。

2. 实验要求

2.1 实验内容

我们已经给出一份 Eratosthenes 筛法求 $2, 3, \ldots, n$ 中素数的参考代码。它很简短,运行得也不太慢:

// 初始时,is_prime[] 为 true
for (int i = 2; i <= n; i++) {
  for (int j = i + i; j <= n; j += i) {
    is_prime[j] = false;
  }
}

但今天你的老板提出了新的要求,他希望你的代码运行得更快一些。请你使用工具找到性能瓶颈,相应地作出算法/代码实现上的改进,尽可能地提升你程序的执行效率。

我们优化的目标是使你的程序相比上述参考代码 (在 Online Judge 上) 性能提升 10 倍。

其中一些值得注意的事项:

  1. 允许修改数据结构的定义和算法。
  2. 我们 (和其他 Labs 一样) 在编译时会开启 -O1 优化开关。除了一些较为激进的优化 (如循环展开等) 外,编译器依然会尽可能地分析数据流、内联函数等方式优化你的代码。大家可以在 gcc 的手册中寻找 -O1 相关的优化,例如 -fdefer-pop, -finline-functions-called-once 等。
  3. 我们允许你做一些预处理,以及我们鼓励你使用预处理。但我们限制 sieve.c 的大小不能超过 4096 字节。
  4. 我们实际运行的测试用例中,$n < 10^7$,因此你不必修改 $N$ 的定义。

2.2 代码获取与提交

Academic Integrity

从网上或别人那里复制几行代码非常简单——但你如果遵守 academic integrity,自己尝试完成,就会遇到巨大的困难 (尤其如果你没有试着用正确的工具、正确的方法诊断问题)。这是我们给你必要的训练

请使用我们的 Makefile 编译 (在实验目录中执行 make),确保 Git 记录完整。

在之前实验的 ics-workbench 中,在终端执行

git pull origin lab3

可以获得实验的框架代码。提交方法同之前的 Lab: 在实验的工作目录中执行 make submit。需要设置 STUID (学号) 和 STUNAME (中文姓名) 环境变量。

ICS2021-Lab3 提交结果

2.3 评分与正确性标准

我们只评测你实现的 sieve.c。你的实现求出的素数表必须正确,不正确将被 Online Judge 拒绝。在素数表实现正确的基础上,如果性能提升达到 10 倍即可通过所有测试用例 (仅有一个用例)。

2.4 常见问题

(TBD)

3. 性能调优

3.1 Trace 和 Profiler

如果想理解一次程序的执行,本质上我们只需要知道程序执行过程中 “发生了什么”——调用了哪些函数/库/操作系统 API;执行了什么语句/指令;它们分别花去了多少时间/资源。从另一个角度来理解,程序 (乃至计算机系统) 的执行可以看成是一次状态机的执行,这意味着我们只要知道状态机运行过程中所有的状态,以及状态迁移时执行的指令/语句,就能对程序的行为了如指掌。

事实上,计算机系统中已经为我们提供了这样的工具——“追踪” 程序执行的工具成为 trace,而更轻量、将执行中的采样信息汇总的工具称为 profiler。我们不妨试试系统中给我们的 trace 和 profiler。下面的命令打印一个程序对操作系统所有 API 调用的 trace,同时带有时间统计——你可能已经意识到,在实际业务系统中,程序所花去的时间很可能大部分都在 I/O 设备和网络的读写上,而 strace 可以帮助你定位哪些操作花去了最多的时间。

$ strace -T echo hello
execve("/bin/echo", ["echo", "hello"], 0x7ffe9f27c010 /* 29 vars */) = 0 <0.000581>
brk(NULL)                               = 0x56303260e000 <0.000128>
arch_prctl(0x3001 /* ARCH_??? */, 0x7ffe42316460) = -1 EINVAL (Invalid argument) <0.000030>
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory) <0.000173>
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3 <0.000219>
fstat(3, {st_mode=S_IFREG|0644, st_size=108466, ...}) = 0 <0.000147>
mmap(NULL, 108466, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f6668245000 <0.000141>
close(3)                                = 0 <0.000110>
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3 <0.000158>
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\360q\2\0\0\0\0\0"..., 832) = 832 <0.000181>
...
brk(NULL)                               = 0x56303260e000 <0.000190>
brk(0x56303262f000)                     = 0x56303262f000 <0.000042>
openat(AT_FDCWD, "/usr/lib/locale/locale-archive", O_RDONLY|O_CLOEXEC) = 3 <0.000209>
fstat(3, {st_mode=S_IFREG|0644, st_size=5699248, ...}) = 0 <0.000066>
mmap(NULL, 5699248, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f6667ae1000 <0.000085>
close(3)                                = 0 <0.000130>
fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(0x88, 0), ...}) = 0 <0.000127>
write(1, "hello\n", 6hello
)                  = 6 <0.000187>
close(1)                                = 0 <0.000095>
close(2)                                = 0 <0.000065>
exit_group(0)                           = ?

类似地,你还可以用 ltrace 查看它向库函数的调用:

$ ltrace python3 --help
pthread_condattr_init(0x95c900, 0x93c820, 0x93c7e8, 0x93c800)                  = 0
pthread_condattr_setclock(0x95c900, 1, 0x93c7e8, 0x93c800)                     = 0
malloc(32)                                                                     = 0x24d12a0
sem_init(0x24d12a0, 0, 1, 0x24d12c0)                                           = 0
pthread_self(0x24d12d0, 0, 1, 0x24d12f0)                                       = 0x7f487858c740

这些平时使用的程序的行为对你来说已经 “一览无余” 了。这些工具在之后的《操作系统》课中会被反复地使用,以真实地理解程序是如何在操作系统上运行的。

Profiler 可以看成是对 trace 信息的汇总——因为我们不需要得到 “每一次” 调用/执行的信息,因此 profiler 很多时候可以实现得更轻量:我们需要隔一段时间对程序的执行采样即可。例如如果我们希望了解哪个函数使用了最多的时间,大家可以想到如下的实现:

  1. 借助系统的机制,每秒给进程发送若干 (例如 100) 次 “中断”,中断到来后,会跳转到一个 “中断” 处理程序。
  2. 在 “中断” 处理程序中,我们遍历函数的调用栈,获得当前的调用链并记录。
  3. 程序执行完毕后,根据采样的得到的信息,就能推断出哪些函数 (近似) 消耗了多少时间。

对小程序来说这个机制当然没有什么大用处;但如果你的项目是数十、数百万行代码的项目,此时发现在某个特定的输入上出现了急剧的性能下降。如果这时候有 profiler 帮忙,那几乎一瞬间就能定位到性能的瓶颈,并诊断出导致性能问题的原因。

Linux perf

Linux 为我们提供了 perf tools 系列的性能诊断工具,确保你安装了它:

$ perf

 usage: perf [--version] [--help] [OPTIONS] COMMAND [ARGS]

 The most commonly used perf commands are:
   ...
   record          Run a command and record its profile into perf.data
   report          Read perf.data (created by perf record) and display the profile
   stat            Run a command and gather performance counter statistics
   ...

Perf 工具的用法很多,在这里我们可以使用 perf record 记录程序的执行信息,然后使用 perf report 查看日志。当然,你可能会遇到一些奇怪的问题,请自行 STFW 解决——这里涉及到的一些概念我们暂时无法彻底地解释清楚,也欢迎大家选修下学期的操作系统课。无论如何,当你成功运行 perf report 之后,你就会立即看到程序的哪个部分运行了最多的时间:

  98.27%  perftune-64  perftune-64       [.] sieve
   0.67%  perftune-64  [unknown]         [k] 0xffffffff980c5067

也就是 sieve 函数是我们的性能瓶颈 (当然)!其他的部分我们暂时可以忽略。同命令行工具交互,我们可以看到详细的汇编代码占用的运行时信息 (不同的机器可能看到不同的结果,尤其是虚拟机):

Percent│    sieve():
       │      cmp     $0x1,%ebx
       │    ↓ jle     89
       │      lea     -0x2(%rbx),%edi
       │      add     $0x3,%rdi
       │      mov     $0x2,%edx
       │      mov     $0x4,%esi
       │      lea     is_prime,%rcx
       │    ↓ jmp     49
  0.05 │3c:   add     $0x2,%rsi
  0.05 │      add     $0x1,%rdx
       │      cmp     %rdi,%rdx
  0.38 │    ↓ je      5d
       │49:   cmp     %esi,%ebx
       │    ↑ jl      3c
       │      mov     %rsi,%rax
  0.33 │50:   movb    $0x0,(%rcx,%rax,1)
 57.32 │      add     %rdx,%rax
  0.43 │      cmp     %eax,%ebx
 38.50 │    ↑ jge     50
       │    ↑ jmp     3c
       │5d:   mov     $0x2,%eax
       │      lea     primes,%rdx
       │      lea     is_prime,%rcx
       │    ↓ jmp     7b
       │72:   add     $0x1,%rax
       │      cmp     %rdi,%rax
       │    ↓ je      89

当然你会对其中的结果产生一些疑问:例如 add 指令占用了绝大部分时间 (57.32%),而访问内存的 movb 却只占用了 0.33%。这是因为现代处理器是 out-of-order 地执行指令,因此 perf 并不能提供一个精确到每条指令的信息 (甚至这样的信息就是不存在的)。

此外,你可以用 perf stat 来查看一次运行的统计信息:

$ perf stat ./perftune-64
     446.40 msec task-clock              #    0.999 CPUs utilized          
          1      context-switches        #    0.002 K/sec                  
          0      cpu-migrations          #    0.000 K/sec                  
       3145      page-faults             #    0.007 M/sec                  
 1237928727      cycles                  #    2.773 GHz                      (82.97%)
    8339594      stalled-cycles-frontend #    0.67% frontend cycles idle     (82.97%)
 1009985758      stalled-cycles-backend  #   81.59% backend cycles idle      (83.04%)
  709642503      instructions            #    0.57  insn per cycle         
                                         #    1.42  stalled cycles per insn  (83.87%)
  184044062      branches                #  412.287 M/sec                    (83.88%)
    1022107      branch-misses           #    0.56% of all branches          (83.26%)

统计信息中有更多关于指令数等的统计;甚至你可以用 -e 选项指定更多的统计信息:

$ perf stat -e cycles,instructions,L1-dcache-loads,L1-dcache-load-misses,LLC-loads,LLC-load-misses ./perftune-64
        1249139985      cycles                                                      
         704974262      instructions              #    0.56  insn per cycle         
         317118378      L1-dcache-loads                                             
          91913746      L1-dcache-load-misses     #   28.98% of all L1-dcache hits  
   <not supported>      LLC-loads                                                   
   <not supported>      LLC-load-misses                                             

不过我这个实验的 AMD Yes (EPYC 7401) 处理器并不支持 LLC 的 load miss 统计。不过我们看到,L1 cache miss rate 和 IPC 都不太满意。大家可以参考某个调优后的代码 (接近 10X 性能提升):

$ perf stat -e cycles,instructions,L1-dcache-loads,L1-dcache-load-misses,LLC-loads,LLC-load-misses ./perftune-64 
         131645242      cycles                                                      
         398053540      instructions              #    3.02  insn per cycle         
          41555727      L1-dcache-loads                                             
           4643651      L1-dcache-load-misses     #   11.17% of all L1-dcache hits  
   <not supported>      LLC-loads                                                   
   <not supported>      LLC-load-misses                                             

指令数减半,并且 IPC 从 0.56 提升到了 5 倍。大家可以根据观察到的统计数据,找到代码的性能瓶颈,并且做出相应的优化。

Creative Commons License    苏 ICP 备 2020049101 号