性能优化的一般策略及方法
在汽车嵌入式开发领域，性能优化始终是一个无法回避的问题：
- 座舱 HMI 想要实现更流畅的人机交互
- 通信中间件在给定的 CPU 资源下，追求更高的吞吐量
- 更一般的场景：嵌入式设备 CPU 资源告急，需要降低 CPU 使用率...
不同的工程师会从不同的角度给出不同的优化建议：
- 有人关注系统调用情况
- 有人建议从算法和数据结构入手
- 有人建议避免递归、循环嵌套
- 有人会从存储器层次结构出发，建议修改代码提高缓存命中率来提升性能
- ...
这些都是具体的代码调优技术/技巧，或许有效，但不够系统。本文不讨论具体的代码调优技术，而是想介绍下具体代码优化技巧之上，更高层次的优化策略。比起代码级别的调优，可能效果更好，成本更低。
开始之前，需要强调下：
Premature optimization is the root of all evil. — Donald Knuth
一、性能概述
代码调优只是代码性能优化的方法之一，还有其他性能优化的方法，也许效果更好、成本更低、对代码的负面影响（降低可读性/可维护性、引入 bug 等）也更少。
1.1 软件质量和性能
性能只是众多软件质量标准中的一个。比起单纯的代码执行速度，用户可能更在意其他方面，比如稳定可靠、简洁易用等。
性能也不只是代码的执行速度，过分追求代码的执行速度而忽略其他方面可能会影响整体性能及软件质量。
1.2 性能和代码调优
假如确定了把 Efficiency 作为首要目标，在代码调优之前，请优先考虑：
- 性能需求
- 程序设计
- 类和方法设计
- 操作系统交互
- 编译器优化
- 硬件升级
- 代码调优
a. 性能需求
Barry Boehm 讲过一个故事：某系统一开始要求亚秒级的响应时间，导致非常复杂的设计，预估成本 1 亿美元。后来分析发现，90%的情况下，用户可以接受 4s 的响应时间。重新修改需求之后，节省了 7000 万美元。
再举一个例子，自动驾驶算法需要周期性获取某些车辆数据，当前的需求是 10ms 的周期上报。如果将周期改为 20ms 仍然可以满足需求，那么不需要任何额外的优化，CPU 占用率便可减少一半。
解决性能问题之前，先确认是否真的必要。
b. 程序设计
软件架构设计主要如何将程序分解到模块/类。有的设计决定了很难实现高性能，有的设计则容易实现高性能。
在软件的架构设计中，设定资源占用的目标很重要：如果每个组件都能达成目标，则整个系统自然也可以。如果某个组件无法达成目标，也可以及早发现，进行设计修改或代码优化。不仅如此，清晰的目标也更利于执行和实施。
c. 类和方法设计
在程序设计基础上更近一步，深入到类的内部。在这一层级，我们可以选择数据结构和算法，从而影响程序的执行速度和内存占用。
d. 操作系统交互
如果程序中涉及外部文件、动态内存、输出设备，通常会和操作系统交互。如果程序性能不好，有可能就是系统调用过多导致的。有时系统库或编译器会在你意想不到的地方产生系统调用。
e. 编译器
编译器优化比手工优化代码效果更好，也更安全！某种程度上来说，选择了正确的编译器，基本就不需要考虑代码级优化了。
f. 硬件
有时候升级硬件是解决性能问题成本最低的方案。不仅节省了性能优化的人力成本，同时还避免了由于性能优化引入的一系列隐性成本。同时，所有其他程序也因为硬件升级而得到性能提升。
g. 代码调优（Code Tuning）
“代码调优”指的是修改正确的代码，使之运行得更快。代码调优的前提是代码正确：设计良好，易于理解和修改。“调优”指的是小规模修改，一个类，一个函数或者几行代码。“调优”不包括大规模设计修改，以及更高层次的性能优化手段。
上面从程序设计到代码调优六个层级中，每一个层级都可能产生 10 倍的性能提升，不同层级的组合起来理论上可以有百万倍的提升。虽然实际不可能在每个层级都取得 10 倍的提升，但是这里想表达的是，性能优化的空间潜力是巨大的。
二、代码调优
2.1 二八法则
a. 优化哪里
有研究和报告表明：
- 20% 的函数占用了 80% 的程序执行时间
- <4% 的代码甚至能占用 50% 的执行时间
不是每一行代码都要做到最快，真正值得花时间把性能调到极致的代码只有很小的一部分！
b. 谁来优化
项目中系统整体的 CPU 接近满负荷，其中 A 负责的模块 CPU 占用 5%，而 B 负责的模块 CPU 占用超过 60%。即便 A 再厉害，把自己优化没了，带来的整体收益也不过 5%，而 B 却因为有更大的优化空间，能轻松地地降低 10%的 CPU 占用。
2.2 常见误区
很多过时的、传说中的代码优化技巧都是无效的，甚至能够产生负面影响。
误区 1: 代码行数越少，程序越快
很容易找到一个反例：初始化大小为 N 的数组，直接写出 N 条赋值语句，其性能是循环赋值的 2.5～4 倍！
误区 2: xxxx 写法很很可能更快
对于性能而言，没有所谓的“很可能”，必须实际测量才知道到底是“优化”了还是“劣化”了。影响性能的因素很多：处理器架构、编程语言、编译器、编译器版本、库、库的版本、内存大小...“很可能”是非常不负责任的说法，对于特定的环境是优化，在另外环境下很能就是劣化。再次强调，必须要实际测量！
此外，为了“性能优化”而引入的特殊写法，反而会影响编译器的优化。
误区 3: 从一开始就写要出“快”的代码
在程序没最终完成之前，几乎不可能识别出真正的性能瓶颈，你所“优化”的代码中，96%其实不需要优化。过分关注执行速度反而会影响软件质量的其他方面。
Premature optimization is the root of all evil. — Donald Knuth
误区 4: “快”和“正确”同等重要
如果程序不能正确运行，或者运行结果不正确，即使再快也没有任何价值。
2.3 什么时候去调优
Jackson's Rule of Optimization:
Rule 1. Don't do it.
Rule 2 (for expert only). Don't do it yet -- that is, not until you have a perfectly clear and unoptimized solution.
简言之，非必要，不优化。先保证良好的设计，编写易于理解和修改的整洁代码。如果现有的代码很糟糕，先清理重构，然后再考虑优化。
2.4 编译器优化
现代编译器优化远比你想象中的更强大。例如编译器能够识别并优化循环嵌套，比手动优化更安全，效果也更好。不要自作聪明地用一些几十年前所谓的特殊“优化技巧”，大概率会给编译器造成困扰，适得其反。
-
各家的编译器各有优缺点，选择最适合项目的编译器
-
开启编译器的不同优化选项，性能可提升为原来的 2 倍甚至更多
程序员应该专注于写整洁代码（设计良好，意图明确清晰，可读性好，易于维护），优化的事情交给编译器就好啦！
三、导致性能问题的常见原因
3.1 常见性能问题元凶
a. 输入/输出操作
不必要的 I/O 操作是最常见的导致性能问题的罪魁祸首。比如频繁读写磁盘上的文件、通过网络访问数据库等。一般来说，内存的读写性能是磁盘的几千几万倍，如果有内存不是很 critical，可以将数据保存在内存中以减少不必要的 IO 操作从而改善性能。
几年前在一个基于 Qt 的座舱项目中，从 CarPlay 界面返回车机首页会有短暂的卡顿，导致无法通过 CarPlay 的认证。用 QmlProfiler 分析发现，切换卡顿是由于从磁盘加载背景图片导致的，将背景图片缓存在内存中，可以直接消除图片加载时间，大幅提升界面切换的流畅度。代价是牺牲了一定的内存，这是一个空间换时间的典型例子。
b. 缺页
有一个经典的例子：
// BAD
for (int col = 0; col < MAX_COLUMNS; ++col) {
for(int row = 0; row < MAX_ROWS; ++row) {
table[row][col] = GetDefaultValue();
}
}
// GOOD
for (int row = 0; row < MAX_ROWS; ++row) {
for(int col = 0; col < MAX_COLUMNS; ++col) {
table[row][col] = GetDefaultValue();
}
}
以上两种写法在特定场景下，性能差距可达 1000 倍。背后涉及到二维数组在内存中的存储方式以及缓存命中等知识，CSAPP 的第 5、6 章对此有详细阐述。
c. 系统调用
系统调用需要进行上下文切换，保存程序状态、恢复内核状态等一些步骤，开销相对较大。对磁盘的读写操作、对键盘、屏幕等外设的操作、内存管理函数的调用等都属于系统调用。
Linux 系统调用可以通过 strace 查看，qnx 也有 tracelogger 等工具
d. 解释型语言
一般来说，C/C++/VB/C# 这种编译型语言的性能好于 Java 的字节码，好于 PHP/Pyhon 等解释型语言。这也是为什么汽车嵌入式领域还是 C/C++ 天下等主要原因。
e. 错误
还有很大很一部分导致性能问题的原因可以归为错误：忘了把调试代码（如保存 trace 到文件）关闭，忘记释放资源/内存泄漏、数据库表设计缺陷（常用表没有索引）等。
3.2 常见操作的相对开销
| 操作 | 示例 | 相对耗时（C++） |
|---|---|---|
| 整数赋值（基准） | i = j |
1 |
| 函数调用 | ||
| 普通函数调用（无参） | foo() |
1 |
| 普通函数调用（单参） | foo(i) |
1.5 |
| 普通函数调用（双参） | foo(i,j) |
2 |
| 类的成员函数调用 | bar.foo() |
2 |
| 子类的成员函数调用 | derivedBar.foo() |
2 |
| 多态方法调用 | abstractBar.foo() |
2.5 |
| 对象解引用 | ||
| 访问对象成员（一级/二级） | i = obj1.obj2.num |
1 |
| 整数运算 | ||
| 整数赋值/加/减/乘 | i = j * k |
1 |
| 整数除法 | i = j / k |
5 |
| 浮点运算 | ||
| 浮点赋值/加/减/乘 | x = y * z |
1 |
| 浮点除法 | x = y / z |
4 |
| 超越函数 | ||
| 浮点根号 | y = sqrt(x) |
15 |
| 浮点 sin | y = sin(x) |
25 |
| 浮点对数 | y = log(x) |
25 |
| 浮点指数 | y = exp(x) |
50 |
| 数组操作 | ||
| 一维/二维整数/浮点数组下标访问 | x = a[3][j] |
1 |
注：上表仅供参考，不同处理器、不同语言、不同编译器、不同测试环境所得结果可能相差很大！
代码调优的方式之一就是用低开销的操作替代高开销操作。一般操作（赋值、函数调用、算数运算）的开销基本相同，除法运算开销较大，超越函数开销尤其巨大，多态函数的调用较普通函数调用有一定额外开销。
四、测量
代码执行耗时和代码量不成比例，必须经过测量才知道时间花在哪里。找到问题，优化，重新测量。
性能优化很多时候是反直觉的（比如代码量越少不一定越快），只有测量了才知道是否有效果。
过往的经验可能不会有太多帮助，针对旧的机器、语言、编译器的优化经验在现在可能完全不适用，必须要实际测量了才知道！
比如在旧版本的编译器中，把二维数组的操作转为对单个指针操作可以提升性能，而在新的编译器却完全没有效果，因为新版编译器会自动进行这样的转化。而手动修改代码只会降低代码的可读性。
测量要准确
- 用专门的 Profiling 工具或者系统时间
- 只测量你自己的代码部分
- 必要时需要用 CPU 时钟 tick 数来替代时间戳以获得更准确的测量结果
要想准确的测量是一件非常困难的事情。不同的硬件、进程的优先级、线程调度策略、测量时其他的进程的运行、甚至外界环境都可能对测量结果产生影响。我们能做的就是尽可能地控制变量，剔除无关因素影响。
五、迭代
很难只用一个技巧就把性能提升 10 倍，但是可以不断尝试，组合不同技巧，最终实现巨大的性能提升。下面是一个通过不断迭代优化，将执行时间从 21 分 40 秒优化到 22 秒的例子：
| 优化项 | 执行时间 |
|---|---|
| 初版，直接实现 | 21:40 |
| bit 转数组 | 7:30 |
| 展开最内层 for 循环 | 6:00 |
| 去除最终排列 | 5:24 |
| 合并 2 个变量 | 5:06 |
| 合并算法的前两步 | 4:30 |
| 在内层循环中，使两个变量共享同一内存 | 3:36 |
| 在外层循环中，使两个变量共享同一内存 | 3:09 |
| 展开所有循环，使用字面量下标 | 1:36 |
| 去除所有函数调用，把代码写在一行 | 0:45 |
| 用汇编重写整个函数 | 0:22 |
六、调优一般方法
- 程序设计良好，易于理解和修改（前提）
- 如果性能不佳：
a. 保存当前状态
b. 测量，找出时间主要消耗在哪里
c. 分析问题：是否因为高层设计、数据结构、算法导致的，如果是，返回步骤 1
d. 如果设计、数据结构、算法没问题，针对上述步骤中的瓶颈进行代码调优
e. 每进行一项优化，立即进行测量
f. 如果没有效果，恢复到 a 的状态。（大多数的调优尝试几乎不会对性能产生影响，甚至产生负面影响。代码调优的前提是代码设计良好，易于理解和修改。Code tuning 通常会对设计、可读性、可维护性产生负面影响，如果 tuning 改良了设计或者可读性，那么不应该叫 tuning，而是属于步骤 1） - 重复步骤 2
七、总结
- 性能只是众多软件质量指标中的一个，而且一般不是最重要的那个。精心调优之后的代码也只能对整体性能产生部分影响，程序架构、详细设计、数据结构/算法的选择、编译器通常比代码本身对性能的影响更大。
- 准确地测量至关重要
- 绝大多数程序的大部分时间都耗在少数代码上，只有测量了才知道时间花在了哪里，优化重点在哪里
- 很多“优化技巧”实际上不仅不会提高性能，甚至会降低性能，只有测量了才能知道
- 测量越接近真实环境越好，模拟的测试环境和程序实际运行环境可能得到完全不同的结果！
- 通常需要多轮优化迭代才能达到预期性能目标
- 如果想为今后（可能）的性能优化提前作准备，最好的准备就是编写易于理解和修改的整洁代码
7.1 检查清单
- 明确需求，是否真的有这么高的性能要求？
- 尝试提高编译器优化选项？
- 考虑升级/更换编译器？
- 考虑过升级/更换硬件？
- 程序的 high-level design、类设计是否合理？
- 检查是否有不必要的系统调用、I/O 操作？
- 考虑用编译型语言替代解释型语言？
- 代码调优是否作为最后手段？
7.2 代码调优方法
- 调优的前提：代码正确，设计良好，易于理解和修改
- 测量，找出瓶颈
- 每次优化后，立即重新测量
- 如果没有效果，撤销改动
- 尝试多种方法，不断迭代
八、扩展阅读
- 《CSAPP》第 5、6 章
- 《Code Complete》第 25、26 章
- 《C++ Core Guidelines》Per 章节