blog
blog copied to clipboard
Published
20 hours ago •
junnplus
junnplus
Python中的整数对象
Python3中的整数对象PyLongObject定义在Include/longobject.h：
/* Long (arbitrary precision) integer object interface */
typedef struct _longobject PyLongObject; /* Revealed in longintrepr.h */
_longobject具体实现在Include/longintrepr.h：
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
在《Python中的对象》中也提到过Python3中的PyLongObject是变长对象（PyVarObject），另外在Python中的整数对象又是“不可变对象”（immutable）。
我们是根据对象维护数据的可变性（是否能改变对象的内容）将对象分为“可变对象”（mutable）和“不可变对象”（immutable）。
0x00 整数对象的存储方式
在Python3中，用2**PyLong_SHIFT进制的字符串来表示大整数。
PyLong_SHIFT的值定义在Include/longintrepr.h中：
/* Parameters of the integer representation. There are two different
sets of parameters: one set for 30-bit digits, stored in an unsigned 32-bit
integer type, and one set for 15-bit digits with each digit stored in an
unsigned short. The value of PYLONG_BITS_IN_DIGIT, defined either at
configure time or in pyport.h, is used to decide which digit size to use.
Type 'digit' should be able to hold 2*PyLong_BASE-1, and type 'twodigits'
should be an unsigned integer type able to hold all integers up to
PyLong_BASE*PyLong_BASE-1. x_sub assumes that 'digit' is an unsigned type,
and that overflow is handled by taking the result modulo 2**N for some N >
PyLong_SHIFT. The majority of the code doesn't care about the precise
value of PyLong_SHIFT, but there are some notable exceptions:
- long_pow() requires that PyLong_SHIFT be divisible by 5
- PyLong_{As,From}ByteArray require that PyLong_SHIFT be at least 8
- long_hash() requires that PyLong_SHIFT is *strictly* less than the number
of bits in an unsigned long, as do the PyLong <-> long (or unsigned long)
conversion functions
- the Python int <-> size_t/Py_ssize_t conversion functions expect that
PyLong_SHIFT is strictly less than the number of bits in a size_t
- the marshal code currently expects that PyLong_SHIFT is a multiple of 15
- NSMALLNEGINTS and NSMALLPOSINTS should be small enough to fit in a single
digit; with the current values this forces PyLong_SHIFT >= 9
The values 15 and 30 should fit all of the above requirements, on any
platform.
*/
#if PYLONG_BITS_IN_DIGIT == 30
typedef uint32_t digit;
typedef int32_t sdigit; /* signed variant of digit */
typedef uint64_t twodigits;
typedef int64_t stwodigits; /* signed variant of twodigits */
#define PyLong_SHIFT 30
#define _PyLong_DECIMAL_SHIFT 9 /* max(e such that 10**e fits in a digit) */
#define _PyLong_DECIMAL_BASE ((digit)1000000000) /* 10 ** DECIMAL_SHIFT */
#elif PYLONG_BITS_IN_DIGIT == 15
typedef unsigned short digit;
typedef short sdigit; /* signed variant of digit */
typedef unsigned long twodigits;
typedef long stwodigits; /* signed variant of twodigits */
#define PyLong_SHIFT 15
#define _PyLong_DECIMAL_SHIFT 4 /* max(e such that 10**e fits in a digit) */
#define _PyLong_DECIMAL_BASE ((digit)10000) /* 10 ** DECIMAL_SHIFT */
#else
#error "PYLONG_BITS_IN_DIGIT should be 15 or 30"
#endif
#define PyLong_BASE ((digit)1 << PyLong_SHIFT)
#define PyLong_MASK ((digit)(PyLong_BASE - 1))
#if PyLong_SHIFT % 5 != 0
#error "longobject.c requires that PyLong_SHIFT be divisible by 5"
#endif
PyLong_SHIFT的值可以是30或15，分别代表Python把30位大小的数值存在uint32_t类型的ob_digit数组中或保存15位的数值在unsigned short类型的ob_digit数组。
我们再来看一眼Include/longintrepr.h中对PyLongObject(_longobject)的定义：
/* Long integer representation.
The absolute value of a number is equal to
SUM(for i=0 through abs(ob_size)-1) ob_digit[i] * 2**(SHIFT*i)
Negative numbers are represented with ob_size < 0;
zero is represented by ob_size == 0.
In a normalized number, ob_digit[abs(ob_size)-1] (the most significant
digit) is never zero. Also, in all cases, for all valid i,
0 <= ob_digit[i] <= MASK.
The allocation function takes care of allocating extra memory
so that ob_digit[0] ... ob_digit[abs(ob_size)-1] are actually available.
CAUTION: Generic code manipulating subtypes of PyVarObject has to
aware that ints abuse ob_size's sign bit.
*/
struct _longobject {
PyObject_VAR_HEAD // PyVarObject ob_base;
digit ob_digit[1];
};
从注释我们可以看出：
- 整数的绝对值计算方式：
SUM(for i=0 through abs(ob_size)-1) ob_digit[i] * 2**(SHIFT*i) - 负数的
ob_size< 0，即正负符号信息由ob_size保存 - 0值被表示成
obsize== 0 ob_digit[abs(ob_size)-1]不为零，且0 <= ob_digit[i] <= MASK
当SHIFT为30的时候我们来看-1152921506754330627这个数字在ob_digit数组的存储方式。
具体的算法在Objects/longobject.c中的PyLong_FromLong实现：
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);
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;
}
/* Fast path for 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);
}
return (PyObject*)v;
}
#if PyLong_SHIFT==15
/* 2 digits */
if (!(abs_ival >> 2*PyLong_SHIFT)) {
v = _PyLong_New(2);
if (v) {
Py_SIZE(v) = 2*sign;
v->ob_digit[0] = Py_SAFE_DOWNCAST(
abs_ival & PyLong_MASK, unsigned long, digit);
v->ob_digit[1] = Py_SAFE_DOWNCAST(
abs_ival >> PyLong_SHIFT, unsigned long, digit);
}
return (PyObject*)v;
}
#endif
/* 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;
}
0x01 整数对象的创建
对象的创建总是调用与对象对应的类型对象的tp_new，PyLongObject的ob_type指针指向的是PyLong_Type，定义在Objects/longobject.c。可以在PyLong_Type找到tp_new的定义：
PyTypeObject PyLong_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"int", /* tp_name */
...
long_new, /* tp_new */
PyObject_Del, /* tp_free */
};
Objects/clinic/longobject.c.h定义了long_new函数:
static PyObject *
long_new_impl(PyTypeObject *type, PyObject *x, PyObject *obase);
static PyObject *
long_new(PyTypeObject *type, PyObject *args, PyObject *kwargs)
{
PyObject *return_value = NULL;
static const char * const _keywords[] = {"", "base", NULL};
static _PyArg_Parser _parser = {"|OO:int", _keywords, 0};
PyObject *x = NULL;
PyObject *obase = NULL;
if (!_PyArg_ParseTupleAndKeywordsFast(args, kwargs, &_parser,
&x, &obase)) {
goto exit;
}
return_value = long_new_impl(type, x, obase);
exit:
return return_value;
}
具体实现又回到了Objects/longobject.c的long_new_impl函数:
/*[clinic input]
@classmethod
int.__new__ as long_new
x: object(c_default="NULL") = 0
/
base as obase: object(c_default="NULL") = 10
[clinic start generated code]*/
static PyObject *
long_new_impl(PyTypeObject *type, PyObject *x, PyObject *obase)
/*[clinic end generated code: output=e47cfe777ab0f24c input=81c98f418af9eb6f]*/
{
Py_ssize_t base;
if (type != &PyLong_Type)
return long_subtype_new(type, x, obase); /* Wimp out */
if (x == NULL) {
if (obase != NULL) {
PyErr_SetString(PyExc_TypeError,
"int() missing string argument");
return NULL;
}
return PyLong_FromLong(0L);
}
if (obase == NULL)
return PyNumber_Long(x);
base = PyNumber_AsSsize_t(obase, NULL);
if (base == -1 && PyErr_Occurred())
return NULL;
if ((base != 0 && base < 2) || base > 36) {
PyErr_SetString(PyExc_ValueError,
"int() base must be >= 2 and <= 36");
return NULL;
}
if (PyUnicode_Check(x))
return PyLong_FromUnicodeObject(x, (int)base);
else if (PyByteArray_Check(x) || PyBytes_Check(x)) {
char *string;
if (PyByteArray_Check(x))
string = PyByteArray_AS_STRING(x);
else
string = PyBytes_AS_STRING(x);
return _PyLong_FromBytes(string, Py_SIZE(x), (int)base);
}
else {
PyErr_SetString(PyExc_TypeError,
"int() can't convert non-string with explicit base");
return NULL;
}
}
穿插下Python3中int类型的Docstring：
int(x=0) -> integer
int(x, base=10) -> integer
Convert a number or string to an integer, or return 0 if no arguments
are given. If x is a number, return x.__int__(). For floating point
numbers, this truncates towards zero.
If x is not a number or if base is given, then x must be a string,
bytes, or bytearray instance representing an integer literal in the
given base. The literal can be preceded by '+' or '-' and be surrounded
by whitespace. The base defaults to 10. Valid bases are 0 and 2-36.
Base 0 means to interpret the base from the string as an integer literal.
>>> int('0b100', base=0)
4
从long_new_impl的函数中我们可以看出来，int的参数x和base分别对应着long_new_impl的后两个参数。
为了创建PyLongObject对象，Python分几种情况处理：
x为NULL->PyLong_FromLongobase为NULL->PyNumber_Longx和obase都不为NULLPyUnicode->PyLong_FromUnicodeObject->PyLong_FromStringPyByteArray/PyBytes->_PyLong_FromBytes->PyLong_FromString
而实际上PyLong_FromUnicodeObject和_PyLong_FromBytes都是先将PyUnicode对象和PyByteArrry/PyBytes对象转化成string（c中的char *），然后再调用PyLong_FromString。
PyLong_FromLong
前面也提到了PyLong_FromLong的实现：
/* Create a new int object from a C long int */
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);
....
}
PyLong_FromLong函数中有一行CHECK_SMALL_INT(ival);，我们来看看CHECK_SMALL_INT的定义：
static PyObject *
get_small_int(sdigit ival)
{
PyObject *v;
assert(-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS);
v = (PyObject *)&small_ints[ival + NSMALLNEGINTS];
Py_INCREF(v);
#ifdef COUNT_ALLOCS
if (ival >= 0)
quick_int_allocs++;
else
quick_neg_int_allocs++;
#endif
return v;
}
#define CHECK_SMALL_INT(ival) \
do if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \
return get_small_int((sdigit)ival); \
} while(0)
这里看起来似乎如果ival的值在[-NSMALLNEGINTS, NSMALLPOSINTS)范围内会直接返回small_ints中对应的值（ival + NSMALLNEGINTS)。
我们再来看一个问题：
>>> a = -6
>>> b = -6
>>> a is b
False
>>> a = -5
>>> b = -5
>>> a is b
True
>>> a = 256
>>> b = 256
>>> a is b
True
>>> a = 257
>>> b = 257
>>> a is b
False
是什么原因导致这种差异？这里就要提到Python中整数对象是如何存活在系统内存中的。
Python在创建整数对象时，分为小整数和大整数区别对待。
小整数对象
小整数的范围在Objects/longobject.c定义着：
#ifndef NSMALLPOSINTS
#define NSMALLPOSINTS 257
#endif
#ifndef NSMALLNEGINTS
#define NSMALLNEGINTS 5
#endif
...
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
/* Small integers are preallocated in this array so that they
can be shared.
The integers that are preallocated are those in the range
-NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
*/
static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
从代码片段我们可以知道，Python会预先分配默认为[-5, 257)之间的小整数到small_ints指针数组（对象池）来缓存，对象池里每一个PyLongObject对象都能被任意地共享。小整数一般是Python程序中高频使用的整数对象，使用小整数对象池可以避免在一些简单的循环和计算中频繁的调用malloc分配内存和free释放内存。这样频繁的内存操作不仅降低运行效率吗，而且会在系统堆上造成大量内存碎片，严重影响Python整体性能。
small_ints中的PyLongObject对象是在Python初始化的时候调用_PyLong_Init函数创建的：
int
_PyLong_Init(void)
{
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
int ival, size;
PyLongObject *v = small_ints;
for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++, v++) {
size = (ival < 0) ? -1 : ((ival == 0) ? 0 : 1);
if (Py_TYPE(v) == &PyLong_Type) {
/* The element is already initialized, most likely
* the Python interpreter was initialized before.
*/
Py_ssize_t refcnt;
PyObject* op = (PyObject*)v;
refcnt = Py_REFCNT(op) < 0 ? 0 : Py_REFCNT(op);
_Py_NewReference(op);
/* _Py_NewReference sets the ref count to 1 but
* the ref count might be larger. Set the refcnt
* to the original refcnt + 1 */
Py_REFCNT(op) = refcnt + 1;
assert(Py_SIZE(op) == size);
assert(v->ob_digit[0] == (digit)abs(ival));
}
else {
(void)PyObject_INIT(v, &PyLong_Type);
}
Py_SIZE(v) = size;
v->ob_digit[0] = (digit)abs(ival);
}
#endif
_PyLong_Zero = PyLong_FromLong(0);
if (_PyLong_Zero == NULL)
return 0;
_PyLong_One = PyLong_FromLong(1);
if (_PyLong_One == NULL)
return 0;
/* initialize int_info */
if (Int_InfoType.tp_name == NULL) {
if (PyStructSequence_InitType2(&Int_InfoType, &int_info_desc) < 0)
return 0;
}
return 1;
}
大整数对象
在《Python的类型》提到过Python2中的整数对象其实有两种：PyIntObject和PyLongObject，在Python2中的大整数其实指的是PyIntObject范围内的不在[-NSMALLNEGINTS, NSMALLPOSINTS)这个区间的值，而Python3中只有PyLongObject一种整数对象，所以大整数指的就是除小整数以外的值。
这里为什么提到Python2的PyIntObject整数对象呢？我们先来看Python2的PyIntObject定义，在Objects/intobject.c中：
typedef struct {
PyObject_HEAD
long ob_ival;
} PyIntObject
Python2中的PyIntObject实际是对c中的long的包装。所以Python2也提供了专门的缓存池，供大整数轮流使用，避免每次使用不断的malloc分配内存带来的效率损耗。具体细节可以参考《Python源码剖析》。
Python3中的PyLongObject就没有使用缓存池，直接malloc/free操作内存，这也是Py3的性能损耗的一个方面。
下面就是PyLong_FromLong调用申请内存空间的函数_PyLong_New:
/* Allocate a new int object with size digits.
Return NULL and set exception if we run out of memory. */
#define MAX_LONG_DIGITS \
((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))
PyLongObject *
_PyLong_New(Py_ssize_t size)
{
PyLongObject *result;
/* Number of bytes needed is: offsetof(PyLongObject, ob_digit) +
sizeof(digit)*size. Previous incarnations of this code used
sizeof(PyVarObject) instead of the offsetof, but this risks being
incorrect in the presence of padding between the PyVarObject header
and the digits. */
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));
if (!result) {
PyErr_NoMemory();
return NULL;
}
return (PyLongObject*)PyObject_INIT_VAR(result, &PyLong_Type, size);
}
可以看出来申请的内存大小是ob_digit相对结构体PyLongObject的偏移大小加上size * digit类型的大小。
PyNumber_Long
PyNumber_Long定义在Objects/abstract.c:
PyObject *
PyNumber_Long(PyObject *o)
{
PyObject *result;
PyNumberMethods *m;
PyObject *trunc_func;
Py_buffer view;
_Py_IDENTIFIER(__trunc__);
if (o == NULL) {
return null_error();
}
if (PyLong_CheckExact(o)) {
Py_INCREF(o);
return o;
}
m = o->ob_type->tp_as_number;
if (m && m->nb_int) { /* This should include subclasses of int */
result = (PyObject *)_PyLong_FromNbInt(o);
if (result != NULL && !PyLong_CheckExact(result)) {
Py_SETREF(result, _PyLong_Copy((PyLongObject *)result));
}
return result;
}
trunc_func = _PyObject_LookupSpecial(o, &PyId___trunc__);
if (trunc_func) {
result = _PyObject_CallNoArg(trunc_func);
Py_DECREF(trunc_func);
if (result == NULL || PyLong_CheckExact(result)) {
return result;
}
if (PyLong_Check(result)) {
Py_SETREF(result, _PyLong_Copy((PyLongObject *)result));
return result;
}
/* __trunc__ is specified to return an Integral type,
but int() needs to return an int. */
m = result->ob_type->tp_as_number;
if (m == NULL || m->nb_int == NULL) {
PyErr_Format(
PyExc_TypeError,
"__trunc__ returned non-Integral (type %.200s)",
result->ob_type->tp_name);
Py_DECREF(result);
return NULL;
}
Py_SETREF(result, (PyObject *)_PyLong_FromNbInt(result));
if (result != NULL && !PyLong_CheckExact(result)) {
Py_SETREF(result, _PyLong_Copy((PyLongObject *)result));
}
return result;
}
if (PyErr_Occurred())
return NULL;
if (PyUnicode_Check(o))
/* The below check is done in PyLong_FromUnicode(). */
return PyLong_FromUnicodeObject(o, 10);
if (PyBytes_Check(o))
/* need to do extra error checking that PyLong_FromString()
* doesn't do. In particular int('9\x005') must raise an
* exception, not truncate at the null.
*/
return _PyLong_FromBytes(PyBytes_AS_STRING(o),
PyBytes_GET_SIZE(o), 10);
if (PyByteArray_Check(o))
return _PyLong_FromBytes(PyByteArray_AS_STRING(o),
PyByteArray_GET_SIZE(o), 10);
if (PyObject_GetBuffer(o, &view, PyBUF_SIMPLE) == 0) {
PyObject *bytes;
/* Copy to NUL-terminated buffer. */
bytes = PyBytes_FromStringAndSize((const char *)view.buf, view.len);
if (bytes == NULL) {
PyBuffer_Release(&view);
return NULL;
}
result = _PyLong_FromBytes(PyBytes_AS_STRING(bytes),
PyBytes_GET_SIZE(bytes), 10);
Py_DECREF(bytes);
PyBuffer_Release(&view);
return result;
}
return type_error("int() argument must be a string, a bytes-like object "
"or a number, not '%.200s'", o);
}
PyNumber_Long处理了obase为NULL的情况，对于能支持数值对象操作(o->ob_type->tp_as_number->nb_int)的，并且会借助_PyLong_Copy和Py_SETREF实现了把数值的PyObject *对象转成PyLongObject *对象。
// Include/object.h
#define Py_SETREF(op, op2) \
do { \
PyObject *_py_tmp = (PyObject *)(op); \
(op) = (op2); \
Py_DECREF(_py_tmp); \
} while (0)
// Object/longobject.c
PyObject *
_PyLong_Copy(PyLongObject *src)
{
PyLongObject *result;
Py_ssize_t i;
assert(src != NULL);
i = Py_SIZE(src);
if (i < 0)
i = -(i);
if (i < 2) {
sdigit ival = MEDIUM_VALUE(src);
CHECK_SMALL_INT(ival);
}
result = _PyLong_New(i);
if (result != NULL) {
Py_SIZE(result) = Py_SIZE(src);
while (--i >= 0)
result->ob_digit[i] = src->ob_digit[i];
}
return (PyObject *)result;
}
在Python对象的类型中，有三组重要的操作族：
tp_as_number、tp_as_sequence、tp_as_mapping，它们分别指向PyNumberMethods、PySequenceMethods和PyMappingMethods函数族。如果一个对象能被视为数值对象，那么在对应的类型中，tp_as_number指向对该对象的数值操作。同样，PySequenceMethods和PyMappingMethods分别定义了作为一个序列对象和关联对象应该支持的行为，这两种对象的典型例子是list和dict。 摘自：《Python源码剖析》 — 陈儒
不能支持数值对象操作的其他对象分别处理，但是最终都是由PyLong_FromString来处理。
PyLong_FromString
/* Parses an int from a bytestring. Leading and trailing whitespace will be
* ignored.
*
* If successful, a PyLong object will be returned and 'pend' will be pointing
* to the first unused byte unless it's NULL.
*
* If unsuccessful, NULL will be returned.
*/
PyObject *
PyLong_FromString(const char *str, char **pend, int base)
{
int sign = 1, error_if_nonzero = 0;
const char *start, *orig_str = str;
PyLongObject *z = NULL;
PyObject *strobj;
Py_ssize_t slen;
if ((base != 0 && base < 2) || base > 36) {
PyErr_SetString(PyExc_ValueError,
"int() arg 2 must be >= 2 and <= 36");
return NULL;
}
while (*str != '\0' && Py_ISSPACE(Py_CHARMASK(*str))) {
str++;
}
if (*str == '+') {
++str;
}
else if (*str == '-') {
++str;
sign = -1;
}
if (base == 0) {
if (str[0] != '0') {
base = 10;
}
else if (str[1] == 'x' || str[1] == 'X') {
base = 16;
}
else if (str[1] == 'o' || str[1] == 'O') {
base = 8;
}
else if (str[1] == 'b' || str[1] == 'B') {
base = 2;
}
else {
/* "old" (C-style) octal literal, now invalid.
it might still be zero though */
error_if_nonzero = 1;
base = 10;
}
}
if (str[0] == '0' &&
((base == 16 && (str[1] == 'x' || str[1] == 'X')) ||
(base == 8 && (str[1] == 'o' || str[1] == 'O')) ||
(base == 2 && (str[1] == 'b' || str[1] == 'B')))) {
str += 2;
/* One underscore allowed here. */
if (*str == '_') {
++str;
}
}
if (str[0] == '_') {
/* May not start with underscores. */
goto onError;
}
start = str;
if ((base & (base - 1)) == 0) {
int res = long_from_binary_base(&str, base, &z);
if (res < 0) {
/* Syntax error. */
goto onError;
}
}
else {
/***
Binary bases can be converted in time linear in the number of digits, because
Python's representation base is binary. Other bases (including decimal!) use
the simple quadratic-time algorithm below, complicated by some speed tricks.
First some math: the largest integer that can be expressed in N base-B digits
is B**N-1. Consequently, if we have an N-digit input in base B, the worst-
case number of Python digits needed to hold it is the smallest integer n s.t.
BASE**n-1 >= B**N-1 [or, adding 1 to both sides]
BASE**n >= B**N [taking logs to base BASE]
n >= log(B**N)/log(BASE) = N * log(B)/log(BASE)
The static array log_base_BASE[base] == log(base)/log(BASE) so we can compute
this quickly. A Python int with that much space is reserved near the start,
and the result is computed into it.
The input string is actually treated as being in base base**i (i.e., i digits
are processed at a time), where two more static arrays hold:
convwidth_base[base] = the largest integer i such that base**i <= BASE
convmultmax_base[base] = base ** convwidth_base[base]
The first of these is the largest i such that i consecutive input digits
must fit in a single Python digit. The second is effectively the input
base we're really using.
Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base
convmultmax_base[base], the result is "simply"
(((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1
where B = convmultmax_base[base].
Error analysis: as above, the number of Python digits `n` needed is worst-
case
n >= N * log(B)/log(BASE)
where `N` is the number of input digits in base `B`. This is computed via
size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
below. Two numeric concerns are how much space this can waste, and whether
the computed result can be too small. To be concrete, assume BASE = 2**15,
which is the default (and it's unlikely anyone changes that).
Waste isn't a problem: provided the first input digit isn't 0, the difference
between the worst-case input with N digits and the smallest input with N
digits is about a factor of B, but B is small compared to BASE so at most
one allocated Python digit can remain unused on that count. If
N*log(B)/log(BASE) is mathematically an exact integer, then truncating that
and adding 1 returns a result 1 larger than necessary. However, that can't
happen: whenever B is a power of 2, long_from_binary_base() is called
instead, and it's impossible for B**i to be an integer power of 2**15 when
B is not a power of 2 (i.e., it's impossible for N*log(B)/log(BASE) to be
an exact integer when B is not a power of 2, since B**i has a prime factor
other than 2 in that case, but (2**15)**j's only prime factor is 2).
The computed result can be too small if the true value of N*log(B)/log(BASE)
is a little bit larger than an exact integer, but due to roundoff errors (in
computing log(B), log(BASE), their quotient, and/or multiplying that by N)
yields a numeric result a little less than that integer. Unfortunately, "how
close can a transcendental function get to an integer over some range?"
questions are generally theoretically intractable. Computer analysis via
continued fractions is practical: expand log(B)/log(BASE) via continued
fractions, giving a sequence i/j of "the best" rational approximations. Then
j*log(B)/log(BASE) is approximately equal to (the integer) i. This shows that
we can get very close to being in trouble, but very rarely. For example,
76573 is a denominator in one of the continued-fraction approximations to
log(10)/log(2**15), and indeed:
>>> log(10)/log(2**15)*76573
16958.000000654003
is very close to an integer. If we were working with IEEE single-precision,
rounding errors could kill us. Finding worst cases in IEEE double-precision
requires better-than-double-precision log() functions, and Tim didn't bother.
Instead the code checks to see whether the allocated space is enough as each
new Python digit is added, and copies the whole thing to a larger int if not.
This should happen extremely rarely, and in fact I don't have a test case
that triggers it(!). Instead the code was tested by artificially allocating
just 1 digit at the start, so that the copying code was exercised for every
digit beyond the first.
***/
twodigits c; /* current input character */
Py_ssize_t size_z;
int digits = 0;
int i;
int convwidth;
twodigits convmultmax, convmult;
digit *pz, *pzstop;
const char *scan, *lastdigit;
char prev = 0;
static double log_base_BASE[37] = {0.0e0,};
static int convwidth_base[37] = {0,};
static twodigits convmultmax_base[37] = {0,};
if (log_base_BASE[base] == 0.0) {
twodigits convmax = base;
int i = 1;
log_base_BASE[base] = (log((double)base) /
log((double)PyLong_BASE));
for (;;) {
twodigits next = convmax * base;
if (next > PyLong_BASE) {
break;
}
convmax = next;
++i;
}
convmultmax_base[base] = convmax;
assert(i > 0);
convwidth_base[base] = i;
}
/* Find length of the string of numeric characters. */
scan = str;
lastdigit = str;
while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base || *scan == '_') {
if (*scan == '_') {
if (prev == '_') {
/* Only one underscore allowed. */
str = lastdigit + 1;
goto onError;
}
}
else {
++digits;
lastdigit = scan;
}
prev = *scan;
++scan;
}
if (prev == '_') {
/* Trailing underscore not allowed. */
/* Set error pointer to first underscore. */
str = lastdigit + 1;
goto onError;
}
/* Create an int object that can contain the largest possible
* integer with this base and length. Note that there's no
* need to initialize z->ob_digit -- no slot is read up before
* being stored into.
*/
size_z = (Py_ssize_t)(digits * log_base_BASE[base]) + 1;
/* Uncomment next line to test exceedingly rare copy code */
/* size_z = 1; */
assert(size_z > 0);
z = _PyLong_New(size_z);
if (z == NULL) {
return NULL;
}
Py_SIZE(z) = 0;
/* `convwidth` consecutive input digits are treated as a single
* digit in base `convmultmax`.
*/
convwidth = convwidth_base[base];
convmultmax = convmultmax_base[base];
/* Work ;-) */
while (str < scan) {
if (*str == '_') {
str++;
continue;
}
/* grab up to convwidth digits from the input string */
c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)];
for (i = 1; i < convwidth && str != scan; ++str) {
if (*str == '_') {
continue;
}
i++;
c = (twodigits)(c * base +
(int)_PyLong_DigitValue[Py_CHARMASK(*str)]);
assert(c < PyLong_BASE);
}
convmult = convmultmax;
/* Calculate the shift only if we couldn't get
* convwidth digits.
*/
if (i != convwidth) {
convmult = base;
for ( ; i > 1; --i) {
convmult *= base;
}
}
/* Multiply z by convmult, and add c. */
pz = z->ob_digit;
pzstop = pz + Py_SIZE(z);
for (; pz < pzstop; ++pz) {
c += (twodigits)*pz * convmult;
*pz = (digit)(c & PyLong_MASK);
c >>= PyLong_SHIFT;
}
/* carry off the current end? */
if (c) {
assert(c < PyLong_BASE);
if (Py_SIZE(z) < size_z) {
*pz = (digit)c;
++Py_SIZE(z);
}
else {
PyLongObject *tmp;
/* Extremely rare. Get more space. */
assert(Py_SIZE(z) == size_z);
tmp = _PyLong_New(size_z + 1);
if (tmp == NULL) {
Py_DECREF(z);
return NULL;
}
memcpy(tmp->ob_digit,
z->ob_digit,
sizeof(digit) * size_z);
Py_DECREF(z);
z = tmp;
z->ob_digit[size_z] = (digit)c;
++size_z;
}
}
}
}
if (z == NULL) {
return NULL;
}
if (error_if_nonzero) {
/* reset the base to 0, else the exception message
doesn't make too much sense */
base = 0;
if (Py_SIZE(z) != 0) {
goto onError;
}
/* there might still be other problems, therefore base
remains zero here for the same reason */
}
if (str == start) {
goto onError;
}
if (sign < 0) {
Py_SIZE(z) = -(Py_SIZE(z));
}
while (*str && Py_ISSPACE(Py_CHARMASK(*str))) {
str++;
}
if (*str != '\0') {
goto onError;
}
long_normalize(z);
z = maybe_small_long(z);
if (z == NULL) {
return NULL;
}
if (pend != NULL) {
*pend = (char *)str;
}
return (PyObject *) z;
onError:
if (pend != NULL) {
*pend = (char *)str;
}
Py_XDECREF(z);
slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;
strobj = PyUnicode_FromStringAndSize(orig_str, slen);
if (strobj == NULL) {
return NULL;
}
PyErr_Format(PyExc_ValueError,
"invalid literal for int() with base %d: %.200R",
base, strobj);
Py_DECREF(strobj);
return NULL;
}
0x02 整数对象的数值操作
前面提到的数值对象的类型中tp_as_number指向对该对象的数值操作，在Objects/longobject.c的PyLong_Type中定义着：
PyTypeObject PyLong_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"int", /* tp_name */
...
&long_as_number, /* tp_as_number */
...
};
long_as_number也在Objects/longobject.c中定义着：
static PyNumberMethods long_as_number = {
(binaryfunc)long_add, /*nb_add*/
(binaryfunc)long_sub, /*nb_subtract*/
(binaryfunc)long_mul, /*nb_multiply*/
long_mod, /*nb_remainder*/
long_divmod, /*nb_divmod*/
long_pow, /*nb_power*/
(unaryfunc)long_neg, /*nb_negative*/
(unaryfunc)long_long, /*tp_positive*/
(unaryfunc)long_abs, /*tp_absolute*/
(inquiry)long_bool, /*tp_bool*/
(unaryfunc)long_invert, /*nb_invert*/
long_lshift, /*nb_lshift*/
(binaryfunc)long_rshift, /*nb_rshift*/
long_and, /*nb_and*/
long_xor, /*nb_xor*/
long_or, /*nb_or*/
long_long, /*nb_int*/
0, /*nb_reserved*/
long_float, /*nb_float*/
0, /* nb_inplace_add */
0, /* nb_inplace_subtract */
0, /* nb_inplace_multiply */
0, /* nb_inplace_remainder */
0, /* nb_inplace_power */
0, /* nb_inplace_lshift */
0, /* nb_inplace_rshift */
0, /* nb_inplace_and */
0, /* nb_inplace_xor */
0, /* nb_inplace_or */
long_div, /* nb_floor_divide */
long_true_divide, /* nb_true_divide */
0, /* nb_inplace_floor_divide */
0, /* nb_inplace_true_divide */
long_long, /* nb_index */
};
整数加法
static PyObject *
long_add(PyLongObject *a, PyLongObject *b)
{
PyLongObject *z;
CHECK_BINOP(a, b);
if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b));
}
if (Py_SIZE(a) < 0) {
if (Py_SIZE(b) < 0) {
z = x_add(a, b);
if (z != NULL) {
/* x_add received at least one multiple-digit int,
and thus z must be a multiple-digit int.
That also means z is not an element of
small_ints, so negating it in-place is safe. */
assert(Py_REFCNT(z) == 1);
Py_SIZE(z) = -(Py_SIZE(z));
}
}
else
z = x_sub(b, a);
}
else {
if (Py_SIZE(b) < 0)
z = x_sub(a, b);
else
z = x_add(a, b);
}
return (PyObject *)z;
}
对于都小于一个digit大小的两数相加，直接进行简单加法计算。整数过大，就分别由x_add和x_sub两个函数来计算。
/* Add the absolute values of two integers. */
static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
PyLongObject *z;
Py_ssize_t i;
digit carry = 0;
/* Ensure a is the larger of the two: */
if (size_a < size_b) {
{ PyLongObject *temp = a; a = b; b = temp; }
{ Py_ssize_t size_temp = size_a;
size_a = size_b;
size_b = size_temp; }
}
z = _PyLong_New(size_a+1);
if (z == NULL)
return NULL;
for (i = 0; i < size_b; ++i) {
carry += a->ob_digit[i] + b->ob_digit[i];
z->ob_digit[i] = carry & PyLong_MASK;
carry >>= PyLong_SHIFT;
}
for (; i < size_a; ++i) {
carry += a->ob_digit[i];
z->ob_digit[i] = carry & PyLong_MASK;
carry >>= PyLong_SHIFT;
}
z->ob_digit[i] = carry;
return long_normalize(z);
}
x_add进行的PyLongObject对象的加法运算也是比较简单的。先申请size_a+1（保证a > b）大小的内存空间（防止进位溢出），从ob_digit的低位开始按位相加，carry做进位处理，另外保证ob_digit[i]中的数值在[0, PyLong_MASK]之间，然后处理a对象的高位数字，最后利用long_normalize函数调整ob_size大小，保证了ob_digit[abs(ob_size)-1]不为零。
/* Normalize (remove leading zeros from) an int object.
Doesn't attempt to free the storage--in most cases, due to the nature
of the algorithms used, this could save at most be one word anyway. */
static PyLongObject *
long_normalize(PyLongObject *v)
{
Py_ssize_t j = Py_ABS(Py_SIZE(v));
Py_ssize_t i = j;
while (i > 0 && v->ob_digit[i-1] == 0)
--i;
if (i != j)
Py_SIZE(v) = (Py_SIZE(v) < 0) ? -(i) : i;
return v;
}
整数乘法
static PyObject *
long_mul(PyLongObject *a, PyLongObject *b)
{
PyLongObject *z;
CHECK_BINOP(a, b);
/* fast path for single-digit multiplication */
if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
return PyLong_FromLongLong((long long)v);
}
z = k_mul(a, b);
/* Negate if exactly one of the inputs is negative. */
if (((Py_SIZE(a) ^ Py_SIZE(b)) < 0) && z) {
_PyLong_Negate(&z);
if (z == NULL)
return NULL;
}
return (PyObject *)z;
}
对于都小于一个digit大小的两数乘积，直接进行简单相乘，而后用PyLong_FromLongLong((long long)v)进行调整。整数过大则使用k_mul函数计算，k_mul函数是Karatsuba multiplication算法的实现，一种快速相乘算法。
延伸阅读
- PEP 237 -- Unifying Long Integers and Integers
- Why is Python 3 is considerably slower than Python 2?
PyLongObject在Python内部是用一个digit类型的柔性数组ob_digit来存储值的。柔性数组（Flexible array）是C99引入的一个feature，比起digit *ob_digit更方便分配内存和释放内存，且ob_digit不额外占用空间，节约指针变量所占的内存大小。
这里对ob_digit类型解释疑有误。若为flexible array，则声明时大小应为空，即digit ob_digit[]，但此处为digit ob_digit[1]，不应该为flexible array。
事实上，这里应该只是单纯声明了一个大小为1的array，固定了这个“指针”的位置，而后在申请空间时，使用了如下方式：
result = PyObject_MALLOC(offsetof(PyLongObject, ob_digit) + size*sizeof(digit));
这里申请的实际内存大小为 HEAD + size*sizeof(digit))，也就是说，在ob_digit后面申请了足够的内存，而这样ob_digit就成了一个单纯的array，其大小是固定的，且通过下标访问也不会越界。
参考：
[1] Flexible array member - wikipedia
[2] Why use array size 1 instead of pointer? - stackoverflow
