前言.......................................................................................................................................................xvii 第 1 章 优化概述................................................................................................................................1

1.1 优化是软件开发的一部分 ......................................................................................................... 2 1.2 优化是高效的 ............................................................................................................................. 3 1.3 优化是没有问题的 ..................................................................................................................... 3 1.4 这儿一纳秒，那儿一纳秒 ......................................................................................................... 5 1.5 C++ 代码优化策略总结.............................................................................................................5

1.5.1 用好的编译器并用好编译器 ........................................................................................6 1.5.2 使用更好的算法 ............................................................................................................7 1.5.3 使用更好的库 ................................................................................................................8 1.5.4 减少内存分配和复制 ....................................................................................................9 1.5.5 移除计算 ........................................................................................................................9 1.5.6 使用更好的数据结构 ....................................................................................................9 1.5.7 提高并发性 ..................................................................................................................10 1.5.8 优化内存管理 ..............................................................................................................10

1.6 小结 ........................................................................................................................................... 10 第 2 章 影响优化的计算机行为...................................................................................................11

2.1 C++ 所相信的计算机谎言.......................................................................................................12 2.2 计算机的真相 ........................................................................................................................... 12 2.2.1 内存很慢 ......................................................................................................................13 2.2.2 内存访问并非以字节为单位 ......................................................................................13 2.2.3 某些内存访问会比其他的更慢 ..................................................................................14

目录

vii

2.2.4 内存字分为大端和小端 ..............................................................................................14 2.2.5 内存容量是有限的 ......................................................................................................15 2.2.6 指令执行缓慢 ..............................................................................................................16 2.2.7 计算机难以作决定 ......................................................................................................16 2.2.8 程序执行中的多个流 ..................................................................................................16 2.2.9 调用操作系统的开销是昂贵的 ..................................................................................18

2.3 C++ 也会说谎...........................................................................................................................18 2.3.1 并非所有语句的性能开销都相同 ..............................................................................18 2.3.2 语句并非按顺序执行 ..................................................................................................18

2.4 小结 ........................................................................................................................................... 19 第 3 章 测量性能..............................................................................................................................20

3.1 优化思想 ................................................................................................................................... 21 3.1.1 必须测量性能 ..............................................................................................................21 3.1.2 优化器是王牌猎人 ......................................................................................................21 3.1.3 90/10 规则 ....................................................................................................................22 3.1.4 阿姆达尔定律 ..............................................................................................................23

3.2 进行实验 ................................................................................................................................... 24 3.2.1 记实验笔记 ..................................................................................................................26 3.2.2 测量基准性能并设定目标 ..........................................................................................26 3.2.3 你只能改善你能够测量的 ..........................................................................................28

3.3 分析程序执行 ........................................................................................................................... 28 3.4 测量长时间运行的代码 ........................................................................................................... 30 3.4.1 一点关于测量时间的知识 ..........................................................................................30 3.4.2 用计算机测量时间 ......................................................................................................35 3.4.3 克服测量障碍 ..............................................................................................................41 3.4.4 创建 stopwatch 类.......................................................................................................44 3.4.5 使用测试套件测量热点函数 ......................................................................................48 3.5 评估代码开销来找出热点代码 ............................................................................................... 48 3.5.1 评估独立的 C++ 语句的开销 .....................................................................................49 3.5.2 评估循环的开销 ..........................................................................................................49 3.6 其他找出热点代码的方法 ....................................................................................................... 51 3.7 小结 ........................................................................................................................................... 51

第 4 章 优化字符串的使用:案例研究......................................................................................53 4.1 为什么字符串很麻烦 ............................................................................................................... 53

4.1.1 字符串是动态分配的 ..................................................................................................54 viii | 目录

4.1.2 字符串就是值 ..............................................................................................................54

