探索CPython源碼：任意精度整數的實現

Python部落(python.freelycode.com)組織翻譯，禁止轉載，歡迎轉發。

你是否曾經注意到Python支持任意大小的整數？本文將對其機制進行回顧。

Python使用C語言的結構體來表現所有的類型。以下的數據結構負責所有的整數對象：

將宏展開後，簡化版的結構體如下所示：

ob_refcnt欄位負責垃圾回收機制中的引用計數，而ob_type則是指向描述整數類型的結構體的一個指針。

通常，在C和C++這一類語言中，整數的精度被限制在64位，但Python內置了對任意精度整數的支持。在Python3中，已經不會有簡單整數類型，所有的整數都用大整數類來表示。

如何存儲任意大小的整數？

一種方案是把整數表示為數字的鏈表。為了提高效率，我們需要把十進位的數字轉換為2³⁰進位數值系統，這樣每個元素代表0到2³⁰-1範圍內的一個值。根據不同的平台， Python使用包含30位數值的32位無符號整數鏈表或者15位數值的16位無符號整數鏈表。使用這種方法也帶了了額外的需求，我們無法使用整數的所有位。上例結構體中ob_digit的值負責這些鏈表。

為了減少不必要的開銷，CPyhton在處理-2³⁰到2³⁰範圍內的整數有一個「捷徑」。這些數字以只有一個元素的列表的形式存儲，只要這個數字能被表示為32位定長的數字。

值得注意的是，不像經典的方法，一個整數的標誌被單獨存儲在ob_size的值中。這個值存儲了ob_digit鏈表的大小。所以如果你想要修改長度為2的鏈表標誌，需要將ob_digit設置為-2。

源代碼的注釋如下：

123456789101112131415將會表示成如下形式：

將現在的表示轉換回去的演算法為:

常用整數的優化

範圍在-5到256之間的小整數對象通常在初始化時就已經進行了預分配。由於Python的整數對象是不可修改的，我們可以將其用作單體。每當需要 創建一個小整數對象時，Python只需要將指針移動到預分配的對象上。這樣就為常用整數的調用節省了時間和空間上的開銷。

有趣的是，PyLongObject結構體分配的整數都佔用了28位元組，這樣一來比64位C整數多佔用了三倍的內存。

數字系統轉換

接下來我們看看Python中如何將數字轉換為鏈表。

例如，我們需要將一個無符號64位長整型轉換成Python整數的表述。需要注意的是，這是標準C類型最可能直接轉換成我們的PyLongObject對象了。更大的數字可以由字元或者位元組鏈錶轉換而來。

以下是由C語言轉換為Python的簡單演算法：

為了驗證結論，我們可以看一下全局表現：

計算

基礎的計算操作的實現和學校中學的數學非常相似，僅有一點不同-鏈表中的每個元素都被看做一個單獨的「數字」。

每個運算操作都會產生一個最小對象。例如，當你想執行c += 10 時，大概會有以下步驟：

• 獲取一個預分配的整數對象10的地址（正如上文所說，由於10是一個小整數，我們不需要再創建一個整數對象）。

• 創建一個新的整數對象用來存儲運算結果。

• 將c和10相加，把結果存儲在新創建的對象。

• 將變數c替換為對新創建對象的引用。

• 將舊的c的引用計數減去1，這樣垃圾回收器可以將其回收。

例如，讓我們看一下使用carring的加法：

深入思考

還有很多細節在一篇文章里無法交代清楚。你可以在CPython(1,2,3)源代碼中了解更多關於整數的知識。

我有繼續這個系列的計劃，在未來幾篇博客中我將會描述類和函數對象的內部。

英文原文：http://rushter.com/blog/python-integer-implementation/
譯者：mrwoody

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！