Why Python is Slow: Looking Under the Hood

Why Python is Slow: Looking Under the Hood

原文連結:Why Python is Slow: Looking Under the Hood

翻譯如有錯誤或語句不順,歡迎來信告知,謝謝您!
提醒:原文以 Jupyter Notebook 來 demo,您可以考慮使用與原文相同的 Jupyter Notebook 或使用 Python IDLE 實驗。

我們以前都聽過一句話:Python is slow。

當我開始用 Python 來教 scientific computing 課程時,我在這門課得很前面就提及這個論點,同時告訴學生為什麼:總結來說是因為 Python 的動態型別、直譯式語言的特性、且資料在記憶體中不會被依序排列。而同時我也補充說明要如何以 NumPy、SciPy 來解決這些問題。

但當我最近發覺到:儘管上述的用詞夠精確,但是:「動態型別、直譯式語言、緩衝區」這些專業術語對於初入門的人意義不大,所以也不能理解在 Python 這層神秘面紗之下,到底藏了一些什麼。

所以我決定寫這一篇文章,深入到其中的原理與細節。我們會透過 Python 原生套件(ctype)一窺 CPython 之中的祕密。所以無論你是個初心者或是有經驗的開發者,我都希望這篇文章能夠讓你學到一些東西。

為什麼 Python 比較慢

Python 比 Fortran、C 還慢有以下幾個原因:

1. Python 是動態型別而非靜態型別

這邊指的是在程式執行期間,直譯器並不知道變數的型態是什麼。和 C 的變數之間的差異可以從以下這個圖看出來(對於編譯式語言我們都以 C 作為範例):

在 C 之中,編譯器都必須清楚地知道變數的型態。但是在 Python 當中,所有東西都被歸類為物件(object)。

所以說,如果你寫下這段程式:

編譯器在一開始就會知道 a, b 是一個整數(Integer),他也不可能會是其他東西,而再來也能去呼叫一個會相加兩整數的副程式,並回傳一個整數。用一個簡單的流程來表示這段程式碼會是:

  1. <int> 1 指定到 a
  2. <int> 2 指定到 b
  3. 呼叫 binary_add<int, int>(a, b)
  4. 把執行結果存到 c

在 Python 當中,與上述程式碼等價的 Code 如下:

可是這邊直譯器只會知道 12 是兩個物件,但是也不知道這兩個物件的型態是什麼。所以直譯器必須要去檢查每個變數的 PyObject_HEAD 並找到其中的型別,然後再呼叫對應型別的相加副程式。最後還需要創造並初始化值為相加結果的物件。所以流程會是:

  1. 1 指定到 a
    • 設定 a->PyObject_HEAD->typecode 是整數型態
    • 設定 a->val = 1
  2. 2 指定到 b
    • 設定 b->PyObject_HEAD->typecode 是整數型態
    • 設定 b->val = 2
  3. 呼叫 binary_add(a, b)
    • a->PyObject_HEAD 找到 typecode [註1]
    • a 是一個整數,他的值是 a->val
    • b->PyObject_HEAD 找到 typecode
    • b 是一個整數,他的值是 b->val
    • 呼叫 binary_add<int, int>(a->val, b->val)
    • 得到結果 result,而且這個結果是一個整數
  4. 建立物件 c
    • 設定 c->PyObject_HEAD->typecode 是整數型態
    • c->val 設定成剛剛得到的結果 result

動態型別也象徵著在任何操作都需要經過很多步驟,這也是在數值資料運算當中,Python 速度遠慢於 C 的原因。

2. Python 是直譯式語言而不是編譯式語言

我們剛剛也看過了一個關於直譯式與編譯式差異的範例了。一個聰明一點的編譯器能夠把不必要的操作省略掉、使重複的操作執行得更有效率,最後就能夠加速執行速度。至於編譯器優化則就是編譯器的強項,我個人也不夠資格來說此事,因此讓我們就此打住。至於關於這段的範例,你可以看看之前關於 Numba 與 Cython 的文章

3. Python 物件的結構導致記憶體存取沒效率

如果你有注意到,應該有看到在 Python Object 多包了一層型別資訊,而這個是 C 沒有的東西。所以現在想像一下你有很多個整數,且想要排程一列去做批次操作。在 Python 你應該會使用原生的 List,而在 C 當中你可能會使用 array。

而 NumPy array 則是一個類似 C array 的 Python 物件。也就是說,他有一個 pointer(指標)指向連續的資料區段。
但是在 Python list 則是有一個 pointer 指向連續的 pointer 區段,而 pointer 區段的每個值再指向實際存於記憶體當中的資料(在這個例子就是 integer)。以下是關於這段說明的圖片:

這裡就能夠很輕易看出,在你要依序操作這些資料時,NumPy 的結構會比 Python 原生結構還要有效率太多,無論是以儲存成本論或是以存取成本論皆是如此。

那為什麼我們還要用 Python?

