fcamel's blog: Python 加速的方法

這一年來用 Python 開發滿爽的，用久後發覺 Python 真的是不夠快啊。雖說這就是 trade-off，拿 CPU 執行時間換工程師開發的時間，但關鍵時刻跑得不夠快，還是得投入時間研究如何加速。程式開發就是一連串的 trade-off，人生也是如此啊！…………………還是少嘴炮，切入正題吧。

用 Profiling 測全體執行時間

去除演算法、資料結構的問題外 (像是 O(N log(N)) vs. O(N^2) 的方法 )，千萬別自己亂猜效能瓶頸就一頭熱地改程式。隨便想想都能舉出一堆自以為聰明的反例。我印象最深的經驗是，有一次我在寫資料結構作業答案，題目是實作 hash table 來統計文章裡單字出現的次數，身為課程助教，程式當然不能跑得太慢啊。所以調了一下效能，結果發覺改了一些演算法 (如 hash table 的「chain」用 binary tree 而不用 linked-list )，卻沒快多少 (變慢是常有的事)，一用 profiler 量，卻發現 1/3 的時間花在把一行文字切成單字上。我原本用 Java 的 split 一次切完回傳一個 List，改用 StringTokenizer 後就省下整體 1/3 的時間。

Python 有內建 profiling 的工具，叫做 profile，可以透過命令列直接下參數使用：

1	python -m cProfile -s time MODULE.py ARGUMENTS

這樣會執行 MODULE 再將測量結果輸出到螢幕，時間依單一函式執行時間來排序。引用官網的例子，cProfile 的輸出格式如下：

     2706 function calls (2004 primitive calls) in 4.504 CPU seconds
 
Ordered by: standard name
 
ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    2    0.006    0.003    0.953    0.477 pobject.py:75(save_objects)
 43/3    0.533    0.012    0.749    0.250 pobject.py:99(evaluate)
 ...

前面的 tottime 是該函式自己執行的時間；後面的 cumtime 則是該函式整體 (包含它呼叫其它函式) 的執行時間。

附帶一提，以前試 Java profiling 工具時，執行速度會慢個數倍，但用 Python 的 cProfile 卻只變成一倍多慢而已，也可能我那時用的 Java 工具太糟，或參數沒設好吧。

用 timeit 來量單一 expression 的速度

timeit 也是內建模組，也可以用命令列執行：

1	python -m timeit EXPRESSION

下面是執行的例子：

$ python -m  timeit 'range(10)'
1000000 loops, best of 3: 0.3 usec per loop
 
$ python -m  timeit 'xrange(10)'
10000000 loops, best of 3: 0.166 usec per loop

我比較常寫程式來測 timeit，透過命令列執行 expression 相當受限，還是自己寫段程式包成函式後，再用 timeit 執行較方便。附上一個例子：

#!/usr/bin/env python
# Count numbers in a list.
# Demonstrate built-in functions' efficiency.
 
import timeit
import random
 
# prepare test data
numbers = range(2)
a = []
for n in numbers:
   a += [n] * 10000
random.shuffle(a)
 
def test():
   c = {}
   for x in a:
       c[x] = c.get(x, 0) + 1
 
def test2():
   c = {}
   for n in numbers:
       c[n] = 0
   for x in a:
       c[x] += 1
 
def test3():
   c = {}
   for n in numbers:
       c[n] = a.count(n)
 
 
if __name__=='__main__':
   t = timeit.Timer("test()", "from __main__ import test")
   print 'test', t.timeit(number=1000)
 
   t = timeit.Timer("test2()", "from __main__ import test2")
   print 'test2', t.timeit(number=1000)
 
   t = timeit.Timer("test3()", "from __main__ import test3")
   print 'test3', t.timeit(number=1000)

有興趣的人可以猜猜看那個方法最快 [1]。

找出瓶頸後加速的方法

用 profiling 找出瓶頸後，大概有幾種作法：

用 multiprocessing 平行化：這年頭 CPU 不用錢，隨便買都是 multi-core。若程式可以單純平行化，這個作法比用 C/C++ 方便一些，至少還是在寫 python code。但若程式稍微複雜，寫起來會很辛苦，且容易因 fork 或 lock 的 overhead 而沒快多少。
將 CPU bound 的地方透過 ctypes 改寫成 C/C++：雖說 ctypes 很好用，不過寫 C/C++ 得注意的事比寫 Python 多太多了，所以我滿少這麼幹的。
從 Python interpreter 下手，改用較快的寫法：這個作法需要一些 Python 運作的知識，才知道怎麼改會比較快。比方若不需用到整個 list 可以改用 generator 減少產生 list 的時間、使用 member field 存取資料以減少 function call、改用 built-in 函式組出要做的事 (如上面附的例子)。這時 timeit 就很好用了，可以先測好關鍵部份，減少重跑整個 profiling 的時間。

不勞而獲的加速方法

我只有偶而注意相關消息，還沒試過，只知道各家方法有些不適用的問題，這裡記些關鍵字。

Psyco 是老字號工具，大家都說讚，對數值運算特別有效，但它只支援 32-bit CPU，作者目前在開發 PyPy。另外 Google 開發的 unladen-swallow 也令人期待。也許在不久的將來，兩邊都會有足以實用的成果吧。

延伸閱讀

經 Victor 告知，Python 官方 Wiki 有幾篇超棒的文件，相當值得一看：

備註

這是我執行出來的數據：
1 2 3
test 5.41639614105 test2 2.70715403557 test3 0.619280815125
即使走訪 list 兩次，方法三還是比前兩個方法 (只走訪一次) 快上不少，這是因為方法三用 C 實作的程式走訪迴圈，而前兩個方法用到 Python 的迴圈。

fcamel's blog

2010年1月5日星期二

Python 加速的方法

用 Profiling 測全體執行時間

用 timeit 來量單一 expression 的速度

找出瓶頸後加速的方法

不勞而獲的加速方法

延伸閱讀

備註

沒有留言:

張貼留言

2010年1月5日 星期二

Python 加速的方法

用 Profiling 測全體執行時間

用 timeit 來量單一 expression 的速度

找出瓶頸後加速的方法

不勞而獲的加速方法

延伸閱讀

備註

沒有留言:

張貼留言

2010年1月5日星期二