16.2　从复杂度到实测：性能剖析

学习目标：学完本节，你能

• 说清理论复杂度和实际性能之间隔着什么（缓存、分支预测、运行时开销）；
• 认出五个基准测试的陷阱，并说出每个陷阱是怎么把结论带偏的；
• 用一份可复用的清单做一次可信的对比实测；
• 判断"我测出来的这个差距，到底是不是真的"。

先修：16.1（选型手册）、13.1（微基准噪声）、3.1（缓存行）、12.1（内存测量）。 固定术语：大 O 记法、缓存行、摊还代价。 环境与版本：.NET 8 / C# 12。 预计阅读：30 分钟。

一、直觉：复杂度和实际性能之间隔着什么

1.1 节开篇提过一个问题：为什么同样的功能，换个写法能差 8.5 万倍？

答案分两半：

一半是复杂度 —— 一个 $O(n^2)$、一个 $O(n)$，规模一大就被甩开。

另一半是常数因子 —— 而这一半，复杂度理论完全不告诉你。

本书前面反复撞见这"另一半"：

把这些放在一起，规律很清楚：

复杂度决定"趋势"，常数因子决定"当下" —— 而常数因子由硬件行为和运行时开销决定。

这一节讲的就是这"另一半"：它从哪来，以及怎么测才不被它骗。

二、实测一：同一算法，只改遍历顺序

先看常数因子能大到什么程度。

用一个 4000×4000 的二维数组（1600 万个 int，约 61 MB），把全部元素加起来：

  两种写法【操作次数完全相同】—— 都是 16,000,000 次加法：
    行优先：外层走行，内层走列（顺着内存排布走）
    列优先：外层走列，内层走行（跨着内存跳）

    行优先：   5.85 ms
    列优先：  12.57 ms
    列优先慢 2.15 倍

两种写法的代码：

// 行优先：顺着内存走
for (int r = 0; r < rows; r++)
    for (int c = 0; c < cols; c++)
        sum += m[r, c];

// 列优先：跨着内存跳
for (int c = 0; c < cols; c++)
    for (int r = 0; r < rows; r++)
        sum += m[r, c];

两者只差内层外层的顺序 —— 算法一模一样，加法次数一模一样，复杂度一模一样。

差的只有一件事：内存访问的顺序。

C# 的二维数组是"行优先"存放的 —— m[r, c] 和 m[r, c+1] 挨在一起， 而 m[r, c] 和 m[r+1, c] 隔了一整行（16000 字节）。

3.1 节讲过的缓存行是 64 字节 —— 所以"跨着跳"的那版，每次访问都可能要把一整行数据重新装进缓存。

这一条的价值在于：它连"换个算法"都没做，只换了两行 for 的位置，就慢了 2.15 倍。

三、五个基准测试的陷阱

既然实测这么重要，那"测得对"就成了前提 —— 而测错的方式比想象中多。

陷阱 1：没有预热

先看一种很常见的测法：直接跑、跑一次、下结论。

  下面这个 ColdSum 方法【在此之前从没被调用过】：

    第一次测「A」：  0.490 ms
    第二次测「B」：  0.129 ms
    结论：B 比 A 快 3.8 倍！

  但 A 和 B 是【同一个方法】—— 两次调用做的事一模一样（结果都是 12374262 和 12374262）。
  第一次多花的那 0.361 ms，是 JIT 把这段代码【编译成机器码】的时间。

同一个方法，测两次，差 3.8 倍。 换成一个真实的 A/B 对比，这个陷阱会怎么表现？

先测的那个方法吃亏（它的第一次调用要付 JIT 的钱），后测的那个占便宜（前面的代码已经把运行时焐热了）。

于是你会得出"后测的那个更快"—— 而它可能只是沾了前面热身的光。

修正：正式测量之前，让每个被测方法先跑几遍。

SumRowMajor(matrix);      // 预热
SumColumnMajor(matrix);   // 预热
// 然后才计时

陷阱 2：只跑一次

预热之后，连续跑 10 次同一段代码：

    5.96  6.02  5.86  5.88  5.95  6.04  5.89  6.06  5.87  5.89

    最快 5.86 ms，最慢 6.06 ms，波动 3%

同一段代码、同样的输入，数字还在跳 —— 因为后台还有 GC、还有别的进程、还有 CPU 的频率调节。

