484
[筆記]Python的整數對象：PyIntObject
一般沒有特指，參考的是Python 2.7.2的源碼。
在intobject.h的開頭就有英文注釋，對PyIntObject進行了一下簡單介紹。
原文如下：
/*
PyIntObject represents a (long) integer. This is an immutable object;
an integer cannot change its value after creation.
There are functions to create new integer objects, to test an object
for integer-ness, and to get the integer value. The latter functions
returns -1 and sets errno to EBADF if the object is not an PyIntObject.
None of the functions should be applied to nil objects.
The type PyIntObject is (unfortunately) exposed here so we can declare
_Py_TrueStruct and _Py_ZeroStruct in boolobject.h; don't use this.
*/
從注釋可以看出以下幾點：
1. PyIntObject實際是long類型；
2. 不可變對象，即創建後不能改變它的值；
3. PyIntObject提供了若幹函數；
關於第二點，可以參考如下代碼：
所以，看上去是a改變了值，實際上a是引用了不同的整數對象。
注釋下麵就是PyIntObject的定義了。
typedef struct {
PyObject_HEAD
long ob_ival;
} PyIntObject;
所以展開來的話，主要就包含了引用計數、對象類型和表示值的long ob_ival。
每一種類型有獨有的特性和操作，對象的很多信息都放在對應的類型中，比如PyIntObject很多信息放在PyInt_Type中。
PyInt_Type定義在intobject.c中：
PyTypeObject PyInt_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"int",
sizeof(PyIntObject),
0,
(destructor)int_dealloc, /* tp_dealloc */
(printfunc)int_print, /* tp_print */
0, /* tp_getattr */
0, /* tp_setattr */
(cmpfunc)int_compare, /* tp_compare */
(reprfunc)int_to_decimal_string, /* tp_repr */
&int_as_number, /* tp_as_number */
0, /* tp_as_sequence */
0, /* tp_as_mapping */
(hashfunc)int_hash, /* tp_hash */
0, /* tp_call */
(reprfunc)int_to_decimal_string, /* tp_str */
PyObject_GenericGetAttr, /* tp_getattro */
0, /* tp_setattro */
0, /* tp_as_buffer */
Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
Py_TPFLAGS_BASETYPE | Py_TPFLAGS_INT_SUBCLASS, /* tp_flags */
int_doc, /* tp_doc */
0, /* tp_traverse */
0, /* tp_clear */
0, /* tp_richcompare */
0, /* tp_weaklistoffset */
0, /* tp_iter */
0, /* tp_iternext */
int_methods, /* tp_methods */
0, /* tp_members */
int_getset, /* tp_getset */
0, /* tp_base */
0, /* tp_dict */
0, /* tp_descr_get */
0, /* tp_descr_set */
0, /* tp_dictoffset */
0, /* tp_init */
0, /* tp_alloc */
int_new, /* tp_new */
(freefunc)int_free, /* tp_free */
};
所以前麵幾項宏展開來是：
PyTypeObject PyInt_Type = {
_PyObject_EXTRA_INIT
1, //引用計數
PyType_Type, //對象類型
0, //可變部分中items的數目，PyIntObject為不可變對象
"int", //類型名稱
sizeof(PyIntObject), //該類型的基本大小
0, //類型包含的item的大小
......
}
後麵的信息就是一些類型擁有的操作，顯而易見的有創建對象和刪除對象、輸出、比較、整數操作和成員函數。
比如int_as_numbers的定義如下：
static PyNumberMethods int_as_number = {
(binaryfunc)int_add, /*nb_add*/
(binaryfunc)int_sub, /*nb_subtract*/
(binaryfunc)int_mul, /*nb_multiply*/
(binaryfunc)int_classic_div, /*nb_divide*/
(binaryfunc)int_mod, /*nb_remainder*/
(binaryfunc)int_divmod, /*nb_divmod*/
(ternaryfunc)int_pow, /*nb_power*/
(unaryfunc)int_neg, /*nb_negative*/
(unaryfunc)int_int, /*nb_positive*/
(unaryfunc)int_abs, /*nb_absolute*/
(inquiry)int_nonzero, /*nb_nonzero*/
(unaryfunc)int_invert, /*nb_invert*/
(binaryfunc)int_lshift, /*nb_lshift*/
(binaryfunc)int_rshift, /*nb_rshift*/
(binaryfunc)int_and, /*nb_and*/
(binaryfunc)int_xor, /*nb_xor*/
(binaryfunc)int_or, /*nb_or*/
......
}
這裏列出了一些基本運算，如加減乘除，還有位移、邏輯、冪運算等。
考慮一下加法運算過程。
static PyObject *
int_add(PyIntObject *v, PyIntObject *w)
{
register long a, b, x;
CONVERT_TO_LONG(v, a);
CONVERT_TO_LONG(w, b);
/* casts in the line below avoid undefined behaviour on overflow */
x = (long)((unsigned long)a + b);
if ((x^a) >= 0 || (x^b) >= 0)
return PyInt_FromLong(x);
return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
}
實際上是long類型的加法運算，並對運算結果進行判斷是否溢出。
采取異或運算判斷與0的比較結果，是為了判斷符號位的變化。
考慮：正數+正數，負數+負數，正數+負數。
第一種情況下溢出，那麼結果x將為負數，不滿足if判斷。
第二種情況下溢出，那麼結果x將為正數，不滿足if判斷。
第三種情況，不會溢出，並且x的符號位必然和其中一個數相同，滿足或的if判斷。
最後是關於小整數和大整數的管理問題。
Python為小整數建立了內存池，小整數的範圍可以自己定義（修改源碼重新編譯），因為小整數是使用十分頻繁的對象。
而對於大整數，Python也采取了一定的措施。
先來看看創建一個整數對象的過程。
參考如下函數：
PyObject *
PyInt_FromLong(long ival)
{
register PyIntObject *v;
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
v = small_ints[ival + NSMALLNEGINTS];
Py_INCREF(v);
#ifdef COUNT_ALLOCS
if (ival >= 0)
quick_int_allocs++;
else
quick_neg_int_allocs++;
#endif
return (PyObject *) v;
}
#endif
if (free_list == NULL) {
if ((free_list = fill_free_list()) == NULL)
return NULL;
}
/* Inline PyObject_New */
v = free_list;
free_list = (PyIntObject *)Py_TYPE(v);
PyObject_INIT(v, &PyInt_Type);
v->ob_ival = ival;
return (PyObject *) v;
}
該函數會對傳進來的參數判斷是否在小整數範圍內（-NSMALLNEGINT ～ NSMALLPOSINTS），如果在就直接在small_ints數組裏取。
static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
如果不是小整數，那麼涉及的就是對大整數的處理。
在對大整數的處理中，首先涉及的是free_list，它被如下初始化：
static PyIntObject *free_list = NULL;
所以，當第一次遇到大整數的時候，會調用函數fill_free_list()來新建一個鏈表。
#define BLOCK_SIZE 1000 /* 1K less typical malloc overhead */
#define BHEAD_SIZE 8 /* Enough for a 64-bit pointer */
#define N_INTOBJECTS ((BLOCK_SIZE - BHEAD_SIZE) / sizeof(PyIntObject))
struct _intblock {
struct _intblock *next;
PyIntObject objects[N_INTOBJECTS];
};
typedef struct _intblock PyIntBlock;
static PyIntBlock *block_list = NULL;
static PyIntObject *free_list = NULL;
static PyIntObject *
fill_free_list(void)
{
PyIntObject *p, *q;
/* Python's object allocator isn't appropriate for large blocks. */
p = (PyIntObject *) PyMem_MALLOC(sizeof(PyIntBlock));
if (p == NULL)
return (PyIntObject *) PyErr_NoMemory();
((PyIntBlock *)p)->next = block_list; //在成功分配內存後，將next指針指向上一個塊（第一次為NULL）
block_list = (PyIntBlock *)p; //讓block_list始終指向最新的塊
/* Link the int objects together, from rear to front, then return
the address of the last int object in the block. */
p = &((PyIntBlock *)p)->objects[0]; //指針p指向數組中第一個元素
q = p + N_INTOBJECTS; //指針q指向數組中最後一個元素的下一個（越界了）
while (--q > p) //利用（濫用）對象的ob_type指針來將所有元素鏈接在一起
Py_TYPE(q) = (struct _typeobject *)(q-1);
Py_TYPE(q) = NULL; //最後一個（實際是第一個，因為是從最後向前遍曆）的ob_type指針指向NULL
return p + N_INTOBJECTS - 1; //返回數組的最後一個元素的地址
}
注釋裏麵說明了Python的對象分配器不適合多個大內存塊，所以一次獲取的大小是sizeof(PyIntBlock)。
PyIntBlock裏麵包含了一個next指針和一個PyIntObject數組。
為了方便，將說明放在代碼中進行注釋。
接著回到PyInt_FromLong函數
{
......
v = free_list; //v指向數組的最後一個元素，最新未使用的PyIntObject
free_list = (PyIntObject *)Py_TYPE(v); //free_list指向最新未使用的PyIntObject，目前未倒2個數組元素，注意，這裏是用ob_type指針來鏈接的
PyObject_INIT(v, &PyInt_Type); //對v進行初始化，即剛得到的整數對象
v->ob_ival = ival; //設置整數對象的值
return (PyObject *) v; //返回整數對象
}
補充。
intobject.c開頭的一段注釋值得注意。
/* Integers are quite normal objects, to make object handling uniform.
(Using odd pointers to represent integers would save much space
but require extra checks for this special case throughout the code.)
Since a typical Python program spends much of its time allocating
and deallocating integers, these operations should be very fast.
Therefore we use a dedicated allocation scheme with a much lower
overhead (in space and time) than straight malloc(): a simple
dedicated free list, filled when necessary with memory from malloc().
block_list is a singly-linked list of all PyIntBlocks ever allocated,
linked via their next members. PyIntBlocks are never returned to the
system before shutdown (PyInt_Fini).
free_list is a singly-linked list of available PyIntObjects, linked
via abuse of their ob_type members.
*/
這一段主要是說為了避免過多的內存分配開銷，采用了特定的策略來管理整數對象的內存分配。
block_list是一個單向鏈表，保存著所有分配過的PyIntBlock，通過next指針鏈接，它會一直存在著，直到係統關閉（PyInt_Fini）。
free_list是PyIntObject的單向鏈表，通過對象的ob_type成員鏈接，這是忽略類型安全的“濫用”。
小整數也是通過這兩個數據結構來管理的，隻不過它是在一開始就初始化好，而大整數是運行時需要才創建的。
下麵是大整數創建過程的草圖。
最後更新：2017-04-02 22:16:33