4.1.3 字符串会进行大量复制 ..............................................................................................55 4.2 第一次尝试优化字符串 ........................................................................................................... 56 4.2.1 使用复合赋值操作避免临时字符串 ..........................................................................57 4.2.2 通过预留存储空间减少内存的重新分配 ..................................................................57 4.2.3 消除对参数字符串的复制 ..........................................................................................58 4.2.4 使用迭代器消除指针解引 ..........................................................................................59 4.2.5 消除对返回的字符串的复制 ......................................................................................59 4.2.6 用字符数组代替字符串 ..............................................................................................60 4.2.7 第一次优化总结 ..........................................................................................................62 4.3 第二次尝试优化字符串 ........................................................................................................... 62 4.3.1 使用更好的算法 ..........................................................................................................62 4.3.2 使用更好的编译器 ......................................................................................................64 4.3.3 使用更好的字符串库 ..................................................................................................64 4.3.4 使用更好的内存分配器 ..............................................................................................67 4.4 消除字符串转换 ....................................................................................................................... 69 4.4.1 将 C 字符串转换为 std::string................................................................................69 4.4.2 不同字符集间的转换 ..................................................................................................70 4.5 小结 ........................................................................................................................................... 70

第 5 章 优化算法..............................................................................................................................71

5.1 算法的时间开销 ....................................................................................................................... 72 5.1.1 最优情况、平均情况和最差情况的时间开销 ..........................................................74 5.1.2 摊销时间开销 ..............................................................................................................74 5.1.3 其他开销 ......................................................................................................................75

5.2 优化查找和排序的工具箱 ....................................................................................................... 75 5.3 高效查找算法 ........................................................................................................................... 75 5.3.1 查找算法的时间开销 ..................................................................................................75 5.3.2 当 n 很小时，所有算法的时间开销都一样 ..............................................................76 5.4 高效排序算法 ........................................................................................................................... 77 5.4.1 排序算法的时间开销 ..................................................................................................77 5.4.2 替换在最差情况下性能较差的排序算法 ..................................................................77 5.4.3 利用输入数据集的已知特性 ......................................................................................78 5.5 优化模式 ................................................................................................................................... 78 5.5.1 预计算 ..........................................................................................................................79 5.5.2 延迟计算 ......................................................................................................................80 5.5.3 批量处理 ......................................................................................................................80

目录 | ix

5.5.4 缓存 ..............................................................................................................................80 5.5.5 特化 ..............................................................................................................................81 5.5.6 提高处理量 ..................................................................................................................81 5.5.7 提示 ..............................................................................................................................81 5.5.8 优化期待路径 ..............................................................................................................82 5.5.9 散列法 ..........................................................................................................................82 5.5.10 双重检查 ....................................................................................................................82

5.6 小结 ........................................................................................................................................... 82 第 6 章 优化动态分配内存的变量...............................................................................................83

6.1 C++ 变量回顾...........................................................................................................................84 6.1.1 变量的存储期 ..............................................................................................................84 6.1.2 变量的所有权 ..............................................................................................................86 6.1.3 值对象与实体对象 ......................................................................................................86

6.2 C++ 动态变量 API 回顾 ..........................................................................................................88 6.2.1 使用智能指针实现动态变量所有权的自动化 ..........................................................90 6.2.2 动态变量有运行时开销 ..............................................................................................92

6.3 减少动态变量的使用 ............................................................................................................... 92 6.3.1 静态地创建类实例 ......................................................................................................92 6.3.2 使用静态数据结构 ......................................................................................................93 6.3.3 使用 std::make_shared 替代 new 表达式..................................................................97 6.3.4 不要无谓地共享所有权 ..............................................................................................97 6.3.5 使用“主指针”拥有动态变量 ..................................................................................98

6.4 减少动态变量的重新分配 ....................................................................................................... 99 6.4.1 预分配动态变量以防止重新分配 ..............................................................................99 6.4.2 在循环外创建动态变量 ..............................................................................................99

6.5 移除无谓的复制 ..................................................................................................................... 100 6.5.1 在类定义中禁止不希望发生的复制 ........................................................................101 6.5.2 移除函数调用上的复制 ............................................................................................102 6.5.3 移除函数返回上的复制 ............................................................................................103 6.5.4 免复制库 ....................................................................................................................105 6.5.5 实现写时复制惯用法 ................................................................................................106 6.5.6 切割数据结构 ............................................................................................................106

6.6 实现移动语义 ......................................................................................................................... 107 6.6.1 非标准复制语义:痛苦的实现 ................................................................................107 6.6.2 std::swap():“穷人”的移动语义 .........................................................................108 6.6.3 共享所有权的实体 ....................................................................................................109

x | 目录

6.6.4 移动语义的移动部分 ................................................................................................109 6.6.5 更新代码以使用移动语义 ........................................................................................ 110 6.6.6 移动语义的微妙之处 ................................................................................................ 111