只跑一次 = 抽一次签。 抽到快的那次你会高估它，抽到慢的那次你会低估它。

修正：跑多轮，取【最快】的那一次。

为什么取最快而不是取平均？

因为"最快的那次"最接近"没有干扰时的真实耗时" —— 干扰只会让时间变长，不会让它变短。

取平均等于把干扰也平均进去了 —— 而我们要的是"这段代码本身要多久"。

陷阱 3：忽略 GC

同一个求和，一个版本每轮新建一个数组，一个版本复用同一块内存：

    每轮新建数组：单次分配  4,000,024 B
    复用同一块内存：单次分配          0 B

    每轮新建数组：0.635 ms
    复用同一块内存：0.375 ms

差 1.7 倍 —— 而这 400 万字节的分配，在只看代码时是完全看不出来的 （两个方法都只有五行，长得几乎一样）。

更麻烦的是：分配会带来 GC，而 GC 什么时候触发是不确定的 —— 所以分配密集的代码，计时波动会明显更大（这也是陷阱 2 在分配型代码上更严重的原因）。

修正：把"分配了多少"一起测出来：

long before = GC.GetAllocatedBytesForCurrentThread();
// 被测代码
long allocated = GC.GetAllocatedBytesForCurrentThread() - before;

⚠️ 不要用 GC.GetTotalMemory 的差值法 —— 12.1 节实测过它给出"0.0 MB"和"-94.0 MB"这样的假结果。

原因：GC.GetTotalMemory 是整个进程的托管堆大小，别的线程一分配、GC 一回收，它就变 —— 你测的那段代码的贡献，被淹没在噪声里了。

陷阱 4：忽略噪声区间

行优先和列优先各跑 8 轮，原样列出：

    行优先：5.89  6.71  5.86  6.02  6.50  6.16  5.86  6.54
    列优先：16.45  14.94  13.64  15.08  16.28  13.66  13.16  12.70

    行优先区间 [5.86, 6.71] ms
    列优先区间 [12.70, 16.45] ms

    两个区间是否重叠：False

"两个区间是否重叠"这一行，才是这张表的重点。

不重叠 → 差距是真实的 ✓（列优先确实慢，不是噪声）

13.1 节测过另一种情况：Kahn 和迭代 DFS 各跑 8 轮，区间互相重叠（比值在 0.55~1.08 之间摆）—— 那种情况下，"谁更快"这个结论就不成立。

修正：报告结论之前，先看区间。

陷阱 5：死代码消除

如果一段计算的结果没有被使用，编译器/JIT 有权把它整个删掉。

    结果被使用（打印/累加）：5.86 ms
    结果被丢弃（直接调用）  ：5.87 ms

这次两个数字很接近 —— 说明在 .NET 上，这里的方法没有被优化掉。

为什么？ 因为 SumRowMajor 是一个独立方法、没有被内联， 而 JIT 不敢随便删掉一次"可能读到越界/可能抛异常"的真实调用。

但在 C/C++ 里这个陷阱非常致命 —— 编译器会把整个循环优化掉，你测到的是"什么都不做"的时间。

修正：让结果流向一个能被观测到的地方。

long sink = 0;
void Use(long v) => sink ^= v;      // 结果被"用掉"

// 测量时
var s = SumRowMajor(matrix);
Use(s);

本节所有测量都这么做了 —— 这也是为什么上面的输出里，两个数字都是真实耗时。

四、一份可复用的清单

把五个陷阱的修正合成一份清单：

  做一次可信的性能对比，按这个顺序：

  1. 【造数据】规模和数据分布都按真实情况来
             —— 别用"完美有序"或"全部相同"的数据（8.2 节的快排退化就是这么来的）

  2. 【预热】每个被测实现先跑几遍
             —— 把 JIT 和缓存都焐热

  3. 【多轮取最快】每项跑 N 轮（建议 ≥ 5），取最快的
             —— 只跑一次等于抽签

  4. 【结果要"用掉"】别让编译器把它当死代码删了

  5. 【同时报告分配量】用 GC.GetAllocatedBytesForCurrentThread()
             —— 不要用 GC.GetTotalMemory 差值法

  6. 【报告原始数字和区间】把多轮的每个数字列出来，让读者看到噪声
             —— 别只报一个"最快值"

  7. 【下结论前看区间】区间重叠就别下结论（13.1 的规矩）

