第3章：测量性能

从“快”必须有尺度和证据开始

性能不是程序的单一属性。“这个版本更快”至少缺少 workload、input size、hardware、compiler、metric 与 uncertainty。处理十个元素时，常数项较小的线性扫描可能胜过建立索引；数据扩大后，增长率才逐渐支配总成本。服务的平均延迟下降也不代表 p99 改善，更不代表 throughput、memory footprint 或 energy 同时改善。

先预测成本由哪种操作和哪段输入分布支配，再建立可证伪的假设。例如“hash lookup 太慢”应改写成：“在 production key distribution 与 load factor 下，lookup 的 p95 CPU time 由 collision chain 支配；降低 load factor 会减少 cycles/op，但增加 memory。”后者明确了指标、原因、控制变量与可能的取舍。

渐近复杂度描述增长率

Big O 给出上界增长类别，不是一次调用的耗时。若算法执行 $3n^2 + 7n + 20$ 次基本操作，规模增大时二次项占主导，因此写作 $O(n^2)$。这不表示系数不存在，也不表示所有 $O(n)$ 算法在所有规模都快于 $O(n^2)$；cache locality、allocation、branching 与 vectorization 都会改变交叉点。

bool containsPairWithSum(const std::vector<int>& values, int target) {
    for (std::size_t i = 0; i < values.size(); ++i) {
        for (std::size_t j = i + 1; j < values.size(); ++j) {
            if (values[i] + values[j] == target) return true;
        }
    }
    return false;
}

最坏情况下检查约 $n(n-1)/2$ 对，是 $O(n^2)$；但找到早期匹配时会提前返回，所以实际 cost 依赖 input。要比较替代实现，必须说明 average/worst case、数据分布和是否包含预处理。用 hash set 可把期望时间降到 $O(n)$，却引入 hashing、allocation 与额外 memory；若 adversarial collision 或 hash guarantee 不成立，不能把期望复杂度说成无条件保证。

空间复杂度同样重要。一个 time-efficient algorithm 可能建立 $O(n)$ auxiliary storage；在 memory-bound workload 中，这会增加 cache/TLB pressure，甚至令理论改进反向。复杂度负责排除不随规模成立的方案，benchmark 负责找出目标区间内的真实交叉点。

摊还复杂度解释偶发昂贵操作

动态数组 push_back 大多只在已分配 storage 尾部构造元素，是常数成本；capacity 用尽时却要申请更大 storage，并移动或复制已有元素。单次扩容可达 $O(n)$，但若 capacity 按几何比例增长，连续 $n$ 次 append 的总迁移量形成几何级数，总工作仍为 $O(n)$，所以每次 append 的摊还成本是 $O(1)$。

设 capacity 每次至少翻倍，达到容量 $n$ 之前被迁移的元素总数满足：

再加上 $n$ 次新元素构造，总操作数小于 $2n$；因此序列总成本是 $O(n)$，除以 $n$ 次 append 得到 amortized time complexity $O(1)$。这是对整段序列的上界推导，不是一次扩容的耗时预测。

std::vector<Record> records;
records.reserve(expected_count); // known bound: avoid intermediate growth
 
for (const auto& input : inputs) {
    records.emplace_back(parse(input));
}

摊还不是概率平均，也不承诺每次调用都快。real-time path 关注 single-operation deadline，偶发 reallocation 仍可能不可接受；此时需要 reserve、fixed-capacity storage 或把 growth 移出关键窗口。反之，盲目 reserve 一个巨大上界会增加 footprint 与 page commitment。正确问题是：sequence-level throughput 还是 per-operation tail latency 是契约？

测量什么：先定义性能属性

latency 回答“一次多久”，throughput 回答“单位时间完成多少”，两者会随 concurrency 与 queueing 相互作用。CPU time 可定位计算消耗，wall time 包含 blocking、I/O 与 scheduling；cycles/op 有助于跨同一机器的运行比较，却不能脱离 frequency 和 microarchitecture。memory 可分 peak resident set、allocation count/bytes、working set 与 bandwidth；还可能关心 startup time、binary size、energy 和 frame-time stability。

稳定系统中可用 Little's Law 检查指标是否自洽：平均在途工作量等于到达率乘平均停留时间。它不是降低延迟的手段，而是提醒我们报告 concurrency、throughput 与 latency 时不能让三者相互矛盾。

测量边界必须与用户可见契约一致。若只计函数 body，却把 input construction、cache warmup 或 output serialization 排除，数字可能回答了另一个问题。microbenchmark 适合隔离机制，component benchmark 观察协作成本，end-to-end test 验证真实路径；三者不是互相替代，而是从因果解释到外部效应逐层补证。

设计可复现的性能测试

performance testing best practices 的核心首先是实验设计。固定代码与 build flags，记录 CPU、OS、compiler 与 library；选择代表 production 的 input size、shape 和 hit/miss ratio；一次只改变一个待验证因素；用 interleaving 或 randomized order 降低温度、频率和时间漂移对 A/B 的偏置。样本数应由 noise 与所需 detection size 决定，而不是迷信固定次数。

