Mdr-C-Tutorial

15. 测量、分析与优化 ​

在 wordfreq 项目的日常测试中，处理教材自带的微型样本 sample.txt 往往只需数毫秒；然而当负载切换为包含一百万单词的长文本时，程序耗时瞬间跃升至一秒以上。这一秒钟的算力究竟消耗在哪些环节？单凭直觉猜测往往会南辕北辙：开发者可能会急于将手写的大小写转换改写为查表操作，或者试图换掉 fprintf 的格式化调用；但费时费力重构之后，重新测试却往往发现总耗时几乎毫无改观。性能优化的科学路径要求我们坚决摒弃“拍脑袋猜瓶颈”的做法：必须遵循“先量化测量、再剖析热点（Profiling）、随后重构核心算法，最后才考量编译器优化与微基准（Microbenchmark）微调”的工程严密次序。

计算机先驱 Donald Knuth 在 1974 年发表的经典论著中曾写道：程序员常常在非关键代码路径上耗费大量心血琢磨速度提升，这些局部折腾在综合考虑系统调试成本与长期可维护性后往往得不偿失；在约 97% 的日常代码场景中，我们理应忘掉那些微不足道的细枝末节，“过早优化是万恶之源”。但在这段警句的同一语境下，他也紧接着指出：绝不应放过那真正关乎全局性能的 3% 关键机会。这两项主张看似矛盾，合起来恰恰奠定了本章所倡导的方法论体系：先借助测量手段精准圈出那至关重要的 3% 瓶颈热点，进而集中算力与精力进行深层突破。

在本章的演进实践中，我们将为 C 语言程序建立起一套可复现的基准性能测量框架：固定数据输入、固定编译参数并多次取中位数剔除系统抖动；通过系统 time 工具与程序内单调时钟分别获取墙钟时间与计算耗时；借助 gprof 采样剖析精准锁定热点瓶颈；利用算法复杂度分析指导数据结构的根本升级；审视编译器优化级别在执行耗时与二进制体积间的权衡抉择；并剖析微基准测试中极为常见的各种测量陷阱与防范技巧。

文中所有计时数字均来自同一台基准实验机：Windows 11（10.0.26300），Intel Core Ultra X7 358H，MinGW-w64 GCC 13.2.0（UCRT），bash 5.3.9。在不同硬件与系统环境下运行，绝对物理时间会产生波动，但核心性能比率与工程判断方法保持一致。本章涉及的代码存放在 code/开发与工程基础/15_测量_分析与优化/wordfreq/，其中 v0.1 源自第 14 章快照，v0.2 为本章优化完成后的终态版本。

1. 先定目标和条件 ​

脱离了具体运行工况的“快”与“慢”在工程上没有任何讨论意义。针对同一个 wordfreq 词频程序，处理一万单词与处理一百万单词所呈现的性能特征存在质的断层；而即便面对同一份测试输入，基于 -O0 与 -O2 构建出的产物耗时也常常相差数倍。因此，在开启任何优化实验之前，必须首先严密界定测量目标与基准环境。

在系统性能工程中，最常关注的核心量化指标主要有如下三类：

指标含义怎么取
墙钟时间 (wall-clock time)从进程启动到退出实际过去的时间bash 的 time、Measure-Command、程序内的单调时钟
CPU 时间 (CPU time)进程占用处理器的时间bash 的 time 的 user 与 sys 两列、clock()
内存占用峰值或总量任务管理器、/usr/bin/time -v 之类的外部工具

在评估程序吞吐时，墙钟时间往往是终端用户最直接感知的金标准。只有当测量数据出现显著的离群偏差时，才需进一步拆解 CPU 时间在用户态（user）与内核态（sys）的分布比例，推导进程是否存在因 I/O 等待引起的空转。

基准测试的编译配置应当始终对齐面向生产的 Release 规格，即开启标准优化并保留调试信息：

sh
gcc -std=c17 -O2 -g -Iinclude src/token.c src/counter.c src/report.c app/main.c -o build/wordfreq

参数中的 -O2 能够让生成的机器指令无限贴近最终交付给用户的真实状态；追加 -g 则确保剖析工具能够从符号表中解析出精准的函数签名与源码行号，其对运行吞吐几乎没有额外拖累。切忌拿未优化的 -O0 调试版本进行性能推导，其数值在生产评估中没有任何参考价值。

另一项至关重要的实验准则是必须将标准输出重定向到空设备（如 /dev/null 或 PowerShell 的 $null），否则控制台在逐行滚动终端字符时所引发的 I/O 延迟，会瞬间喧宾夺主并彻底淹没算法本身的真实运算开销。同时，输入样本、编译器小版本号、编译选项以及宿主 CPU 型号均需白纸黑字完整归档，以备未来回溯比对。

2. 可重复的输入 ​

性能基准测试最忌讳输入负载的动态漂移。直接从互联网下载小说或语料库看似贴近现实，但在工程测量中存在硬伤：既难以灵活横向缩放测试规模，也难以在跨团队协作或自动化 CI 中保证跨环境逐字节一致。

规范的工程做法是构建一个可控且可严格复现的数据生成器。在 tools/gen_words.c 中，我们实现了一个基于固定种子的伪随机文本生成器：通过参数控制不同单词总数 M 与目标生成单词数 N，并利用双随机数取较小值的方式模拟自然语言中高频词聚集的偏斜长尾分布（Zipf-like distribution）。生成器核心逻辑如下：

c
#define MAX_WORDS 100000
#define MIN_WORD_LEN 4
#define MAX_WORD_LEN 11

static uint32_t rng_state;

/* 线性同余生成器：参数取 Numerical Recipes 的一组常数 */
static uint32_t next_random(void) {
    rng_state = rng_state * 1664525u + 1013904223u;
    return rng_state;
}

static size_t bounded(size_t bound) {
    if (bound == 0) {
        return 0;
    }
    return (size_t)(next_random() % (uint32_t)bound);
}

在生成算法中，第 i 个单词的拼写完全由伪随机数发生器的初始种子和序号决定，与总生成词数 N 解耦。因此 gen_words 1000 10000 42 生成的 80053 字节文件，其剔除末尾换行后的全部内容，严格构成了更大规模 gen_words 1000 100000 42 的标准前缀。抽词逻辑利用两组独立状态，优先选取靠前序号的词项，真实拟合了自然语言的统计特征。当设置总词数 N 为一百万时，在生成的 998 个独立词项中，最高频词出现达 2088 次。

sh
gcc -std=c17 -O2 -Iinclude tools/gen_words.c -o build/gen_words
build/gen_words 1000 10000 42 > build/words-10000.txt
build/gen_words 1000 100000 42 > build/words-100000.txt
build/gen_words 1000 1000000 42 > build/words-1000000.txt

我们可以通过系统命令验证其逐字节可复现性：

zsh - 同一组参数生成两次
console
$ build/gen_words 50 30 42 > a.txt
$ build/gen_words 50 30 42 > b.txt
$ cmp a.txt b.txt && echo identical
identical
$ build/gen_words 50 30 43 > c.txt
$ cmp a.txt c.txt
a.txt c.txt differ: char 1, line 1

针对不同规模参数，三个基准样本的体积分别稳定在 80053 字节、800385 字节与 8004233 字节（平均约每个单词 8 字节）。利用微型参数 50 30 42 检视其生成的实际文本形态：

zsh - build/gen_words 50 30 42
text
crqvani kbyngdm klerijapqtw ufwjk ufwjk qtevuhc efgdirs efgdirs klerijapqtw klerijapqtw sdonatm sdonatm ibqvqza ufwjk ufwjk ktwpeng ktwpeng spsrilk shsfczy spuxapk spuxapk slydepk shsfczy shsfczy ahmzkle ahmzkle sdonatm sdonatm qhadane slcxgzm

