Lab2: Optimization for PA2 (PA2+性能优化实验)
小实验 (Labs) 是 ICS 这门课程里的一些小练习题，旨在结合课堂知识解决一些实际PA中的问题。PA本身以外的实验也依旧存在很多值得研究并付出努力的地方。这些练习也能够 有效帮助大家在完成PA过程中写出更优的实现。
- Deadline: 2025年11月30日23:59:59
1. 背景
性能调优是系统编程的一个重要组成部分。例如同学们在遇到 “Online Judge 提交 TLE” 以后，如果排除了死循环等逻辑问题，并且坚持算法/数据结构没有选错，就要开始性能调优。根据我们的了解，大部分同学先前性能调优的方法是 “随机调优法”：
- 观察程序，看到一些可能的性能优化点 (例如找到一个
i *= 2)； - 对程序进行一些功能等价的修改 (例如改成
i <<= 1)； - 运行程序，观察是否有显著的性能提升。
但这种方式显然是不科学、不合理的，例如上面的修改以很大的概率不会对程序的性能有可见的影响。在这个实验中，写出更快的代码不是目的，而是帮助大家熟悉性能分析的工具，然后做出针对性的优化。正如 D. E. Knuth 所说，“Premature optimization is the root of all evil”。
2. 实验要求
2.1 实验内容
大家在 PA2 中已经实现了一个可以正常运行马里奥的全系统模拟器 NEMU。然而你很快就会发现 NEMU 的性能并不理想。即使在你的真机上使用 ARCH=native 编译能够跑到几百 FPS，使用 NEMU 运行马里奥时可能只有十几甚至个位数的 FPS，玩起来相当恼人。
coremark 的跑分结果能够更加直观地展示这一点：
- native
Running CoreMark for 300000 iterations
2K performance run parameters for coremark.
CoreMark Size : 666
Total time (ms) : 10101
Iterations : 300000
Compiler version : GCC10.2.1 20210110
seedcrc : 0xe9f5
[0]crclist : 0xe714
[0]crcmatrix : 0x1fd7
[0]crcstate : 0x8e3a
[0]crcfinal : 0xcc42
Finished in 10101 ms.
==================================================
CoreMark Iterations/Sec 29700029.70
- NEMU (300x slower than native)
Welcome to riscv32-NEMU!
For help, type "help"
Running CoreMark for 10000 iterations
2K performance run parameters for coremark.
CoreMark Size : 666
Total time (ms) : 101891
Iterations : 10000
Compiler version : GCC10.2.1 20210110
seedcrc : 0xe9f5
[0]crclist : 0xe714
[0]crcmatrix : 0x1fd7
[0]crcstate : 0x8e3a
[0]crcfinal : 0x988c
Finished in 101891 ms.
==================================================
CoreMark Iterations/Sec 98144.10
你可能会觉得模拟器比真机更慢是天经地义的，但是 QEMU 的结果马上给了你沉重的一击：
- QEMU (5x slower than native, 60x faster than NEMU)
Running CoreMark for 300000 iterations
2K performance run parameters for coremark.
CoreMark Size : 666
Total time (ms) : 50956
Iterations : 300000
Compiler version : GCC10.2.1 20210110
seedcrc : 0xe9f5
[0]crclist : 0xe714
[0]crcmatrix : 0x1fd7
[0]crcstate : 0x8e3a
[0]crcfinal : 0xcc42
Finished in 50956 ms.
==================================================
CoreMark Iterations/Sec 5887432.29
看到这个结果，你可能马上就想抄起用在 Online Judge 上那一套随机调优法，凭感觉优化 NEMU 中的代码。但是不同于只有数百行的 OJ，完整的 PA 项目中有十万多行代码。并且默认开启的 -O2 编译选项已经帮大家做了相当多的优化了。而根据 阿姆达尔定律，即使你对某一段程序进行了上百倍的优化，如果这一段程序在原型执行时间中仅仅占比百分之三十，你最终提升的效果最多也只有百分之三十。
因此，我们需要一种更加科学的性能调优方法：先分析，后优化。在这个实验中，你需要使用 Linux 下的性能分析工具 perf，找出 NEMU 中的性能瓶颈，然后针对性地进行优化，最终使得 NEMU 的性能至少提升至 2.5 倍。
2.2 代码获取与提交
Academic Integrity
从网上或别人那里复制几行代码非常简单——但你如果遵守 academic integrity，自己尝试完成，就会遇到巨大的困难 (尤其如果你没有试着用正确的工具、正确的方法诊断问题)。这是我们给你必要的训练。
请使用我们的
Makefile编译 (在实验目录中执行make)，确保 Git 记录完整。
在 PA 仓库中，执行：
git commit --allow-empty -am "before starting lab2"
git checkout pa2
git checkout -b lab2
在 PA2 基础上创建新的分支。提交方法同 PA: 在 PA 的工作目录中执行 make submit。需要设置 STUID (学号)、STUNAME (中文姓名) 和 TOKEN (提交凭证) 环境变量。
成绩查看，拼接http://why.ink:8080/oj/ICS2025/LAB2/和你的Token。
2.3 评分与正确性标准
我们一共有 2 个评测程序，分别对应两个优化维度（我们的基准实现几乎没有性能优化）：
-
coremark：运行 CoreMark 基准测试，要求运行时间相比我们的基准实现至少提升至 1.5 倍。此测试主要考察 NEMU 计算性能的提升。 -
klib-bench：运行 klib-bench 基准测试，要求运行时间相比我们的基准实现至少提升至 2.5 倍。此测试主要考察 klib 库函数的性能提升。
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 函数就是性能瓶颈。换句话说，你在优化程序时，应该把主要精力放在 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
3.2 优化建议
在你使用 perf 定位到 NEMU 的性能瓶颈以后，接下来就需要对代码进行优化了。
如果你成功地为 NEMU 记录了 perf 日志，你会发现 NEMU 除了 exec_once 函数以外，居然还有大量的时间花在了另一个函数上。这个函数只有达成某个特定条件才会真正执行，本不应该被如此频繁地调用，进而导致了严重的性能问题。至于具体是哪个函数，我们就留给你使用 perf 去发现了。
对于这个函数的优化，我们建议你选择以下两个方向之一进行优化：
- 减少函数调用的次数。因为我们知道这个函数的进入条件只有很小概率会被满足，因此我们可以将这个函数的条件检查频率降低，例如设置一个全局的计数器，每隔 100 次函数才会检查一次条件，从而大幅度减少函数调用的次数。
- 化轮询为回调。我们不应该在每次执行时都检查一遍进入条件，而是等条件满足之后由操作系统主动通知我们这个条件已经被满足，从而避免频繁的条件检查。你可以参考使用这个函数注册当条件满足时被调用的回调函数。需要注意回调函数是并发的，有可能在 NEMU 正常执行的期间被触发，你需要仔细检查确保不会出现竞态问题。
完成这个优化之后，你应该能够看到 NEMU 的性能有了 1 倍左右的提升，并且能够通过第一个测试用例。
除了优化 NEMU （相当于提升 CPU 运行速度）以外，你还可以优化被运行的程序本身。受益于 Abstract Machine 的设计，你可以直接将马里奥编译到 native 架构上并继续使用 perf、ltrace 等工具进行性能分析，从而发现马里奥程序本身的性能瓶颈。为了简化，我们直接给出你下一个需要优化的性能瓶颈：klib 库函数。
klib 库在 PA 体系里对应真实世界中的 C 标准库 (libc)，它实现了很多常用的字符串处理、内存操作等函数。这些库函数的实现质量相当重要，并且不同 libc 之间的性能差异可以达到非常大，对真实世界中程序的性能也会产生可观的影响。马里奥游戏中就有相当一部分时间都花在了 memcpy 函数上。
因此，你需要对 klib 库中的 memcpy、strcmp、memset、memmove 等函数进行优化，具体测试内容可以参考 klib-bench。其中一个简单的优化方法是使用更宽的内存访问指令 (例如使用 uint32_t 代替 uint8_t 进行内存拷贝)，从而减少内存访问的次数，但是你需要注意非对齐内存访问的问题。你也可以参考一些成熟的 libc 实现 (例如 musl 或者 glibc)，看看它们是如何实现这些函数的。
完成这个优化后，你应该能够看到 klib-bench 的性能又有了 1 倍左右的提升，并且能够通过第二个测试用例。