LiuWen's Blogs
0%

[python源码分析] 4.不溢出的整数int

Posted on Edited on In

整数溢出#

c语言中，32位机器的int 长度为32 位，表示的范围: [-2147483648, 2147483647], 超过这个范围就会溢出了。 由于整数溢出现象的存在，程序员需要结合业务场景，谨慎选择数据类型。

而在python中，就没有整数溢出的烦恼。 Python 可以计算十的一百次方，这在其他语言是不可想象的： 

1
2
>>> 10 ** 100
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
也许我们过去都接触过 c语言大整数的实现，接下来我们来看看python如何实现大整数。

int 对象#

int 对象在 Include/longobject.h 头文件中定义： 

1
typedef struct _longobject PyLongObject; /* Revealed in longintrepr.h */
顺着注释去 Include/longintrepr.h 中，找到了实现 int 对象的结构体： 
1
2
3
4
struct _longobject {
    PyObject_VAR_HEAD        /*可变长对象都具有的公共头部*/
    digit ob_digit[1];     /*这里存储int的整数值*/
};
在 Include/longintrepr.h 头文件，可以找到 digit 字段的定义： 
1
2
3
4
5
6
7
#if PYLONG_BITS_IN_DIGIT == 30
typedef uint32_t digit;
// ...
#elif PYLONG_BITS_IN_DIGIT == 15
typedef unsigned short digit;
// ...
#endif
由此可知digit 就是一个 C 语言整数，因此 int 对象是通过整数数组来实现大整数的。至于整数数组用什么整数类型来实现， Python 提供了两个版本，一个是 32 位的 uint32_t ，一个是 16 位的 unsigned short ，编译 Python 解析器时可以 通过宏定义指定选用的版本。

Python 作者为什么要这样设计呢？这主要是 出于内存方面的考量：对于范围不大的整数，用 16 位整数表示即可，用 32 位就有点浪费。

整数对象| 对象大小（16位）| 对象大小（32位） -:-|-:-|-:- 1|24 + 2 * 1 = 26|24 + 4 * 1 = 28 1000000 |24 + 2 * 2 = 28|24 + 4 * 1 = 28 10000000000 |24 + 2 * 3 = 30|24 + 4 * 2 = 32

Q：ob_digit 数组长度可能大于1，而为什么在结构体定义中， ob_digit 数组长度却固定为 1？#

由于 C 语言中 数组长度不是类型信息，我们可以 根据实际需要为 ob_digit 数组分配足够的内存，并将其当成长度为 n 的数组操作。这也是 C 语言中一个常用的编程技巧。长度信息在 PyVarObject(PyVarObject比PyObjcet多了个ob_size字段，详细定义可以看[python源码分析] 1.对象)中的ob_size中。

实现大整数#

整数分为 正数 、 负数 和 零 ， Python 规定不同整数在 int 对象中的存储方式，要点可以总结为 3 条：

整数 绝对值 根据实际情况分为若干部分，保存于 ob_digit 数组中； ob_digit 数组长度 保存于 ob_size 字段，对于 负整数 的情况，ob_size 为负（这里可以说就很精妙了）； 整数 零 以 ob_size 等于 0 来表示，ob_digit 数组为空； 接下来，我们以 5 个典型的例子详细介绍这几条规则：

  1. 对于整数 0 ， ob_size 字段等于 0 ， ob_digit 数组为空，无需分配。
  2. 对于整数 10 ，其绝对值保存于 ob_digit 数组中，数组长度为 1 ， ob_size 字段等于 1 。
  3. 对于整数 -10 ，其绝对值同样保存于 ob_digit 数组中，但由于 -10 为负数， ob_size 字段等于 -1 。
  4. 对于整数 1073741824 ( 2 的 30 次方)，由于 Python 只使用 32 整数的后 30 位，因此 需要另一个整数才能存储，整数数组长度为 2 。绝对值这样计算：\(2^{30}*1+2^0*0=10737418242\)
  5. 对于整数 -4294967297 (负的 2 的 32 次方加 1 )，同样要长度为 2 的 ob_digit 数组，但 ob_size 字段为负。绝对值这样计算：\(2^{30}*4+2^0*1=42949672972\)

为什么 Python 只用 ob_digit 数组整数的后 30 位？#

这跟 加法进位有关。如果全部 32 位都用来保存绝对值，那么为了保证加法不溢出(产生进位)，需要先强制转换成 64 位类型后在进行计算。但 牺牲最高 1 位后，加法运算便不用担心进位溢出了。那么，为什么 Python 牺牲最高 2 位呢？应该是 为了和 16 位整数方案统一起来：如果选用 16 位整数作为数组， Python 则只使用其中 15 位。

小整数静态对象池#

小整数对象池在 Objects/longobject.c 中实现，关键代码如下： 

1
2
3
4
5
6
7
8
9
/*小整数池的范围通过宏来定义的, 默认是-5-257,我们可以通过修改此处的宏来调整小整数池的大小, 但是需要对python进行重新编译*/
#ifndef NSMALLPOSINTS
#define NSMALLPOSINTS           257   /*该宏规定了对象池 正数个数 (从 0 开始，包括 0 )，默认 257 个*/
#endif
#ifndef NSMALLNEGINTS
#define NSMALLNEGINTS           5     /*该宏规定了对象池 负数个数 ，默认 5 个*/
#endif

static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];  /*一个整数对象数组，保存预先创建好的小整数对象*/

如果在[-5, 257)范围内，会直接返回存于small_ints的对象，所以小整数只会存在一个实例： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// longobject.c
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;