这七条就是本书每一节实测遵循的流程 —— 你回头翻 1.1、3.1、8.2、13.1、16.1，都是这么做的。

最后一条最重要，也最容易被跳过：

"我测出来 A 比 B 快 20%"和"我知道 A 比 B 快 20%"之间，隔着一个"区间有没有重叠"。

13.1 节定的规矩在这里仍然有效：差距不到 2 倍、且复现不了五次以上的"谁更快"，不要写进结论。

五、练习

练习 16.2.1（识别陷阱） 下面每段测量都有问题，指出是哪个陷阱，并说出修正方法：

(a) ```csharp var sw = Stopwatch.StartNew(); var r = FastMethod(data); sw.Stop(); Console.WriteLine($"FastMethod 耗时 {sw.Elapsed.TotalMilliseconds:F2} ms");

```

(b) ```csharp for (int i = 0; i < 5; i++) { var sw = Stopwatch.StartNew(); MethodA(data); sw.Stop(); var tA = sw.Elapsed.TotalMilliseconds; sw.Restart(); MethodB(data); sw.Stop(); var tB = sw.Elapsed.TotalMilliseconds; Console.WriteLine($"A={tA:F1} ms B={tB:F1} ms"); } // 然后看最后一行，得出"B 比 A 快"的结论

```

(c) ```csharp long before = GC.GetTotalMemory(true); var result = BuildHugeList(100_000); long after = GC.GetTotalMemory(true); Console.WriteLine($"用了 {(after - before) / 1024.0 / 1024:F1} MB");

```

(d) ```csharp // 测一个"求和"函数，但结果没有被使用 var sw = Stopwatch.StartNew(); Sum(data); sw.Stop();

```

练习 16.2.2（判断） 判断对错并说明理由：

(a) 复杂度相同，性能就一定差不多。 (b) 取最快的那次比取平均更能反映代码本身的耗时。 (c) 测内存可以用 GC.GetTotalMemory 的差值。 (d) 只要跑了 100 轮，结论就一定可靠。

练习 16.2.3（设计一次测量） 你要验证"对 100 万个整数排序，Array.Sort 比手写快排快"这个说法。

(a) 数据该怎么造？为什么不能全用随机数？（提示：8.2 节） (b) 写出一份符合第四节清单的测量方案（不用写完整代码，说清每一步做什么）。 (c) 如果你测出来"Array.Sort 快 1.3 倍"，你会在报告里怎么写？

练习 16.2.4（挑战·解释一个反常现象） 13.4 节测出：Bellman-Ford 在随机稀疏图上比 Dijkstra 快 5.6 倍（0.46 ms vs 2.59 ms）， 尽管 BF 的复杂度是 $O(V \cdot E)$、Dijkstra 是 $O((V+E)\log V)$。

(a) 用本节"常数因子"的视角解释这个现象。 (b) 这个结论【能推广】到所有图吗？为什么？ (c) 如果要写进技术选型文档，你会怎么措辞？

六、练习答案

16.2.1

(b) 值得多说一句：那个写法还有第二个问题 —— 它每一轮都把 A 和 B 紧挨着测， 而 "B 紧跟在 A 后面"这个位置本身就是优势（A 的运行为 B 预热了缓存）—— 如果 A、B 的测量顺序固定，长期跑下去会系统性地偏向 B。

更严谨的做法是【交换顺序】各测一半，或者分别独立测量。

16.2.2

(d) 是本节最该记住的一条： 多跑几轮解决的是【随机噪声】，解决不了【系统偏差】。

五个陷阱里，只有陷阱 2、4 是噪声问题；陷阱 1、3、5 都是偏差问题 —— 跑再多轮也没用，只能靠改测法。

16.2.3

(a) 数据要造三种：随机、已排序、逆序。

为什么不能只用随机数？ 因为 8.2 节实测过：朴素快排在已排序数据上退化到 376 倍。

快排的"最坏情况"恰恰是最常见的真实输入（日志按时间有序、数据库查询结果有序）。

只用随机数测，你会得出"手写快排和 Array.Sort 差不多"的结论 —— 而这个结论在真实数据上会崩掉。

(b) 一份符合清单的方案

(c) 我会写：

"在随机数据上，Array.Sort 比手写快排快约 1.3 倍（10 轮区间不重叠）。 差距不到 2 倍，属于同一量级 —— 按本书的规矩，这个差距【不足以支撑选型结论】。 真正的差距在已排序数据上：手写快排慢 376 倍。"