這些先天的固有特性使得 Python 沒效率,但是為什麼我們還是要使用 Python?

因為動態型別讓 Python 比 C 更易用,而且這些特性也讓 Python 十分彈性寬鬆,這讓 Python 更能節省開發時間,若你真的需要像是 C 一般的效能,Pyhton 也可以去使用其他已編譯的函式庫(執行速度更快)。這也是為什麼越來越多科學相關社群都使用 Python 的原因,總而言之,Python 用於科學是非常有效率的語言。

Python 背後所作的事:眼見為憑

剛剛有提到 Python 的內部結構,但我們不能就此駐足不前。在我歸納出以上的結論前,我開始研究 Python 之中的祕密。

接下來的小節,我要用一些小技巧來證明以上所言屬實。以下所有程式碼都是使用 Python 3.4 來實作。再之前的版本的內部結構有些許不同,而之後版本的結構也可能完全改變,所以請確定你所使用的版本與我相同。再者,以下程式碼都假設在 64-bits CPU 上跑的,如果你是使用 32-bits 的平台,在以下的程式碼,有些 C 的型別需要再另行調整囉。

深入 Python Integers

在 Python 當中,你可以很容易的創造並使用一個整數:

但是這個簡單的界面之下,掩蓋著底下複雜的原理。在上方我們已經簡要地討論了 Python Integer 在記憶體中的佈置方式。在這裡我們使用 Python 的原生模組 – ctypes 來深究 Python 的整數型態。但在一開始我們需要知道 Python Integer 在底層 C API 的樣子:

實際上,變數 x 在 CPython 當中是被儲存在一個結構裡面,你可以從 CPython 原始碼的 Include/longintrepr.h 找到:

這裡個 PyObject_VAR_HEAD 是巨集(macro),而在 Include/object.h 被定義:

這時又看到了一個 PyObject,它在 Include/object.h 被定義:

而這邊的 _PyObject_HEAD_EXTRA 雖然是一個巨集,但一般來說卻不會被使用到。

所以說,把以上的結構與巨集全部放在一起看,我們的 Integer Object 應該會長得像以下定義的結構(structure):

這裡有個 ob_refcnt 變數是物件被參考(reference)的次數,ob_type 是一個指標,指向一個有著型別資料和物件函式定義的結構,而 ob_digit 則擁有著實際的數值資料(也就是 x 的值)。

有了這些預備知識,我們可以開始用 ctypes 模組來看看實際的物件結構並解析出上述所說的那些資訊(參考次數、型別資料、數值資料 … 等)。

事不宜遲,開始以 Python 來定義 C 的結構吧:

現在可以看看一些數值結構的內部數值資料是多少了,在此以 42 為例。使用 id function 可以得到物件在記憶體中的位置:

看來 ob_digit 是指向正確的記憶體位址沒有錯!
refcount 呢?我們只有建立一個整數阿?為什麼它被參考的次數不是 1 而是 35 呢?

結果是因為 Python 用了很多很多的小整數,如果每一次使用這些小整數都建立一次,那會消耗掉很多的記憶體資源。也因為這個原因,Python 把小整數實作成 singletons(單例,也就是只會有一個實例):在記憶體當中,這些數字只會存在一份。換句話說,每次你建立了位於此範圍的小整數,都只是建立了一個參考指向該數值而已。

變數 xy 都是指向同一個記憶體位址。但是在數字漸增到一個較大的數字時(在 Python 3.4 是 255 以上),這個例子就不會再回傳 True 了:

在 Python 直譯器被啟動的時候會創造一堆整數物件,你也可以從下圖來看出小整數被參考的次數:

從這個圖可以看出,0 這個數字被參考了幾千次,而說不定也如你所預期的:數值被參考的次數是逐漸降低的。
為了確保我們的猜想是正確的,讓我們來檢查一下 ob_digit 的值是否對應到正確的值:

如果你再深入一些觀察,你會發現這個現象只會在數值是 255 以內時成立;在大於 255 時,Python 的儲存數字於記憶體的方式又不同,詳情可以參考 Objects/longobject.c
但是我還是不敢說我瞭解到底原理是什麼,但我認為 Python 能夠有效率的處理會 Overflow 的數值一定有什麼技巧:

這個數字大到沒辦法放在 long 型態裡面,long 最大也只能放 64 bits 的數字(也就是說最大也只能到 $2^{64}$)

深入 Python Lists

再延續剛剛的概念至比較複雜一點的 Lists,和 Integer 類似,我們能在 Include/listobject.h 找到其定義:

所以我們可以像剛剛再把 structure 展開:

這裡的 PyObject 指向 List 的內容,而 ob_size 就是 List 裡面有多少個物件。

嘗試看看之後:

那讓我們來看看要怎麼取得 List 內的物件吧。
就如同我們所見,元素都是被存在PyObject 這個指標當中,它指向一個連續的 Array,所以在此使用 ctypes,我們就能夠建立一個將剛剛寫的 IntStruct 包裝起來的複合結構:

接下來看看裡面的每一個物件吧:

我們已經揭開 List 當中 PyObject 的祕密,你也可以花一些時間回去看看最初所說的在記憶體當中的排列方式,並且確定一下你真的了解 ctypes 操作和圖中的對應關係。

深入 NumPy arrays

現在為了比較,所以我們也需要來窺探 NumPy array 之中的架構,我會跳過關於 NumPy C-API 的陣列定義細節,如果你有興趣的話可以參考:numpy/core/include/numpy/ndarraytypes.h

在此我使用的 NumPy 版本是 1.8,我不確定版本不同會不會有差異:

首先先開始以 ctypes 來定義 NumPy array 的結構吧,我們同時也加上 shape、strides properties:

現在可以試試了:

可以看到我們有把正確的 shape information 拿到了。再來確定一下 reference count 正不正確吧:

現在我們可以用比較 tricky 的方法來拉出 array 中的資料。首先我們先無視掉資料在記憶體中的距離,假設它就是一個 C 的連續陣列:

變數 data 現在就相當於一塊連續的記憶體以 NumPy array 的方式被表示,我們來修改 x 陣列中的一個值看看:

… 然後你可以觀察到 data 裡面的值也變了。也就是說,xdata 指向同一塊連續記憶體區塊。

把 Python List 與 NumPy ndarray 的內部結構互相比較,可以很清楚的發現 NumPy 的好很多,相同型態的資料儲存方式好很多。而這個原因也就是為什麼 compiler 能讓程式更有效率。

Just for fun: a few “never use these” hacks

ctypes 來包裝 C-level 的資料能夠讓你做一些好玩的 hack。

把整數的值 “改掉”

受到這篇 Reddit 貼文的啟發,我們其實可以修改整數物件的數值資料!不過如果我們修改像是 01 這種常見的數字,Python kernel 很可能就這樣 crash 了。但是如果我們來修改比較沒那麼重要的數字就不會造成這麼嚴重的結果了。

不過還是需要提醒一下,這真的不是個好主意。尤其是如果你在 IPython Notebook 嘗試這個的話,你可能會弄壞 IPython kenel 導致不能正常執行(因為你在執行週期內改掉了這個變數)。不過我們還是來嘗試看看啦:

但是我們不能用正常簡單的方式把 113 的值設定回去,因為 113 這個值在 Python 中已經不復存在:

要恢復原樣的話,只能去直接修改 bytes 的值。我們知道 $113=7\times 16^1+1\times 16^0$,所以在 little-endian 64-bits 系統,以下方法可以恢復:

然後就成功恢復了!不過以防萬一再提醒一下,沒事請不要這麼做。

List 內容 In-place 修改法

在上面有提到關於怎麼 In-place 修改 NumPy array 的值。因為 NumPy Array 就只是一串連續的資料,所以很容易。但是我們是不是也能在 Python 做相同的事情呢?這就變得有一點 tricky 了,因為 Lists 是儲存 value 的 reference 而不是存 value 本身。且為了不要讓 Python crash 掉,你要小心 reference count 必須保持原樣,否則會像以下狀況:

所以就像我說的一樣,你永遠都不應該這樣子做,而且說實在的,我也想不到你這麼做的理由是什麼。不過這提供你一個關於怎麼修改 List 內容的想法。與 NumPy array 比較之後,你應該就能夠看出為什麼 Python List 會比 NumPy array 還要慢了。

Meta Goes Meta: a self-wrapping Python object

使用上述方法,我們也能讓一切開始變得越來越奇怪。在 ctypes 裡面的 Structure class 就是它自己,也就是說自己包住自己的這種結構。可以參閱 Modules/ctypes/ctypes.h

所以我們現在來做一個自己包住自己的結構。不過我們沒辦法直接做到這件事情,因為我們不知道新的結構的記憶體位址是什麼。不過我們可以建立兩個 Structure,讓第二個包住第一個,然後再修改其內容。我們先來做一個 meta-structure 然後把它包起來:

現在再加上第三個結構,然後把第三個結構的記憶體位址修改成第二個結構的記憶體位址:

現在我們就有了一個 self-wrapping 的結構了!

再一次強調,我真的想不到你會想這麼做的理由。不過self-reference 並不是開創之舉,因為動態型別的關係,他可以不透過修改記憶體的方式來做到這件事情。

Conclusion

Python 很慢,而最大的原因就出在記憶體存取不夠直接,雖然這能使 Python 開發快、簡單、好玩。而且我們也看到 Python 提供了 hacking Python object 的工具。

我希望在深入研究多種不同的物件之後,你能夠對它更瞭解。還有 CPython 物件內部簡介也是,以上的這些實驗讓我豁然開朗,希望對你也是如此,Happy Hacking!

Leave a Reply

Your email address will not be published. Required fields are marked *