整數的前世今生
在 Python 的世界裡,整數是最基本也最常用的資料型態之一。你是否有想過在 Python 裡建立一個數字例如 n = 9527
的時候,背後究竟發生了什麼事情嗎?有些程式語言的數字會因為作業系統的不同而有最大值的限制,也許是 232 或 264,超過上限會出現「溢位(Overflow)」的情況,但為什麼 Python 可以處理任意大小的整數 ?還有在流程控制章節介紹到 is
關鍵字,為什麼在 -5
到 256
之間的整數有一些特別的性質?這個章節就來看看到底是怎麼回事。
數字是怎麼產生的?
我先寫一行簡單的 Python 程式:
n = 9527
檢視一下它的 Bytecode:
1 2 LOAD_CONST 0 (9527)
4 STORE_NAME 0 (n)
看起來滿簡單的,就是 LOAD_CONST
指令把 9527
這個常數載入到堆疊中,然後再透過 STORE_NAME
指令把它存到變數 n
。那麼,9527
這個值是怎麼建立的?如果在執行 Bytecode 的時候就已經是「載入」這個常數的話,那麼這個常數是在什麼時間點被建立的?
Bytecode 有分編譯跟執行兩個階段,在編譯階段,在 Python 裡負責產生整數的函數是 PyLong_FromLong()
:
PyObject *
PyLong_FromLong(long ival)
{
PyLongObject *v;
unsigned long abs_ival, t;
int ndigits;
// ... 略 ...
return (PyObject *)v;
}
這個函數會把一個整數轉換成 PyLongObject
物件,函數裡面的細節待會再來看。接下來,這個物件會被放到程式碼物件(Code Object)的常數表 co_consts
中:
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
指令在做什麼事:
inst(LOAD_CONST, (-- value)) {
value = GETITEM(frame->f_code->co_consts, oparg);
Py_INCREF(value);
}
看到了嗎?執行的時候會從目前的 Frame 的 Code Object 裡取得在編譯時期建立的常數表 co_consts
拿之前建立好數字物件,而不是重新呼叫 PyLong_FromLong()
再重新建立一個新的,這樣效率才會好。這 裡的 Frame 跟 Code Object 在後面的章節會有詳細的說明,目前可先把 Frame 當做是目前函數的執行環境,而 Code Object 則是函數的程式碼。
整數物件
剛才說到,在 Bytecode 編譯階段 PyLong_FromLong()
函數會把數字包成 PyLongObject
物件並存到 co_consts
裡,那麼這個 PyLongObject
長什麼樣子:
struct _longobject {
PyObject_HEAD
_PyLongValue long_value;
};
結構還算簡單,只有一個成員變數 long_value
,這是一個 _PyLongValue
結構:
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
表示。