该生成器执行效率极高：生成百万级词量仅耗时约 0.4 秒。它只在测试准备阶段离线执行一次，绝不会对后续的算法计时造成任何干扰。

3. 计时 ​

3.1 外部计时 ​

利用 Shell 内建的 time 命令是获取粗粒度性能反馈最快捷的入口，它在目标进程退出后会同步输出三项核心时间指标：

zsh - time build/wordfreq
console
$ time build/wordfreq -n 10 build/words-1000000.txt > /dev/null

real    0m0.088s
user    0m0.000s
sys     0m0.015s

各指标的具体内涵如下：

  • real：从命令发出到进程终止期间，人类在现实世界中经历的物理墙钟时间；
  • user：进程自身的机器指令在 CPU 用户态实际消耗的处理器周期折算时间；
  • sys：操作系统内核代表该进程执行底层系统调用（如处理文件读取、页表分配、I/O 中断等）所占用的处理器时间。

对于纯粹由 CPU 主导的计算密集型逻辑，理想状态下 real 应高度逼近 user + sys 的累加值。若 real 显著大幅超越二者之和，通常表明进程大部分时间陷入了空闲等待，典型如阻塞于磁盘顺序读取、等待网络套接字数据或因宿主系统负载过重而遭遇调度挂起。

Git Bash 的 time 测不准原生 Windows 程序

在 Git Bash 环境下运行由 MinGW 编译生成的原生 Windows PE 可执行文件（.exe）时，user 和 sys 往往会异常显示为 0，且 real 数值通常略微偏大。这是由于此时记录时间的是处于 POSIX 模拟层的 bash 进程，原生子进程内部的精细 CPU 记账并未能穿透回传。粗略观察趋势时可参考 real 数值，若追求严谨的量化数据，应采用下一节介绍的程序内高精计时，或在 PowerShell 环境中执行基准测试。

在原生 Windows 终端中，PowerShell 的 Measure-Command cmdlet 能够提供更为准确的外部耗时度量：

PowerShell - Measure-Command
powershell
PS> (Measure-Command { .\build\wordfreq.exe -n 10 build\words-1000000.txt > $null }).TotalSeconds
0.0864399

必须清醒认识到，任何从外部包裹的黑盒计时手段都附带固定的系统级前置成本：包括操作系统的进程创建调度、PE/ELF 二进制加载、动态链接库初始化以及 Shell 建立进程间管道等。这份固有成本与输入文本的规模完全无关。我们可以通过向程序传入一个空文件来测量出这份固化底噪：

zsh - 空文件的耗时
console
$ : > build/empty.txt
$ time build/wordfreq -n 10 build/empty.txt > /dev/null

real    0m0.022s

在上述输出中，针对百万级词量的 0.088 秒总时间里，实际上约有 0.022 秒耗费在进程拉起的固化启动开销上，分配给内部算法计算的仅有约 0.066 秒。当数据负载极大时，这份固定底噪在总体中的占比相对微弱；但若测试规模收缩至 10^4 词量级，环境底噪甚至会数倍于实际运算时间，导致外部黑盒测量彻底失真并掩盖算法层面的细微差异。

3.2 程序内计时 ​

若需彻底隔离进程初始化底噪、精准量化代码核心模块的真实耗时，应当在 C 源码中嵌入单调时钟（Monotonic Clock）：

c
#define _POSIX_C_SOURCE 200809L
#include <time.h>

static double now_seconds(void) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9;
}

为何必须指定 CLOCK_MONOTONIC？这是因为日常使用的日历时间（如标准库中的 time() 或 C11 的 timespec_get）随时可能受到 NTP 自动化网络对时校准、系统时钟回拨、夏令时切换等外部干预，其时间轴并不是严格单调的；而传统的 clock() 测量的是累计占用的 CPU 周期，其在包含多核并发或线程休眠的场景下统计口径并不等同于物理耗时。CLOCK_MONOTONIC 确保时钟只增不减且步进频率绝对稳定，是系统级精密时间度量的唯一通用标准。在现代 MinGW-w64 的 UCRT 运行时下，clock_gettime 已得到原生支持，可跨平台安心调用。

我们将 now_seconds() 显式插桩在 main 函数的核心处理逻辑前后，并向标准错误流 stderr 输出计算差值。针对百万词量样本，连续运行五次观察其稳定性：

zsh - 带程序内计时的 wordfreq
console
$ for i in 1 2 3 4 5; do build/wordfreq-timed -n 10 build/words-1000000.txt > /dev/null; done
elapsed 0.0707 s
elapsed 0.0702 s
elapsed 0.0694 s
elapsed 0.0696 s
elapsed 0.0678 s

五组测试样本紧密收敛在 0.0678 秒至 0.0707 秒之间，中位数稳定在 0.0696 秒；相较外部计时减少的约 0.018 秒恰好与进程初始化底噪完美吻合。同时，外部计时的抖动幅度远甚于程序内插桩：外部连续测试时 real 数值在 0.088 到 0.095 秒间跳动，环境波动可达 7 毫秒，而程序内测量的抖动幅度始终被牢牢压制在 1 毫秒以内。

单选

在 Git Bash 里对 MinGW 编译的 wordfreq 运行 time，得到 real 0m0.088s、user 0m0.000s、sys 0m0.015s。下列说法正确的是：

real 0.088s，user 0.000s，sys 0.015s：程序在用户态几乎没花时间
real 远大于 user + sys，说明程序大部分时间在等待
应把三项相加作为程序的总耗时
user 为 0 是 Git Bash 的 time 对原生 Windows 程序测不准，实际计算时间要看程序内计时

3.3 多次运行取中位数 ​

在基准性能工程中，依赖单次运行的读数往往无法得出可信结论。

单次运行的数字混杂了调度延迟、其他进程的干扰、磁盘缓存是否命中。至少运行 5 次，报告中位数，同时记下最小值和最大值；最大值离中位数很远，说明这次测量受到了干扰，应当在安静的机器上重测，不要把它一起平均进去。

在统计学上选用中位数（Median）而非算术平均数（Mean），是因为在真实的操作系统中，后台守护进程的偶尔调度插队或瞬间缺页中断会大幅拉长单次测试的耗时，算术平均值极易被这种偶发长尾离群值严重劣化，而中位数能从容免疫此类单点波动。

在自动化基准脚本 tools/bench.sh 中，我们以结构化的方式将测试条件固化下来：固定构建参数、预先扣除环境底噪基线，并执行 5 轮采样计算中位数：

sh
#!/bin/sh
# wordfreq 的基准脚本：固定输入、固定选项，对三种规模各跑 5 次，取 real 时间的中位数。
#
#   sh tools/bench.sh
#
# 外部计时包含进程启动与 shell 开销，先用一个空文件量出这份固定成本，
# 读数时从各规模的耗时里减去，才能看出真正用于计算的时间。
set -eu

cd "$(dirname "$0")/.."

BUILD=build-bench
CC=${CC:-gcc}
CFLAGS="-std=c17 -O2 -g -Iinclude"

mkdir -p "$BUILD"
$CC $CFLAGS tools/gen_words.c -o "$BUILD/gen_words"
$CC $CFLAGS src/token.c src/counter.c src/report.c app/main.c -o "$BUILD/wordfreq"

for n in 10000 100000 1000000; do
    "$BUILD/gen_words" 1000 "$n" 42 > "$BUILD/words-$n.txt"
done
: > "$BUILD/empty.txt"

# 运行 5 次，打印 real 时间的中位数（毫秒）
median_ms() {
    times=""
    for i in 1 2 3 4 5; do
        start=$(date +%s%N)
        "$@" > /dev/null
        end=$(date +%s%N)
        times="$times $(( (end - start) / 1000000 ))"
    done
    printf '%s\n' $times | sort -n | sed -n 3p
}

baseline=$(median_ms "$BUILD/wordfreq" "$BUILD/empty.txt")

