写在最前

本文针对C++和linux环境，但是思想和方法，却对其他语言和环境同样适用。很可供参考的。

优化前

1，确定优化是必须要做的。

如果程序已经跑的足够快了，内存使用也足够省了，那么完全没有优化的必要。什么是足够呢？能够满足当前的业务和需求。因此，如果不是绝对必要，不要优化。

这是因为虽然优化不是万恶之源，但是优化可能会带来问题。为了提升一点点性能就得绞尽脑汁、辗转反侧；它可能让之前只需要一两行逻辑很清晰的代码，变成很难理解的高度优化的实现。优化很多时候某种程度上让代码可读性和可维护性变差。

2，确定该做的优化都做了

有两个方法可以免费地、快速地提高效率：

第一个是使用release模式。如果您的程序在debug模式下表现不佳，那么可以尝试使用release模式进行编译链接。一般说来，这也是发布程序的默认模式。

第二是开启编译器优化。例如g++就提供了多个级别的优化选项，一般使用O2。

3，确定做了优化前的准备工作

最重要的一点是对程序的性能进行详细分析，找出瓶颈段（hot spot）。这很重要，否则，可能导致在错误的方向上越走越远。例如一个程序由函数f和g构成，f花费了2s，g花费了100ns，那您把g从100ns优化为20ns，对系统又有什么帮助呢？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也是一种随机的数据结构，我实现的大规模分布式数据库Soupen里就有提供相应的实现，您可以参考我的这篇博客。

Sunday算法：字符串匹配里，KMP算法是大名鼎鼎了。谁让Knuth是大佬呢？可是，您是否知道Sunday算法？Sunday算法什么时候会比KMP高效而且高效地多？

string.h里提供的算法：包括memcmp、memcpy、memmem、memmove等。当您想手工实现这些函数，正在写一大堆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，查表法。将反复使用的、不大的、静态的数据事先计算好，存在表格里，需要的时候，直接去查，避免计算。

还有很多很多。就看您的知识面和经验了。

有一个错误的想法，很值得在这里说。很多资料上写着：用移位代替乘除法。因此很多人的代码里充斥着大量的>>1 以及 <<1，美其名曰性能优化。

事实上，现在的编译器很聪明了，一点都不傻，不信您可以直接写a / 2 然后看看开启-O2选项后的汇编代码。结果会让您赞叹的。上面的左移一位、右移一位没有任何必要。

正常情况下，请按照逻辑需要直接写代码。现代编译器真的已经很牛逼了。因此，您应该重点关注算法、Cache、分支预测等层面。

优化后

优化后，请记得再次对您的程序进行profiling，确保优化是有效的。

别偏听偏信，别坚信KMP一定比暴力算法快，别盲信教科书、博客、资料里的说法，别跪舔大佬！请实际测试！测试！！再测试！！！

一切以您的环境、以您的系统、以您的测试为准。没有权威。

参考资料

专门针对C++和Linux的优化的书，不多。但是有一些零碎的、七七八八的资料，编程珠玑啊，深入理解计算机系统啊，还有最近刚刚出版的optimized c++啊等等。

有好心的网友在Github上维护了一个项目，分享了不少C++性能优化相关的资料。