理由：1.3 倍这个数字，换个机器、换个 .NET 版本可能就反过来了 —— 而"有序输入上快排退化"是量级上的差距，那才是可靠结论。

这就是 16.1 节那句"差距不到 2 倍且复现不了五次以上的不要写进结论"的实操。

16.2.4

(a) 因为 Dijkstra 每一次取出最小都要走堆，而堆操作的常数很大。

拆开看：

BF 的实际操作次数：$9 \text{ 轮} \times 30000 \text{ 条边} = 27$ 万次极简单的操作。

Dijkstra 的实际操作次数：约 3.5 万次堆操作 —— 次数少，但每次贵得多。

这就是 8.3 节讲过的"堆排序为什么慢"的同一个道理：堆的 $O(\log n)$ 看着漂亮，但它每次都要跳内存。

(b) 不能推广。

因为 BF 的优势来自"实际轮数少"，而轮数由【边的顺序】和【图的形状】决定 —— 13.4 节实测过最坏情况：逆序的链状图上，BF 跑满 4999 轮，19.89 ms，比 Dijkstra 慢约 660 倍。

所以这个结论的完整表述必须带上条件：

"在随机边序的稀疏图上，BF 可能比 Dijkstra 快；在最坏情况下它慢两个数量级。"

(c) 我会这么写：

**"在随机稀疏图（V=5000，E=30000）上，Bellman-Ford 实测比优先队列版 Dijkstra 快约 5.6 倍 （0.46 ms vs 2.59 ms，各跑 5 轮取最快）。 但这个结果是【输入相关】的：在逆序链状图这一最坏情况上，Bellman-Ford 慢约 660 倍（19.89 ms vs 0.03 ms）。

因此：如果边权非负且图是随机的，两者都可选，BF 的常数更小； 如果图可能被外部构造，必须按【最坏情况】选型 —— 那里 Dijkstra 快两个数量级。"**

这道题演示的是"怎么写实测结论" ——

一个光秃秃的"BF 快 5.6 倍"是【误导】；带上适用条件、带上反例，才是【可用的结论】。

这也是 1.3 节的规矩在性能领域的应用：SLA 按最坏情况定，选型也一样。

七、常见错误

八、本节总结

1. 复杂度和实际性能之间隔着"常数因子"，而它由硬件和运行时决定： 缓存、分支预测、JIT、GC。复杂度决定趋势，常数因子决定当下。
2. 实测一（缓存）：4000×4000 的二维数组求和，只改内层外层的顺序 —— 行优先 5.85 ms，列优先 12.57 ms，差 2.15 倍。算法、操作次数、复杂度全都没变。
3. 五个基准测试的陷阱：
   • ① 没有预热 → 实测差 3.8 倍（第一次 0.490 ms vs 第二次 0.129 ms）
   • ② 只跑一次 → 10 轮波动 3%
   • ③ 忽略 GC → 分配 4 MB 的版本慢 1.7 倍（0.635 vs 0.375 ms）
   • ④ 忽略噪声区间 → 行 [5.86, 6.71] / 列 [12.70, 16.45]，不重叠才算真差距
   • ⑤ 死代码消除 → .NET 上较弱（5.86 vs 5.87 ms），但 C/C++ 上会让整个循环消失
4. 一份七步清单：造真实数据 → 预热 → 多轮取最快 → 结果要用掉 → 报告分配量 → 报告区间 → 看区间再下结论。
5. 最重要的一条：多跑几轮只解决随机噪声，解决不了系统偏差。 五个陷阱里，①③⑤ 是偏差问题 —— 跑再多轮也没用，只能改测法。
6. 写结论要带条件：13.4 的"BF 快 5.6 倍"必须配上"在最坏情况上慢 660 倍" —— 光秃秃的结论是误导，带条件的结论才可用。

下一节衔接：本章前两节把"怎么选"和"怎么测"讲完了，但都是分开的动作。

16.3 节把它们合成一件事：从零做一个可运行的项目 —— 一个任务调度器。

它会把全书的三个部分串起来：

• 拓扑排序（13.1） —— 解析任务之间的依赖
• 优先队列（11.4） —— 按优先级调度
• 哈希表（第 6 章） —— 跟踪每个任务的状态

而且会用上本节这套测量方法 —— 因为它的验收标准里有一条是"性能必须达标"。

