Lab3: 性能调优
小实验说明
小实验 (Labs) 是 ICS 这门课程里的一些综合编程题，旨在结合课堂知识解决一些实际中的问题。因为问题来自实际，所以有时候未必能立即在课本上找到相关知识的答案，而是需要 “活学活用”。因此，大家需要利用互联网上的知识解决这些问题，但不要试图直接搜索这些问题的答案，即便有也不要点进去 (也请自觉不要公开发布答案)。
Deadline: 2022 年 12 月 4 日 23:59:59。
1. 背景
性能调优是系统编程的一个重要组成部分。例如同学们在遇到 “Online Judge 提交 TLE” 以后，如果排除了死循环等逻辑问题，并且坚持算法/数据结构没有选错，就要开始性能调优。根据我们的了解，大部分同学先前性能调优的方法是 “随机调优法”：
- 观察程序，看到一些可能的性能优化点 (例如找到一个
i *= 2)； - 对程序进行一些功能等价的修改 (例如改成
i <<= 1)； - 运行程序，观察是否有显著的性能提升。
但这种方式显然是不科学、不合理的，例如上面的修改以很大的概率不会对程序的性能有可见的影响。在这个实验中，写出更快的代码不是目的，而是帮助大家熟悉性能分析的工具，然后做出针对性的优化。正如 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 倍。
其中一些值得注意的事项：
- 允许修改数据结构的定义和算法。
- 我们 (和其他 Labs 一样) 在编译时会开启
-O1优化开关。除了一些较为激进的优化 (如循环展开等) 外，编译器依然会尽可能地分析数据流、内联函数等方式优化你的代码。大家可以在 gcc 的手册中寻找-O1相关的优化，例如-fdefer-pop,-finline-functions-called-once等。 - 我们允许你做一些预处理，以及我们鼓励你使用预处理。但我们限制
sieve.c的大小不能超过 4096 字节。 - 我们实际运行的测试用例中，$n < 10^7$，因此你不必修改 $N$ 的定义。
2.2 代码获取与提交
Academic Integrity
从网上或别人那里复制几行代码非常简单——但你如果遵守 academic integrity，自己尝试完成，就会遇到巨大的困难 (尤其如果你没有试着用正确的工具、正确的方法诊断问题)。这是我们给你必要的训练。
请使用我们的
Makefile编译 (在实验目录中执行make)，确保 Git 记录完整。
在之前实验的 ics-workbench 中，在终端执行
git pull origin lab3
可以获得实验的框架代码。提交方法同之前的 Lab: 在实验的工作目录中执行 make submit。需要设置 STUID (学号) 和 STUNAME (中文姓名) 环境变量。
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 很多时候可以实现得更轻量：我们需要隔一段时间对程序的执行采样即可。例如如果我们希望了解哪个函数使用了最多的时间，大家可以想到如下的实现：
- 借助系统的机制，每秒给进程发送若干 (例如 100) 次 “中断”，中断到来后，会跳转到一个 “中断” 处理程序。
- 在 “中断” 处理程序中，我们遍历函数的调用栈，获得当前的调用链并记录。
- 程序执行完毕后，根据采样的得到的信息，就能推断出哪些函数 (近似) 消耗了多少时间。
对小程序来说这个机制当然没有什么大用处；但如果你的项目是数十、数百万行代码的项目，此时发现在某个特定的输入上出现了急剧的性能下降。如果这时候有 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 倍。大家可以根据观察到的统计数据，找到代码的性能瓶颈，并且做出相应的优化。