早上我偶然看見一篇介紹兩個Python腳本的博文，其中一個效率更高。這篇博文已經(jīng)被刪除，所以我沒辦法給出文章鏈接，但腳本基本可以歸結(jié)如下：
fast.py
 

import time
a = [i for i in range(1000000)]
sum = 0
t1 = time.time()
for i in a:
  sum = sum + i
t2 = time.time()
print t2-t1

slow.py
 

import time
from random import shuffle
a = [i for i in range(1000000)]
shuffle(a)
sum = 0
t1 = time.time()
for i in a:
  sum = sum + i
t2 = time.time()
print t2-t1

如你所見，兩個腳本有完全相同的行為。都產(chǎn)生一個包含前一百萬個整數(shù)的列表，并打印對這些整數(shù)求和的時間。唯一的不同是 slow.py 先將整數(shù)隨機(jī)排序。盡管這看起來有些奇怪，似乎隨機(jī)化足夠?qū)⒊绦蛎黠@變慢。在我機(jī)器上，運行的Python2.7.3， fast.py 始終比 slow.py 快十分之一秒（fast.py 執(zhí)行大約耗時四分之三秒，這是不平常的增速）。你不妨也試試看。（我沒有在Python3上測試，但結(jié)果應(yīng)該不會差太多。）

那為什么列表元素隨機(jī)化會導(dǎo)致這么明顯的減速呢？博文的原作者把這記作“分支預(yù)測（branch prediction）”。如果你對這個術(shù)語不熟悉，可以在 StackOverflow 的提問中看看，這里很好地解釋了這個概念。（我的疑慮是原文的原作者遇到了這個問題或者與此類似的問題，并把這個想法應(yīng)用到不太適合應(yīng)用的Python片段中。）

當(dāng)然，我懷疑分支預(yù)測（branch prediction）是否是真正導(dǎo)致問題的原因。在這份Python代碼中沒有頂層條件分支，而且合乎情理的是兩個腳本在循環(huán)體內(nèi)有嚴(yán)格一致的分支。程序中沒有哪一部分是以這些整數(shù)為條件的，并且每個列表的元素都是不依賴于數(shù)據(jù)本身的。當(dāng)然，我還是不確定python是否算得上足夠“底層”，以至于CPU級別的分支預(yù)測能夠成為python腳本性能分析中的一個因素。Python畢竟是一門高級語言。

因此，如果不是分支預(yù)測的原因，那為什么 slow.py 會這么慢？通過一點研究，經(jīng)過一些“失敗的開端”之后，我覺得自己找到了問題。這個答案需要對Python內(nèi)部虛擬機(jī)有點熟悉。

失敗的開端：列表vs.生成器（lists and generators）

我的第一想法是Python對排序的列表[i for i in range(1000000)] 的處理效率要比隨機(jī)列表高。換句話說，這個列表可以用下面的生成器替代：

def numbers():
  i = 0
  while i < 1000000:
    yield i
    i += 1

我想這可能在時間效率上更高效些。畢竟，如果Python在內(nèi)部使用生成器替代真正的列表可以避免在內(nèi)存中一次保存所有整數(shù)的麻煩，這可以節(jié)省很多開銷。slow.py 中的隨機(jī)列表不能輕易的被一個簡單生成器捕獲，所有VM（虛擬機(jī)）無法進(jìn)行這樣的優(yōu)化。

然而，這不是一個有用的發(fā)現(xiàn)。如果在slow.py的 shuffle() 和循環(huán)之間插入 a.sort()，程序會像 fast.py一樣快。很明顯，數(shù)字排序后的一些細(xì)節(jié)讓程序更快。

失敗的開端：列表對比數(shù)組

我的第二個想法是有可能數(shù)據(jù)結(jié)構(gòu)造成的緩存問題。a 是一個列表，這自然讓我相信a實際上是通過鏈表來實現(xiàn)的。如果shuffle操作故意隨機(jī)化這個鏈表的節(jié)點，那么 fast.py 可能可以把列表的所有鏈表元素分配在相鄰地址，從而采用高級局部緩存，而slow.py會出現(xiàn)很多緩存未命中的情況，因為每個節(jié)點引用不在同一個緩存行上的另外一個節(jié)點。

不幸的是，這也不對。Python的列表對象不是鏈接的列表，而是真正意義上的數(shù)組。尤其是用C結(jié)構(gòu)體定義了Python列表對象：
 

typedef struct {
 PyObject_VAR_HEAD
 PyObject **ob_item;
 Py_ssize_t allocated;
} PyListObject;

……換句話說，ob_item 是一個指向PyObjects指針數(shù)組的指針，并且分配的大小是我們分配給數(shù)組的大小。因此，這對于解決這個問題也沒幫助（盡管這對我不確定Python中關(guān)于列表操作的算法復(fù)雜度有些安慰：列表的添加操作算法復(fù)雜度是O(1)，訪問任意列表元素的算法復(fù)雜度是O(1)，等等）。我只是想說明為什么Guido選擇稱它們?yōu)榱斜怼發(fā)ists”而不是數(shù)組“arrays”，而實際上它們卻是數(shù)組。

解決辦法：整體對象

數(shù)組元素在內(nèi)存中是相鄰的，因此這樣的數(shù)據(jù)結(jié)構(gòu)不會帶來緩存問題。事實證明緩存位置是 slow.py 變慢的原因，但這來自于一個意料之外的地方。在Python中，整數(shù)是分配在堆中的對象而不是一個簡單的值。尤其是在虛擬機(jī)中，整數(shù)對象看起來像下面這樣：
 

typedef struct {
 PyObject_HEAD
 long ob_ival;
} PyIntObject;

上面結(jié)構(gòu)體中唯一“有趣”的元素是ob_ival（類似于C語言中的整數(shù)）。如果你覺得使用一個完整的堆對象來實現(xiàn)整數(shù)很浪費，你也許是對的。很多語言就為了避免這樣而做優(yōu)化。例如 Matz的 Ruby 解釋器通常以指針的方式存儲對象，但是對頻繁使用的指針做例外處理。簡單來說，Ruby解釋器把定長數(shù)作為對象應(yīng)用塞到同樣的空間，并用最低有效位來標(biāo)記這是一個整數(shù)而不是一個指針（在所有現(xiàn)代系統(tǒng)中，malloc總是返回以2的倍數(shù)對齊的內(nèi)存地址）。在那時，你只需要通過合適的位移來獲取整數(shù)的值——不需要堆位置或者重定向。如果CPython做類似的優(yōu)化，slow.py 和 fast.py 會有同樣的速度（而且他們可能都會更快）。

那么CPython是怎樣處理整數(shù)的呢？解釋器的什么行為給我們?nèi)绱硕嗟囊苫?？Python解釋器每次將整數(shù)分配到40Byte的“塊”中（block）。當(dāng)Python需要生成新的整型對象時，就在當(dāng)前的整數(shù)“塊”中開辟下一個可用空間，并將整數(shù)存儲在其中。我們的代碼在數(shù)組中分配一百萬個整數(shù)，大部分相鄰的整數(shù)會被放到相鄰的內(nèi)存中。因此，在有序的一百萬個數(shù)中遍歷展現(xiàn)出不錯的緩存定位，而在隨機(jī)排序的前一百萬個數(shù)中定位出現(xiàn)頻繁的緩存未命中。

因此，“為什么對數(shù)組排序使得代碼更快”的答案就是它根本沒有這個作用。沒有打亂順序的數(shù)組遍歷的速度更快，因為我們訪問整型對象的順序和分配的順序一致（他們必須被分配）。

最新評論