这是全书的最后一节，也是把 15 章的知识拧成一股的地方。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "16.2",
  "title": "从复杂度到实测：性能剖析",
  "covered": [
    "「复杂度决定趋势，常数因子决定当下」的总纲",
    "实测一：同一算法的行优先/列优先遍历差 2.15 倍（缓存的影响）",
    "陷阱 1（没预热）的实测：同一个方法两次调用差 3.8 倍，含 JIT 开销的量化",
    "「先测的吃亏、后测的占便宜」这个更隐蔽的表现形式",
    "陷阱 2（只跑一次）的实测：10 轮波动 3%，以及「取最快而非取平均」的理由",
    "陷阱 3（忽略 GC）的实测：分配 4MB 的版本慢 1.7 倍",
    "用 GC.GetAllocatedBytesForCurrentThread 而非 GC.GetTotalMemory 的原因（呼应 12.1）",
    "陷阱 4（忽略噪声区间）的实测：区间不重叠才算真差距（呼应 13.1）",
    "陷阱 5（死代码消除）在 .NET 上较弱、在 C/C++ 上致命的差别",
    "七步可复用测量清单",
    "「多轮只解决随机噪声，解决不了系统偏差」的辨析",
    "「写结论要带适用条件和反例」的示范（练习 16.2.4）"
  ],
  "unresolved": [
    "BenchmarkDotNet 等专业工具未引入（只用 BCL）",
    "CPU 流水线与分支预测只提及未展开（超出本书范围）",
    "16.3 的综合项目留到下一节"
  ],
  "canonical_terms": {
    "常数因子": "复杂度之外影响实际性能的部分，由缓存、分支预测、JIT、GC 等决定",
    "预热（Warm-up）": "正式计时前先跑几遍被测代码，让 JIT 编译和缓存进入稳定状态",
    "噪声区间": "同一段代码多轮测量得到的最小值与最大值构成的区间；重叠则无法区分快慢"
  },
  "symbols_units": {
    "ms": "毫秒（本节所有耗时）",
    "B": "字节（本节所有分配量）"
  },
  "assumptions": [
    "读者已掌握 3.1 的缓存行、12.1 的内存测量教训、13.1 的噪声规矩",
    "本节所有数字都是「故意测出来的」，包括错误测法的数字",
    "机器配置：AMD Ryzen 7 9700X，.NET 8 Release"
  ],
  "word_count_actual": 3042,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑（AMD Ryzen 7 9700X），输出见正文",
    "项目文件：99-tools/samples/Ch16/Sec162/",
    "实验一：4000×4000 矩阵行优先 5.85 ms / 列优先 12.57 ms（2.15 倍），为实测",
    "陷阱 1：ColdSum 首次 0.490 ms / 第二次 0.129 ms（3.8 倍），为实测",
    "陷阱 2：10 轮 5.86~6.06 ms（波动 3%），为实测",
    "陷阱 3：分配 4,000,024 B vs 0 B；耗时 0.635 vs 0.375 ms，为实测",
    "陷阱 4：行 [5.86, 6.71] / 列 [12.70, 16.45]，不重叠，为实测",
    "陷阱 5：结果被使用 5.86 ms vs 被丢弃 5.87 ms（.NET 上差异小），为实测",
    "内存一律用 GC.GetAllocatedBytesForCurrentThread() 测量"
  ],
  "known_issues": [
    "陷阱 1 初版用已被预热过的 SumRowMajor 演示，两次都是 1.48/1.47 ms，完全没演示出 JIT 的影响 —— 改为新加一个从未调用过的 ColdSum 方法，并把数据换成 500×500 的小矩阵（让 JIT 占比可见），才得到 0.490 vs 0.129 ms",
    "实验一初版用 2000×2000 矩阵，缓存差距只有 1.52 倍，说服力不足 —— 改为 4000×4000（61 MB，超出缓存容量），差距拉到 2.15 倍",
    "陷阱 3 初版用 10,000 个 int 的数组，分配量 40 KB、耗时差只有 1.3 倍 —— 改为 1,000,000 个 int（4 MB），差距变成 1.7 倍且能触发 GC",
    "顶级语句里不能声明 static readonly 字段（CS0106），且局部变量必须先声明后使用（CS0165）—— 已把 buffer/sink 提前声明并改为非 static 局部函数"
  ],
  "next": "16.3 综合项目：一个任务调度器"
}