int部分源码解析(cpython)

2021-06-18

2021-06-17

本文字数: 1.4k 阅读时长: 6 分钟

阅读次数次

Python中有int对象，但是在cPython中可是没有这个对象的
cPython中只有PyLongObject

PyLongObject

struct _longobject {
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;    
    Py_ssize_t ob_size; /* Number of items in variable part */ 
    digit ob_digit[1];
};

1.ob_refcnt 为引用计数
2.ob_type 为一个指针，指向了一个类型
3.ob_size 为一个整数，表示ob_digit的长度
4.ob_digit 为一个数组，可以当成一个指针，存储了具体的数值

整数存储方式

为什么一个整数要那么复杂的表示方式？Python的整数是不会溢出的，
他可以表示任意大的数据，因为使用简单的 c 语言是做不到的，
所以定义了一个那么复杂的东西。

普通进位法

按照digit数组位数
digit[0]*1 + digit[1]*10 + digit[2]*100 .....
这样存储
``` 

### 负数存储
也是放到ob_size中，如果ob_size为-1那么代表ob_digit长度为1，但是这个数为负数

### 部分源码
#### 创建int
小于C中long类型大小的数值基于PyLong_FromLong创建，大于用PyLong_FromString
- 步骤
    - 1.检查如果是小整数，则直接返回缓冲池的小整数对象，在python3中缓冲池范围是[-5, 257)
    - 2.将数值和正负数的标识分开
    - 3.对于小于PyLong_SHIFT位的数进入快速通道，PyLong_SHIFT的值基于当前系统中定义指针的大小确定
    （指针在32位中size为4，64位中为8，因此例如32位平台下32768以下的数字都可以进入该通道）
    - 4.对于指针大小为4字节的情况（例如32位系统），申请对象空间
    - 5.对于较大的数值，需要获取位数，然后申请对应大小的long对象
    
- [源码](https://github.com/python/cpython/blob/main/Objects/longobject.c)

PyObject *
PyLong_FromLong(long ival)
{
PyLongObject v;
// abs_ival中存放绝对值数值
unsigned long abs_ival;
unsigned long t; / unsigned so >> doesn’t propagate sign bit */
int ndigits = 0;
// 数值标记：正数(1)，负数(-1)，零(0)
int sign;
// 检查如果是小整数，则直接返回缓冲池的小整数对象，python3缓冲池范围是[-5, 257)
CHECK_SMALL_INT(ival);
// 将数值和正负数的标识分开
if (ival < 0) {
abs_ival = 0U-(unsigned long)ival;
sign = -1;
}
else {
abs_ival = (unsigned long)ival;
sign = ival == 0 ? 0 : 1;
}

// 对于小于PyLong_SHIFT位的数进入快速通道，PyLong_SHIFT的值基于当前系统中定义指针的大小确定
// （指针在32位中size为4，64位中为8，因此例如32位平台下32768以下的数字都可以进入该通道）
if (!(abs_ival >> PyLong_SHIFT)) {
    // 创建一个数值指向区域size为1*sizeof(digit)的long对象
    v = _PyLong_New(1);
    if (v) {
        // 可以看出ob_size用来标识是正数、负数还是0
        Py_SIZE(v) = sign;
        // ob_digit[0]里存入的是无符号的数值
        v->ob_digit[0] = Py_SAFE_DOWNCAST(
            abs_ival, unsigned long, digit);
    }
    return (PyObject*)v;
}

// 对于指针大小为4字节的情况（例如32位系统），申请对象空间的方式
#if PyLong_SHIFT==15
/* 2 digits /
if (!(abs_ival >> 2PyLong_SHIFT)) {
v = _PyLong_New(2);
if (v) {
Py_SIZE(v) = 2sign;
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

// 对于较大的数值，需要获取位数，然后申请对应大小的long对象
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;

}

1	#### 小整数缓冲池

// #define NSMALLPOSINTS 257
// #define NSMALLNEGINTS 5
static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];

// 获取小整数对象
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;
}

对于小整数使用较多的场景，我们可以通过修改小整数的缓冲池范围来进行优化

#### long_add
由于python中的int属于不可变类型数据，因此在进行加法运算时，
会创建一个新的int对象来存储计算的结果值，并且由于int中数据的
存储是基于数据，因此在计算时实际上模拟了从低位开始逐位相加
算的方式来进行运算，而通过这种存储和计算方式

- long_add

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) {
            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;

}

- x_add

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;

// 如果a比b小，就交换两个数，以保证a是大的那个数
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; }
}
// 以最大的那个值的size+1为新创建的long对象大小
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;
}
// 高位只剩下a的值，直接将a的值填充
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;
// long_normalize将数值前面的0删除（并没有真正删除释放，而是改变其允许指向数值的范围大小）
return long_normalize(z);

}
```

python源码解析

PyLongObject

整数存储方式

普通进位法