第四章 代码优化 (Writing Correct Programs)

一、导读

1.1 本章学习目标

掌握代码优化的系统性方法，理解"先优化算法，再优化代码"的层次策略

深入理解代码优化中的三大技术：减少操作次数、利用缓存层次、减少分支开销

学会通过性能剖析（Profiling）来定位程序的性能瓶颈，避免盲目优化

掌握循环优化、函数调用优化和内存访问优化的具体技术

理解优化与代码可读性之间的权衡，掌握在不牺牲可维护性的前提下进行优化的方法

学会使用数学分析来预测优化效果，避免"优化了不重要的部分"

理解"80/20 法则"在代码优化中的应用——大部分时间花在少量代码上

1.2 为什么本章如此重要

代码优化是每个程序员都必须面对的现实任务。无论初始设计多么精心，当程序面临更大的数据规模、更严格的响应时间要求或更有限的计算资源时，优化都不可避免。然而，优化也是最容易走入歧途的领域之一：许多程序员花费大量时间优化根本不重要的代码，或者在优化过程中引入了难以调试的错误。

Bentley 在本章中传达的核心思想是：优化应该是有系统、有层次的。首先应该优化算法——将 O(n²) 的算法改为 O(n log n) 可以带来数量级的提升，这远超过任何代码级别的优化。其次应该优化数据结构——选择合适的数据结构可以减少不必要的操作。最后才是代码级别的优化——减少操作次数、利用硬件特性、减少分支开销等。

本章还强调了性能剖析的重要性。Donald Knuth 的名言"过早优化是万恶之源"经常被误解为"不要优化"。实际上，Knuth 的意思是"不要在没有数据支持的情况下盲目优化"。通过性能剖析找到真正的瓶颈，然后集中精力优化瓶颈部分，这才是正确的优化策略。

对于现代软件工程师来说，理解代码优化不仅是为了写出更快的程序，更是为了理解计算机系统的运作方式。优化过程中涉及的知识——CPU 缓存、流水线、分支预测、内存层次结构——对于深入理解计算机系统和编写高效程序都至关重要。

1.3 核心问题引导

为什么应该先优化算法，再优化代码？能否用具体数字说明两者的差异？

如何通过性能剖析来定位程序的性能瓶颈？有哪些常用工具和方法？

循环展开（Loop Unrolling）为什么能提升性能？它的代价是什么？

如何利用 CPU 缓存的特性来优化内存访问模式？

函数调用和递归的开销有多大？如何减少这些开销？

在什么情况下，优化会损害代码的可读性和可维护性？如何权衡？

二、核心概念详解

2.1 优化的层次策略

Bentley 提出了一个清晰的优化层次：首先优化算法，其次优化数据结构，最后才是代码级别的微调。这种层次策略的核心思想是：越高层次的优化，带来的提升越大。

算法层面的优化可以带来数量级的性能提升。例如，将线性搜索改为二分搜索，搜索时间从 O(n) 降到 O(log n)；对于百万级数据，这意味着从百万次操作降到 20 次操作——五万倍的提升。这种提升是任何代码级别的优化都无法企及的。

数据结构层面的优化通常可以消除不必要的操作。例如，将列表改为哈希表，查找操作从 O(n) 降到 O(1)；将无序数据改为有序数据，可以利用二分搜索等高效算法。数据结构的选择往往决定了程序的基本性能特征。

代码层面的优化是在算法和数据结构已经最优的情况下，通过减少操作次数、利用硬件特性来提升性能。这类优化的提升通常在 2 到 10 倍之间，远小于前两个层次。但在某些性能关键的场景中，这些优化仍然很有价值。

2.2 性能剖析与瓶颈定位

性能剖析（Profiling）是优化的第一步，也是最重要的一步。它的目的是找到程序中消耗最多时间的部分——通常被称为"热点"（Hot Spot）。研究表明，在大多数程序中，80% 的执行时间集中在 20% 的代码上。因此，找到并优化这 20% 的代码，就能获得最大的收益。

性能剖析的方法分为两类：基于事件的剖析（Event-based Profiling）和统计剖析（Statistical Profiling）。基于事件的剖析通过在代码中插入计时器来精确测量每个函数的执行时间，精度高但开销大。统计剖析通过定期对调用栈进行采样来估计每个函数的执行时间，精度较低但开销小。

在实际操作中，一个简单的剖析方法是：在程序的关键位置插入时间戳，运行程序后比较各个部分的时间消耗。虽然粗糙，但对于初步定位瓶颈已经足够。更精确的分析可以使用系统提供的剖析工具（如 Linux 的 perf、gprof，Java 的 JProfiler 等）。

2.3 循环优化

循环是程序中最常见的性能瓶颈所在，因为循环体内的操作会被重复执行多次。循环优化的核心目标是减少每次迭代的开销和减少迭代次数。

