Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

Introduction To Performance Optimization

写在最前

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

优化前

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

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

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

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

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

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

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

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

最重要的一点是对程序的性能进行详细分析,找出瓶颈段(hot spot)。这很重要,否则,可能导致在错误的方向上越走越远。例如一个程序由函数fg构成,f花费了2sg花费了100ns,那您把g100ns优化为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 ChainingOpen 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++性能优化相关的资料。