echo "build:    $CFLAGS"
echo "baseline: ${baseline} ms  (empty input: process startup, shell and timer overhead)"
printf '%-9s %9s %9s\n' words total net
for n in 10000 100000 1000000; do
    total=$(median_ms "$BUILD/wordfreq" -n 10 "$BUILD/words-$n.txt")
    printf '%-9s %7s ms %5s ms\n' "$n" "$total" "$((total - baseline))"
done

在同一台负载正常的机器上连续执行两次该基准脚本：

zsh - sh tools/bench.sh
text
build:    -std=c17 -O2 -g -Iinclude
baseline: 34 ms  (empty input: process startup, shell and timer overhead)
words         total       net
10000          35 ms     1 ms
100000         43 ms     9 ms
1000000       114 ms    80 ms
text
build:    -std=c17 -O2 -g -Iinclude
baseline: 33 ms  (empty input: process startup, shell and timer overhead)
words         total       net
10000          35 ms     2 ms
100000         43 ms     9 ms
1000000       100 ms    67 ms

对比这两次输出，即使在同一台机器上运行同一组代码，针对百万词量的净计算时间两次依然出现了 13 毫秒的浮动（80 毫秒对比 67 毫秒），几乎占到程序自身真实计算时间的五分之一。这是由于外部脚本调用的 date 命令、Subshell 进程的生成本身就携带微小的抖动。而在面对一万词的极小输入时，净时间更是在 1 毫秒与 2 毫秒间跳动，根本无法精确度量。由此可以得出清晰的结论：外部脚本适合用于快速把握系统级宏观趋势；而面对微小改动的严谨比对，必须依赖程序内精准的高精单调时钟。

4. 找热点 ​

明确程序存在性能瓶颈只是第一步，知道程序总体耗时长，并不等同于能够精准判断每一毫秒究竟消耗在哪个具体函数或循环中。GNU 工具链自带的采样与调用图分析器 gprof，是 C 语言开发者排查性能热点最经典的工具。其使用流程分为标准的三部曲：注入 -pg 编译目标、正常运行可执行程序以落盘 gmon.out 剖析数据、最后调用 gprof 命令解析生成结构化报表。