减少迭代次数的技术包括：循环合并（将多个遍历相同数据的循环合并为一个）、循环消除（如果循环的结果可以预先计算，则直接替换为常量）、部分展开（每次迭代处理多个元素）。

减少每次迭代开销的技术包括：将不变量移出循环（Loop Invariant Code Motion）、减少数组下标计算（使用指针递增替代下标访问）、减少函数调用（将频繁调用的小函数内联展开）。

一个经典的例子是矩阵乘法。朴素的三重循环实现中，内层循环每次迭代都需要计算数组下标。通过重新组织循环顺序（如 i-k-j 顺序）和引入临时变量，可以显著减少下标计算和缓存未命中的次数。这种优化在某些情况下可以将性能提升 5 到 10 倍。

2.4 缓存友好的代码

现代计算机的内存层次结构（寄存器 → L1 缓存 → L2 缓存 → L3 缓存 → 主存 → 磁盘）对程序性能有巨大影响。一次缓存未命中的代价可能是 100 个时钟周期以上，而一次缓存命中只需要 1 到 4 个周期。因此，编写缓存友好的代码是代码优化的重要技术。

缓存友好的核心原则是空间局部性和时间局部性。空间局部性意味着访问一个内存位置后，很可能很快访问其相邻位置。时间局部性意味着访问一个内存位置后，很可能再次访问它。

矩阵遍历的顺序对缓存性能有巨大影响。在 C/C++ 中，二维数组按行存储（Row-major Order），因此按行遍历（外层循环为行，内层循环为列）是缓存友好的，而按列遍历会导致大量的缓存未命中。对于 n × n 的矩阵，两种遍历方式的性能差异可以达到 10 倍以上。

分块技术（Blocking/Tiling）是另一种缓存优化方法：将大矩阵分成适合缓存的小块，每次处理一个块。这样可以最大化缓存的利用率，减少缓存被替换的次数。分块技术在矩阵乘法、卷积运算等密集计算中效果显著。

2.5 代码速度与代码大小的权衡

许多优化技术涉及代码速度与代码大小（Space-Time Tradeoff）的权衡。循环展开通过复制循环体来减少循环控制的开销，但增加了代码大小。查找表（Lookup Table）通过预计算结果来避免运行时计算，但需要额外的存储空间。内联展开通过消除函数调用来减少开销，但增加了代码大小并可能影响指令缓存。

这些权衡在不同场景下的选择不同。在嵌入式系统中，内存通常非常有限，代码大小的增加可能不可接受。在桌面或服务器应用中，内存通常充裕，可以更多地使用空间换时间的策略。

Bentley 提醒我们，这些权衡不是绝对的。现代编译器的优化能力已经相当强大，许多手动优化（如循环展开、函数内联）编译器可以自动完成。在某些情况下，手动优化反而可能干扰编译器的优化策略，导致性能下降。因此，在代码级别优化时，应该先测量效果，确认优化确实有效后再采用。

三、深入分析与讨论

3.1 优化的正确性验证

优化代码时最容易引入错误，因为优化往往涉及对代码逻辑的微调，而这些微调可能改变程序的行为。因此，每次优化后都应该验证程序的正确性。

验证优化的正确性有几种方法：单元测试是最基本的，确保优化后的代码在所有测试用例上产生相同的结果。形式化验证（Formal Verification）可以在数学上证明优化的等价性，但成本较高。随机测试（Randomized Testing）通过大量随机输入来检验优化前后的输出一致性，是一种实用的折中方案。

Bentley 强调了一个重要原则：优化应该在已经验证正确的代码上进行。先确保程序正确，然后再优化性能。如果在优化过程中引入了错误，应该回退到优化前的版本，而不是在错误的代码上继续调试。

3.2 编译器优化与手动优化

现代编译器（如 GCC、Clang、MSVC）已经具备强大的自动优化能力。在开启优化选项（如 -O2 或 -O3）后，编译器可以自动完成许多常见的优化：常量折叠、死代码消除、循环不变量外提、函数内联、循环展开等。

在某些情况下，手动优化与编译器优化可能产生冲突。例如，手动展开的循环可能干扰编译器的向量化（Vectorization）优化；手动内联的函数可能增加代码大小，导致指令缓存效率下降。因此，在进行手动优化之前，应该先了解编译器的优化能力，避免做编译器已经能做的事情。

另一个重要的考虑是代码的可移植性。某些手动优化依赖于特定的硬件特性（如 SIMD 指令、特定的缓存大小），在不同平台上可能无效甚至有害。使用编译器提供的内联汇编或平台特定的优化选项，可以在保持可移植性的同时利用硬件特性。

3.3 优化的收益递减

代码优化存在收益递减的规律：最初的优化（算法改进、数据结构选择）可以带来巨大的性能提升，而后续的优化（代码微调、缓存优化）带来的提升越来越小，但所需的时间和精力却越来越多。

