本文同步刊載於 「為你自己學 Python - 整數的前世今生」

整數的前世今生

在 Python 的世界裡，整數是最基本也最常用的資料型態之一。你有想過在 Python 裡建立一個數字例如 n = 9527 的時候，背後究竟發生了什麼事情嗎？有些程式語言的數字會因為作業系統的不同而有最大值的限制，可能是 2 的 32 次方或 64 次方，如果超過上限會出現「溢位（Overflow）」的情況，但為什麼 Python 可以處理任意大小的整數？還有在流程控制章節介紹到 is 關鍵字的時候，為什麼在 -5 到 256 之間的整數有一些特別的性質？這個章節就來看看這些到底是怎麼回事。

數字是怎麼產生的？

我先寫一行簡單的 Python 程式：

n = 9527

如果用 dis 模組來檢視它的 Bytecode 的話：

  1           2 LOAD_CONST               0 (9527)
              4 STORE_NAME               0 (n)

看起來滿簡單的，就是 LOAD_CONST 指令把 9527 這個常數載入到堆疊中，然後再透過 STORE_NAME 指令把它存到變數 n。那麼，9527 這個值是怎麼建立的？而且如果執行 Bytecode 的時候就已經是「載入」這個常數的話，那它又是在什麼時間點就被建立的？

Bytecode 有分編譯跟執行兩個階段，在編譯階段，在 Python 裡負責產生整數的函數是 PyLong_FromLong()：

// 檔案：Objects/longobject.c

PyObject *
PyLong_FromLong(long ival)
{
    PyLongObject *v;
    unsigned long abs_ival, t;
    int ndigits;

    // ... 略 ...

    return (PyObject *)v;
}

這個函數會把一個整數轉換成 PyLongObject 物件，函數裡面的細節待會再來看。接下來，這個物件會被放到程式碼物件（Code Object）的常數表 co_consts 中：

// 檔案：Python/compile.c

static Py_ssize_t
compiler_add_const(PyObject *const_cache, struct compiler_unit *u, PyObject *o)
{
    assert(PyDict_CheckExact(const_cache));
    PyObject *key = merge_consts_recursive(const_cache, o);
    if (key == NULL) {
        return ERROR;
    }

    Py_ssize_t arg = dict_add_o(u->u_metadata.u_consts, key);
    Py_DECREF(key);
    return arg;
}

這裡的 u->u_metadata.u_consts 指的就是 co_consts，這個 co_consts 是一個 Tuple，裡面會擺放所有這個物件會用到的常數，到這裡是 Bytecode 的編譯階段。

接下來進到 Bytecode 的執行階段，編譯好的 Bytecode 是擺在虛擬機器（VM）上執行的。來看看 Bytecode 裡的 LOAD_CONST 指令在做什麼事：

// 檔案：Python/bytecodes.c

inst(LOAD_CONST, (-- value)) {
    value = GETITEM(frame->f_code->co_consts, oparg);
    Py_INCREF(value);
}

看到了嗎？VM 會從編譯時期建立的常數表 co_consts 拿之前建立好的 PyLongObject 來用，而不是重新呼叫 PyLong_FromLong() 再建立一個新的數字物件，這樣效率才會好。

整數物件

剛才說到，在 Bytecode 編譯階段 PyLong_FromLong() 函數會把數字包成 PyLongObject 物件並存到 co_consts 裡，那麼這個 PyLongObject 長什麼樣子：

// 檔案：Include/cpython/longintrepr.h

struct _longobject {
    PyObject_HEAD
    _PyLongValue long_value;
};

結構還算簡單，只有一個成員變數 long_value，這是一個 _PyLongValue 結構：

// 檔案：Include/cpython/longintrepr.h

typedef struct _PyLongValue {
    uintptr_t lv_tag; /* Number of digits, sign and flags */
    digit ob_digit[1];
} _PyLongValue;