6.7 扁平数据结构 ......................................................................................................................... 113 6.8 小结 ......................................................................................................................................... 113

第 7 章 优化热点语句...................................................................................................................115

7.1 从循环中移除代码 ................................................................................................................. 116 7.1.1 缓存循环结束条件值 ................................................................................................ 117 7.1.2 使用更高效的循环语句 ............................................................................................ 117 7.1.3 用递减替代递增 ........................................................................................................ 118 7.1.4 从循环中移除不变性代码 ........................................................................................ 118 7.1.5 从循环中移除无谓的函数调用 ................................................................................ 119 7.1.6 从循环中移除隐含的函数调用 ................................................................................121 7.1.7 从循环中移除昂贵的、缓慢改变的调用 ................................................................123 7.1.8 将循环放入函数以减少调用开销 ............................................................................123 7.1.9 不要频繁地进行操作 ................................................................................................124 7.1.10 其他优化技巧 ..........................................................................................................126

7.2 从函数中移除代码 ................................................................................................................. 126 7.2.1 函数调用的开销 ........................................................................................................126 7.2.2 简短地声明内联函数 ................................................................................................129 7.2.3 在使用之前定义函数 ................................................................................................129 7.2.4 移除未使用的多态性 ................................................................................................130 7.2.5 放弃不使用的接口 ....................................................................................................130 7.2.6 用模板在编译时选择实现 ........................................................................................133 7.2.7 避免使用 PIMPL 惯用法...........................................................................................134 7.2.8 移除对 DDL 的调用 .................................................................................................. 135 7.2.9 使用静态成员函数取代成员函数 ............................................................................136 7.2.10 将虚析构函数移至基类中 ......................................................................................136

7.3 优化表达式 ............................................................................................................................. 137 7.3.1 简化表达式 ................................................................................................................137 7.3.2 将常量组合在一起 ....................................................................................................138 7.3.3 使用更高效的运算符 ................................................................................................139 7.3.4 使用整数计算替代浮点型计算 ................................................................................139 7.3.5 双精度类型可能会比浮点型更快 ............................................................................140 7.3.6 用闭形式替代迭代计算 ............................................................................................141

7.4 优化控制流程惯用法 ............................................................................................................. 142 目录 | xi

7.4.1 用 switch 替代 if-else if-else...........................................................................142 7.4.2 用虚函数替代 switch 或 if......................................................................................143 7.4.3 使用无开销的异常处理 ............................................................................................144

7.5 小结 ......................................................................................................................................... 145 第 8 章 使用更好的库...................................................................................................................146

8.1 优化标准库的使用 ................................................................................................................. 146 8.1.1 C++ 标准库的哲学 ....................................................................................................147 8.1.2 使用 C++ 标准库的注意事项 ...................................................................................147

8.2 优化现有库 ............................................................................................................................. 149 8.2.1 改动越少越好 ............................................................................................................149 8.2.2 添加函数，不要改动功能 ........................................................................................150

8.3 设计优化库 ............................................................................................................................. 150 8.3.1 草率编码后悔多 ........................................................................................................150 8.3.2 在库的设计上，简约是一种美德 ............................................................................151 8.3.3 不要在库内分配内存 ................................................................................................152 8.3.4 若有疑问，以速度为准 ............................................................................................152 8.3.5 函数比框架更容易优化 ............................................................................................152 8.3.6 扁平继承层次关系 ....................................................................................................153 8.3.7 扁平调用链 ................................................................................................................153 8.3.8 扁平分层设计 ............................................................................................................153 8.3.9 避免动态查找 ............................................................................................................154 8.3.10 留意“上帝函数”.................................................................................................... 155

8.4 小结 ......................................................................................................................................... 156 第 9 章 优化查找和排序 ..............................................................................................................157

9.1 使用 std::map 和 std::string 的键值对表 ........................................................................158 9.2 改善查找性能的工具箱 ......................................................................................................... 159 9.2.1 进行一次基准测量 ....................................................................................................160 9.2.2 识别出待优化的活动 ................................................................................................160 9.2.3 分解待优化的活动 ....................................................................................................160 9.2.4 修改或替换算法和数据结构 ....................................................................................161 9.2.5 在自定义抽象上应用优化过程 ................................................................................162 9.3 优化 std::map 的查找 ...........................................................................................................163 9.3.1 以固定长度的字符数组作为 std::map 的键...........................................................163 9.3.2 以 C 风格的字符串组作为键使用 std::map ...........................................................164 9.3.3 当键就是值的时候，使用 map 的表亲 std::set ....................................................166