static void BM_lookup(benchmark::State& state) {
    const auto table = makeTable(state.range(0), state.range(1));
    const auto queries = makeRepresentativeQueries();
 
    for (auto _ : state) {
        for (const auto key : queries) {
            benchmark::DoNotOptimize(table.find(key));
        }
    }
    state.SetItemsProcessed(state.iterations() * queries.size());
}

编译器会删除无 observable effect 的工作、把 invariant calculation 移出循环，或在 benchmark 与 production 的不同 translation-unit visibility 下产生不同代码。DoNotOptimize/barrier 类工具只能约束特定优化，不能修复不代表生产的 workload。检查 generated assembly 或 counters，确认 timed region 真在执行目标工作；同时把 fixture setup 放到边界外或明确把它纳入指标。

warm cache 与 cold cache 是两个不同场景，不应混成含糊均值。先定义 cache state，再控制或分别报告。frequency scaling、thermal throttling、SMT sibling、NUMA placement、background work 与 allocator state 都可能是 confounder；无法完全消除时，要记录、随机化并报告 distribution。比较结果应给 effect size 与 uncertainty，而不是只给“最快一次”。

热点决定优化上限

若函数只占总时间 2%，即使无限加速，端到端改善也不超过约 2%。这就是先 profile 再优化的理由：热点占比给出收益上限，call stack 和 source line 提供归因入口。热点会在优化后转移；改完要重新 profile，不能继续沿用旧画像。

若热点占原执行时间比例为 $p$，局部加速倍数为 $s$，端到端加速上限由 Amdahl 关系给出；当 $s$ 趋于无穷时，总加速仍不超过 $1/(1-p)$。

flat profile 说明样本或时间落在哪个 symbol，call-tree/profile stack 说明它经哪条调用路径到达。inclusive cost 包含 callees，exclusive/self cost 只算函数自身。看到 allocator 热点不等于“allocator 坏”，它可能是上游对象 churn 的结果；看到 memcpy 热点也要追问复制的 owner 和生命周期。证据需要沿调用链回到可修改的 cause。

插桩分析器与采样分析器

插桩可由 compiler、binary rewriting 或手动 tracing 实现。它能精确记录被探针覆盖的 calls 与 durations，适合低频路径、调用次数和事件序列；代价是每次事件都执行记录逻辑，可能改变 inlining、cache、timing 与 thread interleaving。细粒度热点若调用极频繁，observer effect 会很明显。

采样不记录每次调用，而从统计样本估计 CPU time 或 hardware-event 分布，通常开销较低，适合较长运行和近生产 workload。短函数、稀有事件或运行时间太短可能没有足够样本；sampling frequency 越高，分辨率提高但 overhead 也增加。样本比例是估计，不应伪装成精确到纳秒的调用时长。

原书在这一节并列讨论 hot spots、instrumentation profilers 与 sampling profilers。选择方法取决于问题：问“这个 callback 调了几次、顺序如何”偏向 instrumentation；问“长时间 CPU 都花在哪里”偏向 sampling；问 cache miss、branch miss 或 cycles 可用 PMU event sampling/counting。两者可组合：先低开销 sampling 缩小范围，再对少数边界插桩验证调用与 latency。

hypothesis -> representative workload -> baseline benchmark
           -> sampling profile -> dominant stack / event
           -> focused change -> paired benchmark
           -> profile again -> regression guard

第3章实验协议

1. 为线性扫描、排序与 hash lookup 写出 best/average/worst complexity，并标出假设。
2. 记录 vector 连续 append 的 capacity 与单次 latency，区分 spike 和 amortized cost。
3. 为同一 workload 同时报告 latency distribution、throughput、allocation 与 peak memory。
4. 比较 cold/warm cache 与不同 input distribution，不把两者混成一个均值。
5. 检查 benchmark 的 optimized assembly，证明核心计算未被删除或移出 timed loop。
6. 用 sampling profile 找出 dominant stack，再用 focused instrumentation 验证调用次数。
7. 优化后重新 profile，确认 hotspot 消失、转移或暴露新的 bottleneck。
8. 保存 source revision、build flags、environment、raw samples 与 analysis script。

小结

• 渐近复杂度描述规模增长率，不包含常数、cache行为或目标规模的真实交叉点
• 动态数组append可摊还O(1)，但单次扩容仍为O(n)，tail-sensitive路径必须单独处理
• 测量前先定义latency、throughput、memory、CPU或energy等性能属性与边界
• 可信测试需要代表性workload、相同build、控制变量、有效timed region和uncertainty
• hotspot给出潜在收益上限，inclusive/exclusive cost与调用栈帮助追到原因
• instrumentation精确覆盖事件但可能扰动程序；sampling以较低开销估计成本分布
• 性能工程是“假设、测量、profile、修改、复测、再profile”的闭环

原版目录概念补充核对

以下条目补齐官方目录中容易被示例主线掩盖的概念。它们不重复罗列目录，而是明确每项概念的机制、适用边界和验收证据。

测量什么：机制、边界与证据

在《第3章：测量性能》的官方单元 chp-03 中，测量什么连接本章第 3 组知识约束。学习时要同时说明它接受什么输入、改变什么状态、在何种边界失效；再以本章示例的编译诊断、固定输入输出或失败用例复核结论，不能只记术语名称。