【CPython3.6源码分析】PyLongObject

参考

PyLongObject

在 Python2 中,存在 PyIntObject 和 PyLongObject 两种类型。前者是一个定长对象,后者是一个变长对象。Python3中 只存在后者。在 Python2 的结构体中 定义的是 long ob_ival,而 Python3 中定义的是只有1个元素的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// longobject.h.10
typedef struct _longobject PyLongObject;

// longintrepr.h.85
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1]; // digit 与平台相关,长度不一致
};
/*
ob_size == 0 -> zero
ob_size < 0 -> 负数
PyLong_SHIFT == 30 or 15
value == SUM(for i=0 through abs(ob_size)-1) ob_digit[i] * 2**(SHIFT*i)
*/

由上可以看出,在 Python 中,整形的存储方式,是存储在一个数组中。因此通过控制 PyVarObject 的 ob_size 值,可以表示出非常非常大的数。

PyTypeObject

1
2
3
4
5
6
7
8
9
10
11
12
13
// longobject.c.5431
PyTypeObject PyLong_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"int", /* tp_name */
offsetof(PyLongObject, ob_digit), /* tp_basicsize */
sizeof(digit), /* tp_itemsize */
...
&long_as_number, /* tp_as_number */
0, /* tp_as_sequence */
0, /* tp_as_mapping */
long_new, /* tp_new */
PyObject_Del, /* tp_free */
};

可见:

  • int对象的类型对象是 PyLong_Type
  • 从之前的 PyObject 分析也能得出 PyLong_Type的类型对象是 PyType_Type
  • int对象,只支持 as_number,不支持作为序列、映射对象操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// longobject.c.5393
static PyNumberMethods long_as_number = {
(binaryfunc)long_add, /*nb_add*/
(binaryfunc)long_sub, /*nb_subtract*/
(binaryfunc)long_mul, /*nb_multiply*/
...
long_float, /*nb_float*/
...
};

// longobject.c.3108
static PyObject *
long_add(PyLongObject *a, PyLongObject *b)
{
PyLongObject *z;
.. // 检查,计算,返回
return (PyObject *)z;
}

long_as_number 是前文所述 PyNumberMethods 函数簇的 一个结构体实例,初始化了大量方法。如上面的 long_add 操作,创建并返回一个新的 PyObject。

对象池 small_ints

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// longobject.c.12
#define NSMALLPOSINTS 257
#define NSMALLNEGINTS 5
static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];

// longobject.c.5514
int _PyLong_Init(void)
{
int ival, size;
PyLongObject *v = small_ints;

for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++, v++) {
size = (ival < 0) ? -1 : ((ival == 0) ? 0 : 1);
(void)PyObject_INIT(v, &PyLong_Type); // Py_TYPE(op) = tp;

Py_SIZE(v) = size;
v->ob_digit[0] = (digit)abs(ival);
}
return 1;
}

如上,当 Python 初始化时,_PyLong_Init 被调用,然后会 初始化 small_ints数组,作为小整数对象池来共享使用。

前面也提到了 _longobject 结构体中 定义的是 digit ob_digit[1],从源码中可以发现:

  1. small_ints数组长度,默认[-5, 256]
  2. size 与 值的关系:小于0 or 等于0 or 大于0

小整数共享

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// longobject.c.51
#define CHECK_SMALL_INT(ival) \
do if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \
return get_small_int((sdigit)ival); \
} while(0)

// longobject.c.37
static PyObject * get_small_int(sdigit ival)
{
PyObject *v;
assert(-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS);
v = (PyObject *)&small_ints[ival + NSMALLNEGINTS];
Py_INCREF(v);
return v;
}

如上,通过宏 CHECK_SMALL_INT,可以共享小整数。返回增加引用计数,并且返回指针。

创建对象

1
2
3
4
5
6
7
8
9
10
11
PyObject* PyLong_FromLong(long v)
PyObject* PyLong_FromUnsignedLong(unsigned long v)
PyObject* PyLong_FromSsize_t(Py_ssize_t v)
PyObject* PyLong_FromSize_t(size_t v)
PyObject* PyLong_FromLongLong(long long v)
PyObject* PyLong_FromUnsignedLongLong(unsigned long long v)
PyObject* PyLong_FromDouble(double v)
PyObject* PyLong_FromString(const char *str, char **pend, int base)
PyObject* PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base)
PyObject* PyLong_FromUnicodeObject(PyObject *u, int base)
PyObject* PyLong_FromVoidPtr(void *p)

在 CPython3.6.6 中,提供了大量创建 PyLongObject 的方法。下面,我们将查看其中一个。

PyLong_FromLong

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
PyObject * PyLong_FromLong(long ival)
{
PyLongObject *v;
unsigned long abs_ival;
unsigned long t; /* unsigned so >> doesn't propagate sign bit */
int ndigits = 0;
int sign;

CHECK_SMALL_INT(ival); // 宏,尝试小整数共享

// 处理得到 abs_ival(unsigned long)
if (ival < 0) {
/* negate: can't write this as abs_ival = -ival since that
invokes undefined behaviour when ival is LONG_MIN */
abs_ival = 0U-(unsigned long)ival;
sign = -1;
}
else {
abs_ival = (unsigned long)ival;
sign = ival == 0 ? 0 : 1;
}

/* 处理 single-digit ints */
if (!(abs_ival >> PyLong_SHIFT)) {
v = _PyLong_New(1);
if (v) {
Py_SIZE(v) = sign;
v->ob_digit[0] = Py_SAFE_DOWNCAST(abs_ival, unsigned long, digit);
// pyport.h.304: #define Py_SAFE_DOWNCAST(VALUE, WIDE, NARROW) (NARROW)(VALUE)
}
return (PyObject*)v;
}

/* Larger numbers: loop to determine number of digits */
t = abs_ival;
while (t) {
++ndigits;
t >>= PyLong_SHIFT;
}
v = _PyLong_New(ndigits);
if (v != NULL) {
digit *p = v->ob_digit;
Py_SIZE(v) = ndigits*sign;
t = abs_ival;
while (t) {
*p++ = Py_SAFE_DOWNCAST(t & PyLong_MASK, unsigned long, digit);
t >>= PyLong_SHIFT;
}
}
return (PyObject *)v;
}

如上,创建一个 int 对象,主要有以下几个步骤:

  1. 尝试从对象池中获取
  2. 处理获取 abs_value
  3. 处理 single-digit
  4. 循环处理 Larger numbers

代码很简单,下面只看一下 _PyLong_New 具体逻辑。

_PyLong_New

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// longobject.c.179
#define MAX_LONG_DIGITS \
((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))

PyLongObject * _PyLong_New(Py_ssize_t size)
{
PyLongObject *result;
if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
PyErr_SetString(PyExc_OverflowError,
"too many digits in integer");
return NULL;
}
result = PyObject_MALLOC(offsetof(PyLongObject, ob_digit) +
size*sizeof(digit));
return (PyLongObject*)PyObject_INIT_VAR(result, &PyLong_Type, size);
}

从代码可以看出,能够表示的最大整数是跟堆内存相关的,几乎可以表示无穷大的数了。