zsh - 带 -pg 构建并运行 v0.1
console
$ gcc -std=c17 -O2 -g -pg -no-pie -Iinclude src/*.c app/main.c -o build/wordfreq_pg
$ build/wordfreq_pg -n 10 build/words-1000000.txt > /dev/null
$ ls gmon.out
gmon.out
$ gprof -b build/wordfreq_pg gmon.out

MinGW 上不加 -no-pie 会得到空报告

Windows 上的 GCC 默认生成位置无关可执行文件 (PIE)。这种可执行文件加载到随机地址，gprof 采样时算出的地址对不上符号表，报告里只有表头。加上 -no-pie 关掉它，才有数据。Linux 上的 GCC 通常不需要这个选项。

在调用参数中，追加 -b 可以精简输出，仅打印平面剖析与调用图，略去冗长的格式说明手册。我们观察 v0.1 在 500 万单词压力下的平面剖析（flat profile）：

zsh - gprof 平面剖析
text
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ns/call  ns/call  name
 56.76      0.63     0.63  5000000   126.00   126.00  wf_counter_add
 33.33      1.00     0.37                             strcmp
  5.41      1.06     0.06                             _mcount_private
  3.60      1.10     0.04  5000002     8.00     8.00  wf_tokenizer_next
  0.90      1.11     0.01                             __fentry__
  0.00      1.11     0.00        2     0.00     0.00  wf_report_print
  0.00      1.11     0.00        1     0.00     0.00  wf_counter_create
  0.00      1.11     0.00        1     0.00     0.00  wf_counter_destroy
  0.00      1.11     0.00        1     0.00     0.00  wf_counter_top
  0.00      1.11     0.00        1     0.00     0.00  wf_tokenizer_init

报表各列的统计维度如下：

列含义
% time这一项占总采样时间的比例
self seconds这个函数自己的代码花掉的秒数，不含它调用的函数
calls被调用次数；不显示数字的是没被插桩的函数（如库函数）
self ns/call单次调用平均耗时

从报表中可以清晰提炼出核心线索：wf_counter_add 独占了 56.76% 的采样周期，在 500 万次调用中单次平均耗时约 126 纳秒；排在第二位的 strcmp 占用了 33.33% 的周期，二者合计消耗了超过 90% 的执行时间！strcmp 的 calls 列为空，是因为它来自 UCRT 动态链接库，在编译期未被 -pg 探针插桩。而分词函数 wf_tokenizer_next 仅占 3.6%，其余逻辑几乎不占可感知的比例。至于 _mcount_private 与 __fentry__，纯粹是 -pg 框架用于函数入口记账所引入的自身开销，在正常的发布版本中并不存在。

调用图（call graph）进一步还原了函数层级调用拓扑：

同一次运行的调用图
text
			Call graph

granularity: each sample hit covers 4 byte(s) for 0.90% of 1.11 seconds

index % time    self  children    called     name
                                                 <spontaneous>
[1]     60.4    0.00    0.67                 count_stream [1]
                0.63    0.00 5000000/5000000     wf_counter_add [2]
                0.04    0.00 5000001/5000002     wf_tokenizer_next [5]
                0.00    0.00       1/1           wf_tokenizer_init [12]
-----------------------------------------------
                0.63    0.00 5000000/5000000     count_stream [1]
[2]     56.8    0.63    0.00 5000000         wf_counter_add [2]
-----------------------------------------------
                                                 <spontaneous>
[3]     33.3    0.37    0.00                 strcmp [3]
-----------------------------------------------
                0.00    0.00       1/5000002     main [7]
                0.04    0.00 5000001/5000002     count_stream [1]
[5]      3.6    0.04    0.00 5000002         wf_tokenizer_next [5]
-----------------------------------------------
                0.00    0.00       1/5000002     wf_tokenizer_next [5]
                0.00    0.00       1/1           wf_counter_create [8]
                0.00    0.00       1/1           wf_counter_top [10]
                0.00    0.00       1/1           wf_report_print [11]
                0.00    0.00       1/1           wf_counter_destroy [9]

调用图的数据同样十分明确：在负责驱动词频统计的 count_stream 累计耗时中，wf_counter_add 贡献了绝大部分开销。<spontaneous> 标记代表采样器未能沿调用栈向上回溯到被插桩的父函数。

gprof 指明的热点与直觉猜测截然不同：系统的瓶颈牢牢定格在词频计数器的检索比对上，而非分词器解析或最后的排版打印。这就是先量化剖析的价值。

在工程实践中依赖 gprof 定位热点时，有两处内在局限需要提前厘清。

它只能统计被插桩的代码。 如果耗时集中在没有加入 -pg 选项编译的第三方动态库或系统运行库中，那部分开销便无法被采样器记录，甚至在报告中完全隐形。示例代码 code/开发与工程基础/15_测量_分析与优化/gprof_dll/loop.c 将全部计算逻辑置于一个包含 400 万次 sprintf 调用的紧凑循环中：

zsh - 时间全在动态库里
console
$ gcc -std=c17 -O2 -pg -no-pie loop.c -o loop
$ time ./loop > /dev/null

real    0m0.211s
$ gprof -b loop gmon.out
Flat profile:

Each sample counts as 0.01 seconds.
 no time accumulated

外部墙钟耗时达到 0.211 秒，gprof 给出的报告却显示「no time accumulated」。原因在于 sprintf 驻留在系统的 UCRT 动态库内，该动态库在编译打包时并未开启 -pg 插桩。连续执行十次测试，绝大多数轮次均呈现这种空结果；仅有个别轮次偶发性地捕获到一两个样本，将其归算在 sprintf、__stdio_common_vsprintf 或 main 名下，采样累计时间仅有 0.02 秒，不足真实物理耗时的十分之一。

wordfreq 能够将 strcmp 的耗时捕获进报告，是因为 MinGW 环境在生成可执行目标文件时为导入的 strcmp 构建了跳转跳板（jmp *__imp_strcmp），指令指针落入跳板时碰巧能与符号名对应。如果缺乏这种跳转跳板机制，外部动态库代码的执行时间将从报告中完全消失，其他被插桩函数的耗时占比也会被系统性高估。验证剖析报告是否存在严重遗漏的有效方法，是将 gprof 汇报的累计采样时间与外部工具 time 测得的 real 墙钟时间进行横向核对；若两者相差数倍乃至数量级，即表明有大段系统调用或动态库调用被漏记。

它的采样精度较粗。 报告表头的「Each sample counts as 0.01 seconds」仅为标称换算基准。实际采得的有效样本量受限于操作系统调度与剖析器获取控制权的频率，以及采样触发瞬间指令指针是否恰好停留在保留符号的翻译单元内。在同一台机器上针对一百万词输入连续测定六轮，墙钟耗时始终稳定在 1.13 至 1.19 秒之间，而 gprof 报告里汇总的采样时间却在 0.11 到 0.20 秒之间大幅摆动，strcmp 占总时间的比例也随之在 18% 至 50% 间跳跃。这样的分辨率足以协助开发者识别“谁是首要耗时大户”，但难以用于微调并对比两个细微改动之间的毫厘之差。若需要更细腻的分辨率，除了扩充测试数据量和延长运行周期，还可以引入更为通用的系统级采样剖析工具。

现代采样剖析器（如 Linux 下的 perf、Windows 平台的 Windows Performance Analyzer 以及 macOS 的 Instruments）通常基于硬件性能计数器或定时器中断，以极高频率打断执行流并记录调用栈快照。在 Linux 生态中，通常使用 perf record 捕获采样数据，配合 perf report 展开层级视图；当调用关系复杂时，还可以导出堆栈并绘制火焰图（Flame Graph）：

console
$ perf record -F 99 -g ./build/wordfreq -n 10 build/words-1000000.txt
$ perf report --stdio
$ perf script | stackcollapse-perf.pl | flamegraph.pl > profile.svg

当前测试平台未配备 perf，上述命令与典型用法遵循系统性能领域的标准实践与手册指引，这里不赘述其终端输出。

将整个测量、分析与决策的工程闭环梳理成如下流程：

只有建立在可重复测量的数据基础之上，快慢的评判才具备客观价值；定位到具体的执行热点，才能明确代码修改的主攻方向；改动完成后首先回归既有功能测试，确认程序行为严格无误，再借助同等条件下的基准测量验证性能收益。遵循这套闭环，能有效避免盲目猜测带来的代码负优化。

5. 先改算法 ​

热点定位明确之后，面临的抉择是如何下手改造。面对密集的字符串比较，直觉反应往往是将 strcmp 替换为手写的展开内联比对，或是直接开启 -O3 期待编译器自动向量化。然而这两项尝试针对的都只是执行过程中的常数因子，v0.1 的根本症结并不在常数项，而在于整体算法的时间复杂度。

优化的先后顺序应当由预期收益的量级决定：将 O(N⋅M) 降低为 O(Nlog⁡M) 能带来随规模扩张而显著放大的结构性收益；常数因子的微调通常最多把同一段逻辑加速数倍。数据规模越大，两者的效益差距越为悬殊。因此在着手优化常数项之前，必须先借助复杂度分析确认算法层面的瓶颈。

在 v0.1 的实现中，每向计数器追加一个单词，程序都必须将当前已收录的所有条目从头到尾线性扫描一遍。假设处理的总单词数为 N，其中互不相同的去重词汇数为 M，平均每次检索需要检查约 M/2 个条目，总比较次数大致在 N⋅M/2 这一量级。在实际语料中，虽然词汇去重后的规模随着输入文本长度呈现亚线性增长，但一旦词表规模扩大，这个乘积所代表的计算量将迅速攀升。以同一批总计 105 个单词的输入文本为例，若仅调整词表的多样性：当词表大小为 995 时，大约发生 5×107 次比对；而当词表扩充到 46058 时，比对次数陡增至 2.3×109 次，理论计算量扩大了近 46 倍。实测耗时也由 0.113 秒飙升至 6.097 秒，耗时增长了 54 倍（详见本节后文的数据对比表）。这种数量级的计算膨胀，显然无法通过在微观层面微调单次比较开销来弥补。

稳健的解法是重塑底层数据结构。v0.2 保证底层动态数组始终按照单词字典序升序排列，检索与插入位置的定位均改用二分查找（Binary Search）；当发现新词时，借助标准库 memmove 将后续元素整体后移腾出插槽：

c
/* 在有序数组中找 word 应当插入的位置：第一个不小于 word 的元素下标 */
static size_t lower_bound(const wf_counter *c, const char *word) {
    size_t lo = 0;
    size_t hi = c->size;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (strcmp(c->items[mid].word, word) < 0) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

int wf_counter_add(wf_counter *c, const char *word) {
    size_t pos = lower_bound(c, word);
    if (pos < c->size && strcmp(c->items[pos].word, word) == 0) {
        c->items[pos].count++;
        return 0;
    }
    /* ……扩容、复制单词，然后用 memmove 腾出位置 */
}

如此一来，单词检索的总比较次数由原本的 N⋅M/2 锐减至 N⋅log2⁡M。一百万词的测试输入中总共仅包含 998 个独立词汇，log2⁡(998)≈10，理论比对次数直接从 5×108 压缩到 107 量级；词表越庞大，两者的计算量鸿沟就越惊人。虽然插入新词时调用的 memmove 会产生内存搬运开销，但在独立词表规模有限的场景下，这笔开销远低于海量线性比较的代价。

❌ v0.1 线性查找
c
static struct item *find_entry(const wf_counter *c, const char *word) {
    for (size_t i = 0; i < c->size; i++) {
        struct item *e = &c->items[i];
        if (strcmp(word, e->word) == 0) {
            return e;
        }
    }
    return NULL;
}
✅ v0.2 二分查找
c
static size_t lower_bound(const wf_counter *c, const char *word) {
    size_t lo = 0;
    size_t hi = c->size;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (strcmp(c->items[mid].word, word) < 0) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

值得注意的是，对外暴露的公共头文件与接口定义完全没有发生任何改动。由于在第 7 章中已将 wf_counter 封装为不透明指针（Opaque Pointer），结构体布局 struct wf_counter 仅在 counter.c 内部私有定义，因此无论底层存储从无序切换为有序，还是在实现中引入辅助函数 lower_bound，上层调用方代码均完全无感知。这也解释了为何在 v0.1 到 v0.2 的版本演进中，业务入口 app/main.c 与输出排版 report.c 在代码层面保持着逐字节的一致。此前在第 11 章构建的三组自动化测试直接运行即可全部通过：

zsh - ctest --test-dir build
text
Test project .../build
    Start 1: token
1/3 Test #1: token ............................   Passed    0.04 sec
    Start 2: counter
2/3 Test #2: counter ..........................   Passed    0.03 sec
    Start 3: e2e
3/3 Test #3: e2e ..............................   Passed    0.06 sec

100% tests passed, 0 tests failed out of 3

在改动算法核心之前完备测试用例，并在重构后立即执行回归测试以证明外在行为完全等价，是工程优化得以安心落地的基石。

两个版本在同一台机器、同一组输入上的程序内计时（各 5 次取中位数，单位秒）：

单词数v0.1v0.2加速比
100000.01080.00119.8
1000000.11030.007814.1
10000001.12860.069616.2

测量结果与渐近复杂度的理论推导高度吻合：v0.1 的耗时大体随单词总量 N 呈线性增长（数据规模扩大十倍，耗时也增加约十倍）；v0.2 同样呈现线性增长趋势，但常数项缩小了整整一个数量级以上，并且加速比随着数据规模的攀升而持续扩大。这正体现了二分查找消减与去重词表规模 M 相关开销的威力和价值。

进一步观察固定单词总数 N、仅调整去重词汇数 M 的对照实验，可以更直观地看清两者的性能分水岭。这里采用总词数同为 105、但词表密度各异的三份语料展开对比：

不同单词数v0.1（秒）v0.2（秒）加速比
9950.11280.008014.1
94551.05160.016962.2
460586.09740.132246.1

去重词汇量越大，v0.1 的性能衰退越剧烈（从 995 词膨胀至 46058 词时，耗时激增 54 倍，与理论 N⋅M/2 预测的 46 倍增长基本吻合）；而切换为有序数组二分查找的 v0.2，耗时仅增长了约 17 倍。二分查找所需的比对次数仅随 log2⁡M 缓慢爬升（log2⁡(46058)/log2⁡(995)≈1.56），v0.2 额外产生的增长主要来源于插入罕见词时通过 memmove 平移内存以及离散访问引发的 CPU 缓存失效代价。这组数据清晰地印证了算法在性能优化中的决定性作用：同一套程序，在数据规模未变、仅词汇多样性扩大的情况下，v0.1 的执行时间便跌落了五十余倍。

单选

gprof 显示 v0.1 有一半时间花在 wf_counter_add 的线性查找上，输入越大、词表越大越明显。首要的优化方向是：

把 strcmp 换成手写的循环比较，省掉函数调用开销
用 -O3 重新编译，让编译器向量化查找过程
把线性查找换成二分查找，把每次查找的比较次数从 M/2 降到 log2(M)
把 wf_entry 里的 count 从 size_t 改成 unsigned int，让数组更紧凑

在算法复杂度降级之后，剩下的时间消耗在哪里？在 tools/gen_words 生成的一百万词标准测试集上，v0.2 的程序内实测总耗时约为 0.0696 秒。经过独立拆解测算，读取 8 MB 文本文件耗时约 0.004 秒，字符流分词耗时约 0.0043 秒，这两项基础 I/O 与解析开销累计不足 0.01 秒。此时进一步实施常数级性能调优才具有实际意义。而接下来的调优抓手，依然需要通过剖析器重新测量新的性能热点。在一百万词输入上重新执行 gprof 采样，得到的平面剖析报告如下：

zsh - v0.2 在 10^6 词上的平面剖析
text
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ns/call  ns/call  name
 50.00      0.01     0.01  1000000    10.00    10.00  wf_counter_add
 50.00      0.02     0.01                             __fentry__
  0.00      0.02     0.00  1000002     0.00     0.00  wf_tokenizer_next
  0.00      0.02     0.00        1     0.00     0.00  wf_counter_create
  0.00      0.02     0.00        1     0.00     0.00  wf_counter_destroy
  0.00      0.02     0.00        1     0.00     0.00  wf_counter_top
  0.00      0.02     0.00        1     0.00     0.00  wf_report_print

随着程序执行速度大幅提升，采样周期内落入目标代码的时钟滴答急剧减少：整轮运行全程仅采得 2 个有效样本，其中 1 个落在 wf_counter_add，另 1 个则落在 -pg 编译器生成的追踪探针 __fentry__ 内部。这样的样本量显然失去了统计信度。为了让剖析器获得足够清晰的分辨率，需要将输入规模扩增至 2×107 个单词，将单次运行时间拉长到 1.53 秒：

zsh - v0.2 在 2×10^7 词上的平面剖析
text
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ns/call  ns/call  name
 50.79      0.32     0.32 20000000    16.00    16.00  wf_counter_add
 34.92      0.54     0.22                             _mcount_private
  6.35      0.58     0.04                             __fentry__
  3.17      0.60     0.02 20000002     1.00     1.00  wf_tokenizer_next
  3.17      0.62     0.02                             strcmp
  1.59      0.63     0.01                             count_stream
  0.00      0.63     0.00        1     0.00     0.00  wf_counter_create
  0.00      0.63     0.00        1     0.00     0.00  wf_counter_destroy
  0.00      0.63     0.00        1     0.00     0.00  wf_counter_top
  0.00      0.63     0.00        1     0.00     0.00  wf_report_print
  0.00      0.63     0.00        1     0.00     0.00  wf_tokenizer_init

放大测试规模后，热点分布重新变得清晰：wf_counter_add 依然占据了约一半的自耗时，而 strcmp 和分词逻辑各自回落到 3% 左右。值得关注的是，插桩开销 _mcount_private 与探针 __fentry__ 合计占去了 40% 的运行时间。这两项均属于 -pg 插桩代码在每次函数入口记账的额外税收，在正式构建中并不存在。高达 2×107 次计数操作对应着等量的记账探针调用，调用越密集，这笔插桩开销就越显著。若在心智模型中剔除这部分测量伴生的干扰开销，wf_counter_add 在实际生产构建中的纯耗时比重会显著高于 50.79%。

v0.2 虽然借助二分查找将比对次数成功压制在 log2⁡M，但每次插入新词仍然需要维护连续动态数组：复制字符串对象、触发动态扩容、以及通过 memmove 平移已有条目。这些正是当前残留开销的聚集地。如果在此基础上追求进一步的极限突破，需要再次重构数据结构——例如采用散列表（Hash Table）或字典树（Trie）将单次查找均摊降低至接近常数级复杂度，不过这涉及到哈希冲突消解与指针跳转等更深入的设计考量，属于后续数据结构篇章探讨的主题。

关于二分查找算法的边界处理与标准库 qsort 的深度实践，请参阅查找与选择。

6. 编译器优化 ​

算法策略敲定后，工程优化的下一环是合理选用编译器优化级别。以同一套 v0.2 源码为基础，在 MinGW-w64 GCC 环境下分别启用五个标准优化级别进行编译，在 106 词规模的输入集上记录程序内耗时（5 轮测量取中位数）以及生成的可执行文件 text 段代码尺寸：

选项中位数（秒）text 段（字节）说明
-O00.095218828关闭优化，严格保留调试符号与对象映射
-O10.068417176启用基础优化，精简指令并引入寄存器分配
-O20.069817472工业界发布构建的推荐基准，兼顾速度与代码体积
-O30.070717464激进优化，开启自动循环向量化与更大幅度的函数内联
-Os0.072016960尺寸优先，禁用可能导致代码膨胀的展开与重排

在这套测试案例中，-O1 便已收割了绝大多数优化红利；-O1、-O2 与 -O3 之间的微小数值差异完全处于系统调度的测量噪声范围之内（在另一轮相同环境的实测中，三者的中位数分别为 0.0685、0.0679 与 0.0689 秒，先后位次再次发生微调）。-O3 未能展现出显著优势，原因在于其核心手段主要集中在针对连续紧凑内存循环的自动向量化（SIMD），而 wordfreq 当前的执行瓶颈（二分查找的区间折半、逐字节字符串比对、以及离散的内存插入）充斥着数据依赖分支与非连续寻址，缺乏能够展开并行向量操作的规整循环。而 -Os 虽然使 text 段微缩了约 3%，但代价是运行时间退步约 3%；对于一般的桌面或服务器应用而言，这微乎其微的代码尺寸收益通常并不划算，但在资源受限的嵌入式微控制器固件场景中则具有实际考量价值。

从汇编指令的映射关系中，可以直观洞察编译器的转换机理。一个对正数执行累加的求和函数，在未开启优化的 -O0 下逐条通过栈帧操作内存：

text
sum_positive:
    pushq   %rbp
    ...
    movq    -16(%rbp), %rax
    leaq    0(,%rax,4), %rdx
    movq    16(%rbp), %rax
    addq    %rdx, %rax
    movl    (%rax), %eax
    testl   %eax, %eax
    jle     .L3

而在 -O2 优化下，循环的循环控制对象与累加对象均被收纳进硬件寄存器，原本依赖跳转的分支指令被编译器提炼为无分支预测开销的条件传送指令（cmovg）：

text
sum_positive:
    .seh_endprologue
    testq   %rdx, %rdx
    je      .L5
    leaq    (%rcx,%rdx,4), %r9
    xorl    %eax, %eax
.L4:
    movl    (%rcx), %edx
    testl   %edx, %edx
    leal    (%rax,%rdx), %r8d
    cmovg   %r8d, %eax
    addq    $4, %rcx
    cmpq    %rcx, %r9
    jne     .L4
    ret

原本产生跳转预测风险的 jle 被替换为 cmovg，条件分支在流水线中被平滑执行；循环内部每次迭代的地址偏移计算，也被折叠为高效的连续指针自增。利用 gcc -S 生成汇编文本，或借助在线工具 Compiler Explorer 审视这类汇编差异，能够比泛读优化文档更精准地理解编译器的代码塑形行为。

在实际项目中，还有两个选项常常遭到盲目误用。选项 -march=native 会指示编译器针对当前编译机的主机 CPU 架构生成专用指令集，允许其调度最新的超宽向量寄存器；然而其代价是编译产物一旦迁移到稍早世代的处理器上，便可能直接因遇到非法指令（Illegal Instruction）而引发崩溃。在当前的 wordfreq v0.2 测试中，由于缺乏可向量化的热点循环，开启该选项未见任何加速收益。在工程交付中，若需榨取指令集特性，应当明确指定诸如 -march=x86-64-v2 等基线指令集等级，或干脆保持默认基线。另一个选项是跨翻译单元链接期优化 -flto（Link-Time Optimization），它允许编译器突破文件边界，将 counter.c 中的函数直接内联到 main.c 的调用点处。开启该特性需要在编译与链接阶段统一注入选项。然而在本案例中，该选项同样未带来可测的性能提升，因为核心热点的连续调用原本就完全封闭在 counter.c 翻译单元之内。

在软件工程规范中，-O2 -g 通常是综合考量运行性能与调试可观测性后的标准发布配置：编译器完成了充分的指令重排与寄存器分配，同时保留了基础的调试符号。诸如 -O3、针对特定微架构的目标指令集选项以及跨模块链接期优化，应当在量化剖析确认存在瓶颈且实测确实带来可观收益后再行引入，而不宜作为全局默认选项过早开启。优化级别会调整算术运算的指令调度、消除看似无用的空循环，并将大量对象固定在寄存器中，正如第 12 章在分析调试器时所呈现的，这会导致在调试单步跟踪时频繁遭遇 <optimized out> 现象，增加排查缺陷的心理负荷。

7. 微基准的常见错误 ​

微基准（Microbenchmark）用于隔离测量单一函数或极简代码片段的微观吞吐。由于其测量粒度往往精细到微秒乃至纳秒级，极易受到编译器激进变换与硬件微架构特性的隐式干扰。在微基准设计中，最普遍也最隐蔽的陷阱，莫过于待测代码在编译优化阶段被当作死代码（Dead Code）整体剔除或强度折叠。

先看一段看似合理的微基准计时代码。这段逻辑在循环中反复对外部文本调用 strlen，并将计算出的长度累加进局部对象 total，最后统一打印输出：

c
size_t total = 0;
double start = now_seconds();
for (long i = 0; i < ITERATIONS; i++) {
    total += strlen(text);
}
double end = now_seconds();
printf("plain local   %6.3f s  (total = %zu)\n", end - start, total);

指针 text 来自命令行参数输入，编译器无法在编译期静态推导出其所指字符串的具体长度。然而开启 -O2 优化后，编译器的循环不变式代码外提（LICM）策略识破了循环体的本质：每次迭代所调用的函数入参完全恒定，且遵循标准规范的 strlen 被视为没有副作用的纯计算函数。于是编译器直接将其折叠为单次 strlen 调用，紧接着用一条 64 位乘法指令 imulq $10000000 乘上迭代总次数。生成的可执行文件中，原本预期循环一千万次的迭代结构在反汇编后荡然无存。运行实测程序（code/开发与工程基础/15_测量_分析与优化/bench_strlen.c）得到如下对比结果：

zsh - ./bench_strlen（-O2）
text
plain local    0.000 s  (total = 640000000)
volatile sink  0.042 s  (sink = 640000000)

第一行输出报告的 0.000 秒，正是因为循环体被彻底消解、strlen 仅被实际执行了一次所致，与算法自身的执行效率毫无瓜葛。然而两行输出中的累计总量 total 完全一致，表明逻辑输出表面上毫无破绽。这种测量数值完全失真的缺陷，极难单纯从终端打印结果中察觉。

解决这类死代码消除的工程手段，是迫使编译优化器必须将每一次迭代的计算结果当作可观察的外部副作用落实。在 C 语言中，将累加对象显式修饰为 volatile：

c
volatile size_t sink = 0;
start = now_seconds();
for (long i = 0; i < ITERATIONS; i++) {
    sink += strlen(text);
}
end = now_seconds();

volatile 类型限定符明确告知编译器：该对象的每一次读写都代表外部可观察的物理访问，严禁优化器将其合并、删除或外提。如此一来，循环便无法被静态折叠，每一次迭代都必须忠实完成函数调用与内存写回。在生成的汇编代码中，带有分支跳转的真实循环得以重新就位：call strlen、addq %rdx, %rax、movq %rax, 40(%rsp) 以及条件回跳指令 jne .L8。

❌ 结果没人用
c
size_t total = 0;
for (long i = 0; i < ITERATIONS; i++) {
    total += strlen(text);
}
printf("%zu\n", total);
✅ 结果写进 volatile 对象
c
volatile size_t sink = 0;
for (long i = 0; i < ITERATIONS; i++) {
    sink += strlen(text);
}
printf("%zu\n", (size_t)sink);

除了待测代码被编译器整段优化消除之外，微基准评测中还普遍存在以下几类典型干扰：

单次测量周期过短： 单次轻量函数调用的执行耗时仅需数十纳秒，而现代通用操作系统的单调时钟 API 存在固有的纳秒级量化误差与系统调用开销（实测系统时钟分辨率约为 100 纳秒）。若是直接对单次调用计时，读数必然淹没在时钟截断噪声中。稳妥的做法是通过足量的大循环进行聚合测量，确保总测量时长远超计时器的最小分辨率。

忽略冷启动与预热阶段： 首次执行代码往往伴随着操作系统缺页中断、指令缓存（I-Cache）冷启动加载以及分支预测器冷启动等偶发抖动，其耗时显著高于后续稳态执行。在展开正式基准记录之前，应当主动执行数轮空转预热（Warmup），剔除前期的瞬态样本，或者将测量循环次数拉长到让稳态占据主导地位。

二进制布局与环境扰动： Mytkowicz 等学者在 ASPLOS 2009 的经典论文中揭示了一个反直觉的实验现象：在完全相同的源代码与编译器配置下，仅仅因为链接器决定的对象摆放顺序发生微调，或是操作系统环境变量占用的栈底字节长度改变，基准测量的结果就会产生几个乃至十几个百分点的浮动。这类偏差源自 CPU 缓存行对齐与分支目标缓冲区的隐式冲突，与逻辑本身无关。

将微基准局部加速与端到端性能混为一谈： 某个原子函数经微优化加速了 20%，若该函数在端到端业务链路中仅占 1% 的总耗时，根据阿姆达尔定律（Amdahl's law），对整体吞吐的实际贡献几乎可以忽略。微基准的定位是精准验证某项特定的改写是否在微观层面生效，绝不能替代端到端的全流程测量。

用 -S 确认循环还在

在完成微基准的设计后，应当使用 gcc -O2 -S 输出对应的汇编源文件，核验内层循环的指令标签与循环跳转逻辑是否真实存在。如果在汇编中找不到紧凑循环的踪迹，所测得的纳秒级数据便缺乏可信度。

8. 记录与防止退化 ​

基准测量的关键成果必须以规范的文档形式固化沉淀，否则未来的重构与功能演进将失去参照基线。在本项目中，docs/performance.md 承担了这一基准归档职责，其结构通常由三项要素构成：宿主运行环境、版本对照数据表、以及基准采样的执行规范。

markdown
# 性能记录

## 环境

| 项目 | 值 |
| --- | --- |
| 机器 | Windows 11（10.0.26300），Intel Core Ultra X7 358H |
| 编译器 | MinGW-w64 GCC 13.2.0（UCRT） |
| 构建选项 | `-std=c17 -O2 -g` |
| 输入 | `tools/gen_words 1000 N 42` 生成，N 为 10^4、10^5、10^6 |
| 计时 | 程序内 `clock_gettime(CLOCK_MONOTONIC)`，每种规模 5 次取中位数 |

## v0.1 与 v0.2 对照

| 单词数 | v0.1 中位数（秒） | v0.2 中位数（秒） | 加速比 |
| --- | --- | --- | --- |
| 10000 | 0.0108 | 0.0011 | 9.8 |
| 100000 | 0.1103 | 0.0078 | 14.1 |
| 1000000 | 1.1286 | 0.0696 | 16.2 |

:::

记录性能数据应当遵循清晰的工程准则。表格主体统一记录多轮测量的中位数，并在附注或补充说明中如实记录极值（最小值与最大值），单次运行读数不具备统计代表性，不单独入表。当硬件配置、编译器版本或优化级别发生变更时，应另立章节记录，严禁将异构环境下的数值混编于同一张对比表中，避免读者误将环境波动归因为代码效益。每一组测试用例均须详细阐明输入数据的规模与伪随机种子的生成方法，确保未来能够无损复现相同的测试负载。

防范性能退化，根本途径在于将基准测试有机融入日常开发流程。

每次完成计数器模块或底层数据结构的改动后，首先执行单元回归测试，随后启动性能基准测量。前者验证程序的功能正确性与边界行为无误，后者守卫代码的吞吐效率未发生倒退。这两道防线均可实现全自动判定：第 11 章介绍的 ctest 若退出码非 0 即提示功能回归失败；而运行 tools/bench.sh 采集的最新数据与 docs/performance.md 中的历史基线比对，便可迅速捕捉性能波动。对于微小波动，5% 以内的涨跌通常归因于系统环境噪声；但一旦耗时膨胀超过 20%，便达到了触发深入排查的告警阈值。

在执行严格的基准测量时，切忌在多人共享或高负载服务器上开展。同一宿主机上并行的外部进程会剧烈争抢 CPU 时间片、最后一级缓存（LLC）以及内存总线带宽，由此得出的测量数字既不可复现，亦失去横向可比性。在 Linux 环境下开展高精度测量时，建议借助 taskset 工具将待测进程绑定至指定的物理核心（CPU Pinning），并确保宿主系统处于低干扰的空闲状态。

优化迭代告一段落后，切勿草率清理临时编写的基准驱动脚本与语料生成器。将它们纳为工程资产妥善归档，在下一次架构重构或依赖升级时，能省去重新搭建评测脚手架的重复劳动。

9. 习题 ​

9.1 巩固 ​

#21501
⚡1⏳1

tools/bench.sh 在一台机器上连续跑两次，输出如下：

text
build:    -std=c17 -O2 -g -Iinclude
baseline: 34 ms  (empty input: process startup, shell and timer overhead)
words         total       net
10000          35 ms     1 ms
100000         43 ms     9 ms
1000000       114 ms    80 ms
text
build:    -std=c17 -O2 -g -Iinclude
baseline: 33 ms  (empty input: process startup, shell and timer overhead)
words         total       net
10000          35 ms     2 ms
100000         43 ms     9 ms
1000000       100 ms    67 ms

(1) 两次运行的基线不同（34 与 33 ms）。用 total - baseline 核对两次的一万词与一百万词两行，写出各自的净时间。两次的一万词净时间相差 1 ms，一百万词相差 13 ms；哪一行的差异更能说明「外部计时不可靠」，依据是什么？

(2) 基线 33～34 ms 是怎么来的，为什么它既不能忽略，也不能简单地从一个「程序内计时」的数字里减掉？

(3) 一万词的真实计算时间用程序内计时量出来是 0.0011 秒。外部计时在这一行上还能分辨出两个版本 20% 的差别吗？据此说明 bench.sh 适合回答什么问题、不适合回答什么问题。

#21502
⚡2⏳2

tools/gen_words.c 生成可重复的输入。用注释里的构建命令编出 gen_words，完成下面的实验。

(1) 用 gen_words 50 30 42 生成两次，cmp 比较；再换种子 43 生成一次，比较。记录 cmp 的输出。

(2) 生成 gen_words 1000 10000 42、1000 100000 42、1000 1000000 42 三个文件，记录字节数。先比较 10k 文件与 1M 文件：10k 文件去掉末尾的换行之后，是否逐字节等于 1M 文件的开头？再用 cmp 找出 1M 文件里偏离 100k 文件前缀的第一个字节，说明它为什么在那里不同。

(3) 用 tr ' ' '\n' < words | sort -u | wc -l 统计三个文件的不同单词数，再用 sort | uniq -c | sort -rn | head -3 找最高频的三个。三次结果分别是什么？不同单词数为什么不随 N 线性增长。若统计结果比预期少 1，检查文件末尾的字节。

(4) 固定 N 为 100000，改 M 为 1000、10000、100000 各生成一份，统计不同单词数。把这三个数和正文第 5 节表格里的 995、9455、46058 对照；差几，差在哪里。

#21503
⚡2⏳2

写一个程序 clocks.c，在同一段代码里做三组测量：

  1. 睡眠约 300 ms（Linux 用 nanosleep，Windows 用 Sleep）；
  2. 忙等约 4 亿次加法（用 volatile 累加对象，确保循环不被删掉）。

每组前后各取一次 clock()、clock_gettime(CLOCK_MONOTONIC)、clock_gettime(CLOCK_PROCESS_CPUTIME_ID) 与 timespec_get，打印四个差值。

(1) 把两组的八个数字整理成表。睡眠那一组里，四个时钟各是多少？忙等那一组呢？

(2) 哪两个时钟在睡眠期间几乎不增长？它们分别适合回答什么问题？

(3) timespec_get 取的是日历时间。如果测量期间系统对时向前跳了 2 秒，用它算出的间隔会是多少？CLOCK_MONOTONIC 为什么不受影响？

(4) 在 MinGW 上，clock() 在 Sleep 期间可能照常增长（本机实测 0.302 秒）。若把 clock() 的结果当成 CPU 时间汇报，会得出什么错误结论？这一条对「测量程序必须写明构建条件与平台」有什么补充。

9.2 编程 ​

#21504
⚡3⏳3

用第 14 章快照 code/开发与工程基础/14_覆盖率与模糊测试/wordfreq/（线性查找的 v0.1）做一次剖析。

(1) 按正文的命令带 -pg 构建，分别加与不加 -no-pie 运行，各生成一份 gprof -b 报告。记录两种情况下平面剖析的前几行，说明 -no-pie 改变了什么。

(2) 在 gmon.out 那份有效报告里，wf_counter_add 与 strcmp 各占多少比例，calls 一列为何 strcmp 是空的。用 self seconds 与 calls 算出 ns/call，与报告里的数字对照。

(3) _mcount_private 与 __fentry__ 是什么？它们占的比例能说明程序慢在哪里吗？测真实版本时这两项为什么不存在。

(4) 用 time 记录同一份输入的总耗时，与 gprof 报告累计的采样秒数相比。相差多少？报告里「Each sample counts as 0.01 seconds」这句话该怎么理解。

#21505
⚡3⏳3

gprof 只统计带 -pg 编译的代码。取 code/开发与工程基础/15_测量_分析与优化/gprof_dll/loop.c：

(1) 按注释里的命令构建并运行，记录 time 的 real 与 gprof -b 的平面剖析。墙钟两百多毫秒，报告为什么是 no time accumulated？

(2) 把 loop.c 里的循环体原样搬进自己的 heavy.c，与 main 一起用 -pg 编译，再跑一次。这次报告里出现了什么？calls 一列有数字吗？

(3) 把 heavy.c 编成目标文件时故意不加 -pg，main 仍加 -pg，链接后运行。报告里时间还在吗？calls 呢？再把它编成 libheavy.dll 并链接（-L. -lheavy），重复一次。静态链接与动态库两种情形下「没有插桩」的后果有什么不同。

(4) 正文给了判断报告是否漏时间的办法：拿 gprof 的累计采样时间与 time 的 real 对比。对这三组实验各做一次对比，写出结论。本机那组静态链接的对照是：未插桩时报告 100% 记在 heavy_sum 上、calls 为空；插桩后同一函数有 calls 1、110 ms/call。

#21506
⚡3⏳3

写一个测量程序 measure.c，对 wordfreq 的两种构建（-O0 与 -O2）各测五轮：

  • 用 CLOCK_MONOTONIC 在程序内计时，输入固定为 gen_words 1000 1000000 42 生成的文件；
  • 每轮打印一个数字，最后打印中位数、最小值、最大值；
  • 计时区间只包住读文件、分词、计数、输出，stdout 重定向到空设备。

(1) 贴出两张表。两个版本的耗时相差多少倍？最大最小值之间的差距与中位数的比值各是多少。

(2) 写一个「单次测量」的对照版本，只跑一轮，连续运行十次。十个数里最大值与最小值相差多少？如果只取其中一次下结论，可能错到什么程度。

(3) 在程序运行时后台跑一个占满一个核的进程，再测五轮。中位数与最大值各变化多少？正文建议「最大值离中位数很远时在安静的机器上重测」，这个实验能否印证。

(4) 为什么计时区间要把输出重定向到空设备；如果输出到终端，测得的是哪一段的时间。

#21507
⚡4⏳3

这一题量化复杂度。v0.1 的 counter.c 在 find_entry 里逐个 strcmp，v0.2 用 lower_bound 做二分查找。

(1) 在两个快照的 counter.c 里临时加一个计数器：每次调用 strcmp 前自增一个文件作用域的 size_t，程序结束前打印出来。不要用编译器优化掉的写法，确保计算结果被显式消费而非被编译器优化消除。记录 -O0 与 -O2 两种构建下的计数。

(2) 用 gen_words 1000 100000 42、10000 100000 42、100000 100000 42 三份输入（不同单词数约 995、9455、46058）分别跑两个版本，各填一张表：不同单词数、strcmp 次数、耗时、与上一行的比值。

(3) 计算 v0.1 的比较次数与 N⋅M/2、v0.2 与 N⋅log2⁡M 的相对误差。哪一版与理论更接近？v0.2 多出来的部分花在哪里？

(4) 这一组实验说明「优化先改算法」的依据是什么？用一句不超过 40 字的话概括，并指出哪一种情况下换算法没有收益。

参考数字（同一台机器，在 counter.c 内部自加计数，-O0 与 -O2 测得的次数相同）：词表约一千时 v0.1 做了约 4300 万次比较，词表约九千五时约 4.0 亿次。与 N⋅M/2 和 N⋅log2⁡M 各算一遍，看哪一版更接近理论值。自己数到的词表可能比正文表格少一，原因见上一题第 (3) 问。

#21508
⚡4⏳4

用同一份 v0.2 源码构建五个版本：-O0、-O1、-O2、-O3、-Os，都带 -g。

(1) 用 size 记录每个版本 text 段的字节数，用程序内计时各测五轮取中位数（输入为一千词规模的 words-1000000.txt），填成一张表。本机的参考值是 text 段 18608、17004、17256、17272、16792 字节。

(2) 哪个级别已经拿到全部收益？-O3 为什么没有更快？用 gcc -fopt-info-vec 编译 counter.c 与 token.c，看哪些循环真的被向量化了，把输出贴出来。

(3) -Os 用多大的时间代价换来了多少体积？什么样的项目会做这个交换，桌面程序与固件分别怎么选。

(4) 测试 -march=native 与 -flto：记录耗时与体积的变化，并解释为什么在这个程序上两者都没有收益。-march=native 的产物拿到旧机器上会发生什么。

#21509
⚡5⏳4

微基准最容易骗人。以 code/开发与工程基础/15_测量_分析与优化/bench_strlen.c 为起点，写一个 bench4.c，对同一个 strlen 循环做四种写法：

c
/* 1：累加进普通局部对象 */
size_t total = 0;

/* 2：累加进 volatile 对象 */
volatile size_t sink = 0;

/* 3：通过函数指针调用 */
size_t (*fn)(const char *) = strlen;

/* 4：通过 volatile 函数指针调用 */
static size_t (*volatile vfn)(const char *) = strlen;

(1) 四种写法各跑一千万次，记录耗时。本机在 -O2 下的参考值是 0.000、0.042、0.000、0.043 秒。每一种的数值是否可信？

(2) 对四种写法各生成一次汇编（gcc -O2 -S），找出循环标签还在不在、call strlen 出现了几次、有没有 imul。用汇编解释四个数字。

(3) 计时器的分辨率在本机是 100 ns。一次 strlen("...") 约几十纳秒，单次调用直接计时会得到什么？要循环多少次才能让总时间可靠？

(4) 正文提到「预热」与「链接顺序」两类干扰。为前者写一段可复现的实验：同一段代码先跑一轮、再跑第二轮，比较两轮的数字；后者说明为什么两个函数在同一个可执行文件里的相对快慢不能只看微基准。

(5) 用一句话写出你会给同事的微基准检查清单，至少包含三项。

9.3 综合与挑战 ​

#21510
⚡6⏳5

这一题走完「测量、改动、记录、防退化」的完整流程。

(1) 用 tools/bench.sh 或自己的测量程序，记录 v0.2 在一千词、一万词、十万词三种输入上的中位数，写进 docs/performance.md 的新一节，环境表按正文的格式填全（机器、编译器、构建选项、输入生成方式、计时方法）。

(2) 做一次改动：把 counter.c 里 reserve_one 的扩容策略从「容量翻倍」改成「每次加 16」，接口与行为不变。先用第 11 章的三个测试验证行为，再用同一套测量比较新旧版本。记录耗时与加速比，判断差异是否超过 20% 的追查阈值。如果测不出差别，解释为什么——分配器在什么情况下会把 realloc 做成原地扩展，从而让「扩容次数」这个指标变得不重要。

(3) 挑战：正文说 v0.2 的剩余开销在「复制新单词、按需扩容、memmove 腾出插入位置」。设计一个实验区分三者。提示：让输入的单词按字典序已排好，插入位置永远在末尾，memmove 搬 0 个元素。用 gen_words 100000 100000 42 生成一份，再用 tr ' ' '\n' < ... | sort | tr '\n' ' ' 得到排好序的版本，各测五轮。本机实测未排序约 0.15 秒、已排序约 0.034 秒，你测到的比值是多少？

(4) 解释 (3) 的结果：为什么输入顺序会改变一个「与算法无关」的实现的时间。这个现象对「用一份随机输入代表所有负载」的做法提出了什么要求。

(5) 把 (2) 与 (3) 的结论写进 docs/performance.md，并给出下一次改动的判断：按现在的数据，下一步该改算法（换散列表或前缀树）还是继续做常数优化？给出数字依据。

10. 参考资料 ​