xii | 目录

图灵社区会员 ChenyangGao(2339083510@qq.com) 专享 尊重版权

9.4 使用 <algorithm> 头文件优化算法......................................................................................167 9.4.1 以序列容器作为被查找的键值对表 ........................................................................168 9.4.2 std::find():功能如其名，O(n) 时间开销.............................................................169 9.4.3 std::binary_search():不返回值 .......................................................................... 169 9.4.4 使用 std::equal_range() 的二分查找....................................................................170 9.4.5 使用 std::lower_bound() 的二分查找....................................................................170 9.4.6 自己编写二分查找法 ................................................................................................171 9.4.7 使用 strcmp() 自己编写二分查找法.......................................................................172

9.5 优化键值对散列表中的查找 ................................................................................................. 173 9.5.1 使用 std::unordered_map 进行散列........................................................................173 9.5.2 对固定长度字符数组的键进行散列 ........................................................................174 9.5.3 以空字符结尾的字符串为键进行散列 ....................................................................175 9.5.4 用自定义的散列表进行散列 ....................................................................................176

9.6 斯特潘诺夫的抽象惩罚 ......................................................................................................... 177 9.7 使用 C++ 标准库优化排序....................................................................................................178 9.8 小结 ......................................................................................................................................... 179

第 10 章 优化数据结构 ................................................................................................................181

10.1 理解标准库容器 ................................................................................................................... 181 10.1.1 序列容器 ................................................................................................................. 182 10.1.2 关联容器 ................................................................................................................. 182 10.1.3 测试标准库容器 ..................................................................................................... 183

10.2 std::vector 与 std::string ..............................................................................................187 10.2.1 重新分配的性能影响 ............................................................................................. 188 10.2.2 std::vector 中的插入与删除...............................................................................188 10.2.3 遍历 std::vector...................................................................................................190 10.2.4 对 std::vector 排序..............................................................................................191 10.2.5 查找 std::vector...................................................................................................191

10.3 std::deque............................................................................................................................191 10.3.1 std::deque 中的插入和删除.................................................................................193 10.3.2 遍历 std::deque.....................................................................................................194 10.3.3 对 std::deque 的排序............................................................................................194 10.3.4 查找 std::deque.....................................................................................................194

10.4 std::list.............................................................................................................................. 194 10.4.1 std::list 中的插入和删除...................................................................................196 10.4.2 遍历 std::list 中..................................................................................................197 10.4.3 对 std::list 排序..................................................................................................197

目录 | xiii 图灵社区会员 ChenyangGao(2339083510@qq.com) 专享 尊重版权

10.4.4 查找 std::list.......................................................................................................197 10.5 std::forward_list .............................................................................................................. 198 10.5.1 std::forward_list 中的插入和删除...................................................................199 10.5.2 遍历 std::forward_list .......................................................................................199 10.5.3 对 std::forward_list 排序 .................................................................................. 199 10.5.4 查找 std::forward_list .......................................................................................199 10.6 std::map 与 std::multimap ................................................................................................199 10.6.1 std::map 中的插入和删除.....................................................................................200 10.6.2 遍历 std::map.........................................................................................................202 10.6.3 对 std::map 排序....................................................................................................202 10.6.4 查找 std::map.........................................................................................................203 10.7 std::set 与 std::multiset ................................................................................................203 10.8 std::unordered_map 与 std::unordered_multimap..........................................................204 10.8.1 std::unordered_map 中的插入与删除 .................................................................206 10.8.2 遍历 std::unordered_map .....................................................................................207 10.8.3 查找 std::unordered_map .....................................................................................207 10.9 其他数据结构 ....................................................................................................................... 208 10.10 小结 ..................................................................................................................................... 209

第 11 章 优化 I/O...........................................................................................................................210

11.1 读取文件的秘诀 ................................................................................................................... 210 11.1.1 创建一个吝啬的函数签名 ..................................................................................... 211 11.1.2 缩短调用链 ............................................................................................................. 213 11.1.3 减少重新分配 ......................................................................................................... 213 11.1.4 更大的吞吐量——使用更大的输入缓冲区 ......................................................... 215 11.1.5 更大的吞吐量——一次读取一行 ......................................................................... 216 11.1.6 再次缩短函数调用链 ............................................................................................. 217 11.1.7 无用的技巧 ............................................................................................................. 218