這個 lv_tag 後面寫的註解 Number of digits, sign and flags，它用來存放整數的一些 meta data，例如整數的位數、正負號以及一些其它的資訊。而 ob_digit 這個陣列則是用來存放整數的實際數值，這個陣列的大小是 1，但實際上可能會有多個 digit 來存放整數的值。

在 64 位元的作業系統上，lv_tag 的結構大概像這樣：

 63                                         2   1   0
+-------------------------------------------+---+---+
|                   DATA                    | T | S |
+-------------------------------------------+---+---+

這裡我用 S、T、DATA 幾個名稱來表示這些位元的意義，S 用來表示正負號，T 是一個標記，表示是不是「小整數」，而佔最大塊的 DATA 是整數的位數。以 9527 這個數字來舉例：

首先，S 位元是用來記錄正負號，正數是 0，負數是 1，所以 9527 的 S 位元是 0。

在 CPython 裡有個叫做「小整數」的東西，細節晚點介紹，它是從 -5 到 256 之間的整數，如果是在這個小整數的範圍內，這個 T 位元就是 0，只要不在這個範圍的整數就會設定成 1。雖然 9527 這個數字也沒多大，但因為不在這個範圍內，所以 lv_tag 的 T 位元是 1。

接下來 DATA 部份就比較複雜一點了。在 Python 裡有個東西叫 digit，在 64 位的作業系統上，每個 digit 可以擺放 30 個位元（有興趣可查原始碼裡 PYLONG_BITS_IN_DIGIT 的定義）。而 9527 這個數字的二進位表示是 10010100110111，總共只有 14 個位數，所以只要 1 個 digit 就能裝的下。在上面示意圖裡 DATA 部分存儲的是這個整數需要多少個 digits 來表示。因為 9527 只需要 1 個 digit，所以 data 部分存儲的值就是 1。

因此，9527 這個數字的 lv_tag 就會是：

 63                                         2   1   0
+-------------------------------------------+---+---+
|0000000000000000000000000000000000000000001| 1 | 0 |
+-------------------------------------------+---+---+

把前面的零省略掉的話就是 110，轉換成十六進位是 0x6。那麼 9527 這個數字本體呢？它會被存到 _PyLongValue 的 ob_digit[0] 裡。所以 9527 在 _PyLongValue 的樣子會像這樣：

lv_tag: 0x6
ob_digit[0]: 9527

如果你有看懂的話，基本上只要是在 2^30 - 1 以內的數字，都能用 1 個 digit 表示。

天文數字！

但是，如果遇到更大的數字怎麼處理？例如 2 的 50 次方 1,125,899,906,842,624，換成二進位等於是 1 後面再加 49 個 0。因為一個 digit 只能放 30 個位元，所以需要再找另一個 digit 來放剩下的位元。這時候的 DATA 部分就會是 2（二進位 = 10），表示需要 2 個 digit 來表示：

 63                                         2   1   0
+-------------------------------------------+---+---+
|0000000000000000000000000000000000000000010| 1 | 0 |
+-------------------------------------------+---+---+

因此 lv_tag 就會是 1010，算成十六進位是 0xA。那 ob_digit 的部份呢？因為 2 的 50 次方的二進位總共有 50 位數，ob_digit[0] 會先吃掉後面 30 個 0，剩下的 1 以及後面的 19 個 0，就會被放到 ob_digit[1] 裡。

所以 2 的 50 次方的 _PyLongValue 會像這樣：

lv_tag: 0xA
ob_digit[0] = 0
ob_digit[1] = 524288

假設需要用到 3 個 digit 的情況呢？lv_tag 的 DATA 部分就會是 3（二進位 = 11），然後 ob_digit 就會有 3 個元素，以此類推，

 63                                         2   1   0
+-------------------------------------------+---+---+
|0000000000000000000000000000000000000000011| 1 | 0 |
+-------------------------------------------+---+---+

只要多用幾個 digit 就能存更多位數的數字，這也是為什麼 Python 可以處理任意大小的整數的原因，只要你的硬體設備的記憶體夠大，要算多大的數字都行，這就是 Python 在處理超級大的數字時候的計算方式。

