神刀安全网

Introduction To Performance Optimization

写在最前

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

优化前

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

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

这是因为虽然优化不是万恶之源,但是优化可能会带来问题。它会让你把头发掉光,绞尽脑汁;它可能让之前只需要一两行逻辑很清晰的代码,变成很难理解的高度优化的实现。优化很多时候某种程度上让代码可读性和可维护性变差。

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

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

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

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

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

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

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Introduction To Performance Optimization

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址