Back to home

我是如何一步一步压榨出python程序的性能的

初次发表于2016/12/26

前段时间为了解决web扫描过程中对重写过的URL不能识别参数和去重的问题,设计了一套算法。在申请专利之前POC自然少不了,基本思路验证OK,也顺便去鲁班奖打了个酱油,侥幸还有人识货。算法其实比较小众,懂行的人自然知道它的价值,然而这儿要说的性能优化却跟很多同学都有共同话题了。
POC是用python语言实现的,在产品化之前,除了要保证有效性、稳定性之外,还要满足web扫描引擎的性能要求。在没做性能优化之前,处理1kURL耗时100s,而处理15kURL却差不多耗时1个多小时,这种非线性的性能下降是万不能接受的。网络有云,大多数人的努力程度之低,根本轮不到拼天赋,所以第一时间并没有嫌弃pythonC语言慢,去换个语言或者解释器执行,而是静下心来,尝试一步一步压榨下我的python程序的性能。
1. 确立基线
首先,得知道程序到底慢在哪儿,哪儿才是最耗性能的地方。python 内置了丰富的性能分析工具,如timeit profilecProfile hotshot 等。为了更精确地知道哪行代码是性能瓶颈,我使用了line_profilerkernprof(详见https://github.com/rkern/line_profiler)。
在代码中为需要分析的函数加上装饰器@profile,通过python -m kernprof -l -v xxx.py运行你的程序,运行结束后,即可在控制台看到逐行的分析结果,形如:


2. 各个击破

下来需要做的就是重点分析进入次数最多和耗时最长的代码或者函数调用进一步分析(一个@profile足矣),不断进行优化和比较,直到跑出您满意的性能。过程中有这么一些点可以作为checklist,以优先级为序:
a. 程序本身的时间复杂度
你的程序的时间复杂度是O(1) -> O(lg n) -> O(n lg n) -> O(n^2) -> O(n^3) -> O(n^k) -> O(k^n) -> O(n!)中的哪一种?尽量想办法把时间复杂度往左移动。一个良好的算法能够对性能起到关键作用,因此性能改进的首要点是对算法的改进,后面所说的点基本都是用后天勤奋来弥补先天的不足。
b. 使用合适的数据结构
Listsetdict该选谁,这个应该是基本要清楚的,那这些数据结构的增删改查怎么才是高效的也是必须要明白的,也有教科书般的规范来说,此处不再赘述。如果常规的数据结构频繁使用,比较耗性能了,那另一些集合类在性能优化中你也是应该要知道的:
· namedtuple主要用来产生可以使用名称来访问元素的数据对象
· Deque:双向链表实现的队列,如果你在使用list.insert,赶紧看看deque
· Counter:强大的计数器
· Defaultdict:让你进行字典操作的时候,不用担心KeyError,少做逻辑判断,自然有益性能提升
· OrderedDictKey会按照插入的顺序排列,而不是Key本身排序
它们位于Python内建的一个集合模块collections中。Python官方文档把它们统称为“High-performance container datatypes”,光这名字,您不妨感受一下(详见https://docs.python.org/2/library/collections.html)。
c. 优化循环
费劲心思让每一行代码执行的快一些之前,别忘了先让代码执行的次数尽可能少。有多重循环的尽量将内层的计算提到上一层这是教科书般的建议,静态化和cache也许也应该更新到你的笔记本中。
静态化是指可以将大部分时间不用重复计算的变量等作为类的静态成员直接使用。
Cache是将大量重复调用的函数根据函数名和参数把返回值缓存下来。python3.2开始引入的functools.lru_cache就是这样一个非常优雅的缓存机器。当您用的是python2无法享受这样的高级功能时,可以借鉴别人移植到python2上的版本backports.functools_lru_cache(详见https://pypi.python.org/pypi/backports.functools_lru_cache/1.0.1),还可以参考在LRU基础上引入了expires特性的pylocache(详见https://pypi.python.org/pypi/PyLocache/0.0.1
d. 充分利用 Lazy if-evaluation 的特性
python 中条件表达式是 lazy evaluation 的,也就是说如果存在条件表达式 if x and y,在 x false 的情况下 y 表达式的值将不再计算。If条件该咋写,直白点就是把简单逻辑写在前面,牵扯到复杂计算和耗时的逻辑写在后面,对orand都是如此。
e. 正则虽好,可不要滥用
我们的算法中有大量的字符串比较,正则匹配、替换等操作,除了熟悉正则贪婪和非贪婪的写法之外,还要谨记:能用字符串查找解决的,就别用正则匹配;正则的预编译放在循环外,甚至把预编译结果缓存下来,也许性能上能给你意想不到的惊喜。
f. 字符串拼接有学问
朴素的添加+%s格式化、字符串列表join、还有其它MutableString和字符数组等比较小众的方法,到底什么才是拼接字符串的正确姿势?如果你已经意识到并习惯用第三种字符串列表join的方式,建议当您需要添加非常多的字符串时,不妨考虑下cStringIO
g. 选更快更新的库
告诉自己,python内建的函数和库总是比你自己实现的要快;C版本的函数总是由于非C版本的性能,如用cPickle而不是pickle
3. 优化无止境
做完上面的优化,还可以尝试:
· 使用C扩展,例如python2+ctypes据说有很不错的性能提升
· 使用命令行优化选项-O
· 使用高性能的第三方库和工具,如GPULibGPUs加速,Cythonpython转换成Cpypy
但是,有两点需要引起你的注意:
a. Pythonic的写法往往有更好的性能,但是可能会使代码可读性和维护性差一些。尤其是当这个不是性能的主要瓶颈时,建议可读性的优先级高于这么一点点的性能优化。
b. 长尾效应无处不在,当你用20%的精力完成了80%的优化之后,下来要做的,也许并不是80%的精力去完成剩下的20%的优化,而是将你的经验常态化,并分享给更多的人。比如本文所做的。
总结下,python程序性能优化的一般思路:
1. 用合适的工具,找准基线
2. 抓住主要矛盾,各个击破
3. 优化无止境,做好取舍
不断地让数据说话,经过持续的折腾,算法处理1kURL耗时从100s降到了十几秒,15KURL耗时从1小时多降到了6分钟左右,基本把算法的时间复杂度控制在了O(n)线性的规模上。