Introduction To Performance Optimization
写在最前
本文针对 C++ 和 linux 环境，但是思想和方法，却对其他语言和环境同样适用。很可供参考的。
优化前
1，确定优化是必须要做的。
如果程序已经跑的足够快了，内存使用也足够省了，那么完全没有优化的必要。什么是足够呢？能够满足当前的业务和需求。因此，如果不是绝对必要，不要优化。
这是因为虽然优化不是万恶之源，但是优化可能会带来问题。它会让你把头发掉光，绞尽脑汁；它可能让之前只需要一两行逻辑很清晰的代码，变成很难理解的高度优化的实现。优化很多时候某种程度上让代码可读性和可维护性变差。
2，确定该做的优化都做了
有两个方法可以免费地、快速地提高效率：
第一个是使用 release 模式。如果你的程序在 debug 模式下表现不佳，那么可以尝试使用 release 模式进行编译链接。一般说来，这也是发布程序的默认模式。
第二是开启编译器优化。例如 g++ 就提供了多个级别的优化选项，一般使用 O2 。
3，确定做了优化前的准备工作
最重要的一点是对程序的性能进行详细分析，找出瓶颈段 （hot spot ）。这很重要，否则，可能导致在错误的方向上越走越远。例如一个程序由函数 f 和 g 构成， f 花费了 2s ， g 花费了 100ms ，那你把 g 从 100ms 优化为 50ms ，对系统又有什么帮助呢？ f 才是大头啊。
因此，这里就会有三个问题：
第一，如何定位程序瓶颈段？
要是有一个工具，能够告诉我系统模块的开销比例，那就太好了。有这样的工具吗？有的。 Linux 下的 perf 就是。 这里 是对 perf 非常好的 tutorial ，强烈建议初学者阅读。简单说来，一条命令即可：
sudo perf record -g ./yourprograme 第二，我想给我的程序的某个函数计时，应该怎么做？
有很多方法，强烈建议您阅读我的这篇博客，很可供参考。我个人比较喜欢用 timespec ，原因是：知道它的人不多；它可以精确到纳秒；它不受系统时钟的影响（ gettimeofday 显然会，因为它就是读取系统时钟嘛）。
第三，优化后，函数变快了，系统变快了多少？
哦，回忆一下我们本科计算机体系结构里的 Amdahl 定律。如果您没学过这个定律，或者早已还给老师，那么 这里 的内容可能对你有帮助。
优化中
一旦确定要优化，并且定位了瓶颈段，那么就是想尽一切办法进行加速了。个人总结的一些比较有效的思路和方法：
0，cache friendly access pattern
尽可能利用 cache ，编写 cache friendly 代码。例子，比如说非常著名的二维数组按行按列访问问题。
1，算法和数据结构层面
使用合适的、高效的数据结构和算法，往往能带来很大的提升。不过，前提是，你需要对你的需求进行认真分析。 find、search、insert、successor、del、min、max 这些操作，哪些是你期望需要非常高效的？哪些操作是你业务里经常出现的？
你需要对以下数据结构和算法有所了解：
哈希表： O(1) 的查找时间，因此这点常常成为除了数组之外的首选，当查找非常关键时。只知道 Separate Chaining 和 Open Addressing ？那您 out 了。建议您阅读我的这篇讲解 cuckoo hashing 的博客。
跳表：说到 O(lgn) 的 insert、find、del ，很多人想到二叉搜索树，由于非平衡的二叉搜索树有退化为 O(n) 的风险，因此很多场景需要平衡树。 B 树？红黑树？太 heavy 了。有时候，您需要跳表，真的，很需要。它足够简单，而且很多时候就能满足您的需求。除此之外， Treap 也是一种随机的数据结构，我实现的大规模分布式数据库 Yedis 里就有提供相应的实现，以后会放出。
Sunday算法：字符串匹配里， KMP 算法是大名鼎鼎了。谁让 Knuth 是大佬呢？可是，您是否知道 Sunday 算法？ Sunday 算法什么时候会比 KMP 高效而且高效地多？
string.h里提供的算法：包括 memcmp、memcpy、memmem （我第一次知道 memmem 是从我的主管杨志丰先生那儿）等。当你想手工实现这些函数，正在写一大堆 while 循环时，请优先选择这些库函数。
排序算法：快速排序，非常常见、常用。那么，如何编写一个高效的快速排序？建议您阅读我的这篇博客。
2，将小但是频繁调用的函数内联。注意， gcc 有提供强制内联的 feature ，也就是 __attribute__((always_inline))
3，为分支预测适当加上 likely 或者 unlikely 。请注意， if 语句并不可怕，可怕的是分支预测失败。这正和锁并不可怕，因为加锁和释放锁其实很快，可怕的是锁冲突。所以，您需要了解这两组宏：
#define likely(x) __builtin_expect(!!(x), 1) #define unlikely(x) __builtin_expect(!!(x), 0) 4，消除 if 语句。比如说如下代码：
if (a > 0 ) b += 2; else b+= 1; 那么可以消除为 b += 1 + (a > 0);
5，查表法。将反复使用的、不大的、静态的数据事先计算好，存在表格里，需要的时候，直接去查，避免计算。
6，避免重复计算。很多计算只需要执行一次，比如说非常著名的
for (int i = 0; i < strlen(a); i++) do sth; 其中 strlen(a) 可以事先计算好，用一个变量存放即可。
还有很多很多。就看您的知识面和经验了。
优化后
优化后，请记得再次对您的程序进行 profiling ，确保优化是有效的。
别偏听偏信，别坚信 KMP 一定比暴力算法快，别盲信教科书、博客、资料里的说法，别跪舔大佬！请实际测试！测试！！再测试！！！
一切以您的环境、以您的系统、以您的测试为准。没有权威。
参考资料
专门针对 C++ 和 Linux 的优化的书，不多。但是有一些零碎的、七七八八的资料，编程珠玑啊，深入理解计算机系统啊，还有过几个月会出的 optimized c++ 啊等等。
正文到此结束
热门推荐
相关文章
近期评论
-
你这基本没有更新呀，最近文章显示还是2019年的文章。不符合要求哈
-
关键词：慕云博客 链接：https://www.lilun.me 描述：分享原创文字的个人博客
-
-
-
可以提供一下源码吗
-
不是商业站，鸡娃学习笔记
-
-
-
-
听他们说很厉害的样子
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