在实践中，应该设定一个性能目标，达到目标后就停止优化。过度优化不仅浪费时间，还可能降低代码的可读性和可维护性。正如 Bentley 所说："让正确的程序更快"应该先于"让程序更快再确保正确"。优化的最终目标是让程序满足性能需求，而不是追求理论上的最优。

四、实践案例

4.1 字符串搜索的优化

字符串搜索是一个经典的优化案例。朴素的字符串匹配算法（Brute Force）在最坏情况下需要 O(n × m) 的时间，其中 n 是文本长度，m 是模式长度。通过优化，可以逐步提升性能。

第一步优化是使用 KMP（Knuth-Morris-Pratt）算法，通过预处理模式串构建部分匹配表（Failure Function），避免文本指针的回溯。这将最坏情况时间降到了 O(n + m)。

第二步优化是 Boyer-Moore 算法，利用"坏字符规则"和"好后缀规则"从右向左匹配模式串，在许多实际场景中可以跳过大量文本字符，平均比较次数远小于 n。

第三步优化是 Rabin-Karp 算法，使用滚动哈希函数在 O(1) 时间内计算子串的哈希值，只在哈希值匹配时才进行逐字符比较。这种基于哈希的方法在搜索多个模式时特别高效。

4.2 矩阵乘法的优化历程

矩阵乘法是数值计算中最基本的操作之一，其优化历程展示了代码优化的多个层次。

最朴素的实现是三重循环（i-j-k 顺序），时间复杂度 O(n³)。第一步优化是调整循环顺序为 i-k-j，利用数组的行主序存储特性，将缓存未命中次数从 O(n³) 降到 O(n³/B)，其中 B 是缓存行大小。

第二步优化是分块（Blocking）：将矩阵分成 B × B 的小块，使得每个块可以放入缓存。这将缓存未命中进一步减少，在实际测试中可以将性能提升 3 到 5 倍。

第三步优化是利用 SIMD 指令（如 SSE、AVX）进行向量化计算：一条指令同时处理多个数据元素。例如，使用 256 位 AVX 指令可以同时计算 8 个浮点乘法，将理论峰值性能提升 8 倍。

五、常见误区与注意事项

5.1 优化不重要的代码

最常见的优化错误是花大量时间优化只占程序总执行时间很小比例的代码。通过性能剖析找到热点后，应该集中力量优化热点，而不是在无关紧要的地方做微调。

5.2 忽视算法层面的优化

许多程序员一提到优化就想到代码级别的技巧（循环展开、内联等），却忽视了算法层面的优化。将 O(n²) 改为 O(n log n) 的提升远超过任何代码级别的优化。在开始代码优化之前，先确认算法已经是最优的。

5.3 优化后不验证正确性

优化过程中容易引入微妙的错误。每次优化后都应该运行完整的测试套件，确保程序行为没有改变。对于数值计算，还需要注意精度变化：某些优化（如改变运算顺序）可能影响浮点运算的精度。

5.4 过度优化损害可读性

代码的可读性和可维护性同样重要。如果一个优化使代码变得晦涩难懂，但只带来 5% 的性能提升，那么这种优化通常不值得。只有在性能确实是瓶颈，且提升显著时，才应该考虑牺牲一定的可读性。

5.5 不进行测量就优化

没有测量就没有优化。在优化之前，必须先通过性能剖析了解程序的实际瓶颈。凭直觉优化往往事倍功半。同样，优化后也需要测量效果，确认优化确实有效。

六、本章小结

本章系统地介绍了代码优化的方法和原则。优化的核心策略是分层进行：先优化算法（数量级提升），再优化数据结构（消除冗余操作），最后才是代码级别的微调（常数因子优化）。性能剖析是优化的前提——通过测量找到真正的瓶颈，避免盲目优化。循环优化、缓存友好编程和代码大小-速度权衡是代码级别优化的三大主题。优化过程中必须始终关注正确性：先确保程序正确，再进行优化；每次优化后都要验证结果。最后，优化应该有度——达到性能目标后就停止，避免过度优化损害代码质量。

七、思考题与练习

对一个冒泡排序的实现进行优化：首先改进算法（如使用快速排序），然后优化代码（如循环展开、缓存友好），比较每一步的性能提升。

实现矩阵乘法的三种版本（朴素、循环重排、分块），在 1000 × 1000 的矩阵上测量性能差异。

使用性能剖析工具（如 perf、gprof）分析一个实际程序的性能瓶颈，并针对瓶颈进行优化。

实现字符串搜索的三种算法（朴素、KMP、Boyer-Moore），在不同长度的文本和模式上比较性能。

分析以下代码的性能瓶颈并提出优化方案：一个频繁调用的函数，内部包含大量的字符串拼接操作。

比较查找表方法和实时计算方法在三角函数（sin/cos）计算中的性能和精度。

实现一个缓存友好的二维数组遍历，比较行主序和列主序遍历在不同矩阵大小下的性能差异。

讨论：在什么情况下，"不优化"是最好的策略？给出你的判断标准。