11.2 写文件 ................................................................................................................................... 219 11.3 从 std::cin 读取和向 std::cout 中写入..........................................................................220 11.4 小结 ....................................................................................................................................... 220

第 12 章 优化并发 ......................................................................................................................... 221

12.1 复习并发 ............................................................................................................................... 222 12.1.1 并发概述 ................................................................................................................. 222 12.1.2 交叉执行 ................................................................................................................. 226 12.1.3 顺序一致性 ............................................................................................................. 226

xiv | 目录

12.1.4 竞争 ......................................................................................................................... 227 12.1.5 同步 ......................................................................................................................... 228 12.1.6 原子性 ..................................................................................................................... 228

12.2 复习 C++ 并发方式..............................................................................................................230 12.2.1 线程 ......................................................................................................................... 230 12.2.2 promise 和 future..................................................................................................231 12.2.3 异步任务 ................................................................................................................. 233 12.2.4 互斥量 ..................................................................................................................... 234 12.2.5 锁 ............................................................................................................................. 235 12.2.6 条件变量 ................................................................................................................. 236 12.2.7 共享变量上的原子操作 ......................................................................................... 238 12.2.8 展望未来的 C++ 并发特性....................................................................................240

12.3 优化多线程 C++ 程序..........................................................................................................241 12.3.1 用 std::async 替代 std::thread .........................................................................242 12.3.2 创建与核心数量一样多的可执行线程 ................................................................. 243 12.3.3 实现任务队列和线程池 ......................................................................................... 244 12.3.4 在单独的线程中执行 I/O.......................................................................................245 12.3.5 没有同步的程序 ..................................................................................................... 245 12.3.6 移除启动和停止代码 ............................................................................................. 247

12.4 让同步更加高效 ................................................................................................................... 248 12.4.1 减小临界区的范围 ................................................................................................. 248 12.4.2 限制并发线程的数量 ............................................................................................. 249 12.4.3 避免惊群 ................................................................................................................. 250 12.4.4 避免锁护送 ............................................................................................................. 250 12.4.5 减少竞争 ................................................................................................................. 250 12.4.6 不要在单核系统上繁忙等待 ................................................................................. 251 12.4.7 不要永远等待 ......................................................................................................... 252 12.4.8 自己设计互斥量可能会低效 ................................................................................. 252 12.4.9 限制生产者输出队列的长度 ................................................................................. 252

12.5 并发库 ................................................................................................................................... 253 12.6 小结 ....................................................................................................................................... 254

第 13 章 优化内存管理 ................................................................................................................255

13.1 复习 C++ 内存管理器 API ..................................................................................................255 13.1.1 动态变量的生命周期 ............................................................................................. 256 13.1.2 内存管理函数分配和释放内存 ............................................................................. 256 13.1.3 new 表达式构造动态变量......................................................................................259

目录 | xv

13.1.4 delete 表达式处置动态变量 ................................................................................261

13.1.5 显式析构函数调用销毁动态变量 ......................................................................... 262 13.2 高性能内存管理器 ............................................................................................................... 263 13.3 提供类专用内存管理器 ....................................................................................................... 264

13.3.1 分配固定大小内存的内存管理器 ......................................................................... 265 13.3.2 内存块分配区 ......................................................................................................... 267 13.3.3 添加一个类专用 new() 运算符 .............................................................................269 13.3.4 分配固定大小内存块的内存管理器的性能 ......................................................... 270 13.3.5 分配固定大小内存块的内存管理器的变化形式 ................................................. 270 13.3.6 非线程安全的内存管理器是高效的 ..................................................................... 271

13.4 自定义标准库分配器 ........................................................................................................... 271 13.4.1 最小 C++11 分配器................................................................................................273 13.4.2 C++98 分配器的其他定义.....................................................................................274 13.4.3 一个分配固定大小内存块的分配器 ..................................................................... 278 13.4.4 字符串的分配固定大小内存块的分配器 ............................................................. 279

13.5 小结 ....................................................................................................................................... 281 作者介绍..............................................................................................................................................282

封面介绍..............................................................................................................................................282