至于为什么选择静态缓存从 -5 到 256 之间的小整数，主要是出于某种 权衡 ：这个范围内的整数使用 频率很高 ，而缓存这些小整数的 内存开销相对可控 。很多程序开发场景都没有固定的正确答案，需要根据实际情况平衡利弊。

理解了静态对象池，如下现象就很好理解了： 

1
2
3
4
5
6
7
8
9
>>> a = 1 + 0
>>> b = 1 * 1
>>> id(a), id(b)
(4408209536, 4408209536)

>>> c = 1000 + 0
>>> d = 1000 * 1
>>> id(c), id(d)
(4410298224, 4410298160)

由于整数对象是 不可变对象 ，任何整数运算结果都以新对象返回，而对象创建销毁开销却不小。为了优化整数对象的性能， Python 在启动时将使用 频率较高 的小整数预先创建好，这就是 小整数缓存池 。默认情况下，小整数缓存池缓存 从 -5 到 256 之间的整数。

数学运算#

根据我们在 PyTypeObject 中学到的知识，对象的行为由对象的 类型 决定。因此，整数对象 数学运算的秘密藏在整数类型对象中。在 Objects/longobject.c 中找到整数类型对象( PyLong_Type )，其定义如下所示： 
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
PyTypeObject PyLong_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "int",                                      /* tp_name */
    offsetof(PyLongObject, ob_digit),           /* tp_basicsize */
    sizeof(digit),                              /* tp_itemsize */
    0,                                          /* tp_dealloc */
    0,                                          /* tp_vectorcall_offset */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_as_async */
    long_to_decimal_string,                     /* tp_repr */
    &long_as_number,                            /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    (hashfunc)long_hash,                        /* tp_hash */
    0,                                          /* tp_call */
    0,                                          /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
        Py_TPFLAGS_LONG_SUBCLASS,               /* tp_flags */
    long_doc,                                   /* tp_doc */
    0,                                          /* tp_traverse */
    0,                                          /* tp_clear */
    long_richcompare,                           /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    0,                                          /* tp_iter */
    0,                                          /* tp_iternext */
    long_methods,                               /* tp_methods */
    0,                                          /* tp_members */
    long_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 */
    long_new,                                   /* tp_new */
    PyObject_Del,                               /* tp_free */
};
类型对象中， tp_as_number 是一个关键字段。该字段指向一个 PyNumberMethods 结构体，结构体保存了 各种数学运算的 函数指针 ： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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*/
    // ...
};
下图展示了 整数对象 、 整数类型对象 以及 整数数学运算处理函数 之间的关系：

加法#

如何为一个由数组表示的大整数实现加法？问题答案得在 long_add 函数中找，该函数是整数对象 加法处理函数 。我们再接再厉，扒开 long_add 函数看个究竟(同样位于 Objects/longobject.c )： 

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
static PyObject *
long_add(PyLongObject *a, PyLongObject *b)
{
  /*定义变量 z 用于临时保存计算结果*/
    PyLongObject *z;  

    CHECK_BINOP(a, b);

    /*
    如果参与运算的整数对象底层数组长度均不超过 1 ，直接用 MEDIUM_VALUE 宏将整数对象转化成 C 整数类型进行运算，
    性能损耗极小。满足这个条件的整数范围在 -1073741823~1073741823 之间，足以覆盖程序运行时的绝大部分运算场景
    */

    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) {
          /*如果两个整数均为 负数 ，调用 x_add 计算两者绝对值之和，再将结果符号设置为负( 16 行处)*/
            z = x_add(a, b);
            if (z != NULL) {
                assert(Py_REFCNT(z) == 1);
                Py_SIZE(z) = -(Py_SIZE(z));
            }
        }
        /*如果 a 为负数， b 为正数，调用 x_sub 计算 b 和 a 的绝对值之差即为最终结果*/
        else
            z = x_sub(b, a);
    }
    else {
        if (Py_SIZE(b) < 0)
            z = x_sub(a, b);
        else
        /*如果两个整数均为正数，调用 x_add 计算两个绝对值之和即为最终结果*/
            z = x_add(a, b);
    }
    return (PyObject *)z;
}
### x_add x_add 用于计算两个整数对象绝对值之和，源码同样位于 Objects/longobject.c ： 
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
static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
 /*取ob_size的绝对值*/
    Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));


    /*用变量z 临时存储计算结果*/
    PyLongObject *z;
    Py_ssize_t i;
    /*临时进位*/
    digit carry = 0;

    /* Ensure a is the larger of the two: */
    if (size_a < size_b) {
     /*如果 a 数组长度比较小，将 a 、 b 交换，数组长度较大的那个在前面*/
        { PyLongObject *temp = a; a = b; b = temp; }
        { Py_ssize_t size_temp = size_a;
            size_a = size_b;
            size_b = size_temp; }
    }
    /*创建新整数对象，用于保存计算结果（注意到长度必须比 a 和 b 都大一，因为可能有进位）*/
    z = _PyLong_New(size_a+1);

    if (z == NULL)
        return NULL;
    /*遍历 b 底层数组，与 a 对应部分相加并保存到 z 中，需要特别注意进位计算*/
    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;
    }
    /*遍历 a 底层数组剩余部分，与进位相加后保存到 z 中，同样需要特别注意进位计算*/
    for (; i < size_a; ++i) {
        carry += a->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    /*将进位写入 z 底层数组最高位单元中*/
    z->ob_digit[i] = carry;
    /*去除计算结果 z 底层数组中前面多余的零，因为最后的进位可能为零*/
    return long_normalize(z);
}

reference#

  1. Python 源码深度剖析/07 int 对象，永不溢出的整数
  2. Python 源码深度剖析/08 int 源码解析：如何实现大整数运算？
  3. Python3源码—整数对象