雖然 2^50 在數學上是一個滿大的數字，但在 Python 的內部表示中，它實際上被分解成了兩個相對較小的數字來存儲（0 以及 524288）。這種表示方法可以讓 Python 很有效率的處理非常大的整數，而且不受典型 CPU 整數像是 2 的 32 或 64 次方的大小限制。

照這樣的設計，Python 的數字上限理論上可以非常非常大，如果把 DATA 部份的位元全部填 1 的話，就有 2 的 62 次方 - 1 這麼多個 digit，每個 digit 又能存 2 的 30 次方 - 1 的整數，這兩個數字相乘之後，以目前地球上的硬體設備來說，應該沒有夠大的記憶體可以存下這麼大的數字。

也就是說，Python 的整數可以非常大，16 GB 的記憶體，大概就能用來建立大約有十億位的數字，這可不是平常有機會見的到的數字。

小整數

在 Python 程式中，整數的使用算是非常頻繁，如果每次使用整數的時候都要重新建立一個整數物件的話，可能會造成不必要的記憶體浪費。所以 Python 會預先幫我們建立一些整數物件，讓我們需要的時候就直接拿來用就好，不需要重新建立。但數字那麼多，也不能無限上網把所有的數字都先建立一份，Python 只會先幫我們建立一些比較常用的整數，這算是 Python 為了讓效能更好的特殊設計。

在 Python 從 -5 到 256 之間的整數因為使用的頻率特別高，所以這些整數在 Python 裡是被預先建立好並且編譯進到 Python 本體裡的，所以當我們使用這些數字的時候不需要再重新建立，它們都是同一個物件，不信的話，我們可以用 is 關鍵字來試試看：

>>> a = 256
>>> b = 256
>>> a is b
True
>>> c = 257
>>> d = 257
>>> c is d
False

這是怎麼做到的？在前面介紹到的 PyLong_FromLong() 函數裡，有一段是這樣寫的：

// 檔案：Objects/longobject.c

if (IS_SMALL_INT(ival)) {
    return get_small_int((sdigit)ival);
}

這個 IS_SMALL_INT() 巨集是用來判斷是否是小整數的，看一下它的定義：

// 檔案：Objects/longobject.c

#define IS_SMALL_INT(ival) (-_PY_NSMALLNEGINTS <= (ival) && (ival) < _PY_NSMALLPOSINTS)

這個 _PY_NSMALLNEGINTS 跟 _PY_NSMALLPOSINTS 分別是什麼呢？

// 檔案：Include/internal/pycore_global_objects.h

#define _PY_NSMALLPOSINTS           257
#define _PY_NSMALLNEGINTS           5

就是 5 跟 257，所以 IS_SMALL_INT 巨集判斷的範圍就是在 -5 到 256 之間的整數。如果是小整數的話，就會呼叫 get_small_int() 函數：

// 檔案：Objects/longobject.c

static PyObject *
get_small_int(sdigit ival)
{
    assert(IS_SMALL_INT(ival));
    return (PyObject *)&_PyLong_SMALL_INTS[_PY_NSMALLNEGINTS + ival];
}

在定義 Python 的全域物件的檔案裡，有寫了這樣一段：

// 檔案：Include/internal/pycore_global_objects.h

struct _Py_static_objects {
    struct {
        /* Small integers are preallocated in this array so that they
         * can be shared.
         * The integers that are preallocated are those in the range
         * -_PY_NSMALLNEGINTS (inclusive) to _PY_NSMALLPOSINTS (exclusive).
         */
        PyLongObject small_ints[_PY_NSMALLNEGINTS + _PY_NSMALLPOSINTS];

        // ... 略 ...
    } singletons;
};

這個 small_ints 陣列是 static_objects 的成員，這些物件會在打包並且編譯 CPython 的時候就直接編進 Python 直譯器，也就是說當你啟動並執行 Python 的時候，它們早就已經存在。

本文同步刊載於 「為你自己學 Python - 整數的前世今生」