第2篇:CPython实现原理:整数对象(前篇)

在CPython中的整数对象的堆内存分配并非在即时对某个需要使用的整数分配内存的，因为这样势必对CPython的内存利用率非常底下。而是有一套非常高效的内存管理方案就是针对整数对象-缓冲池机制（高效吗，得跟什么参照物对比？那是Python编程技术圈很官腔的褒赞而已）。我们知道在CPython的内存管理模型中，每个内建对象都有自己独有的对象池机制。而本篇我们恰好讲解整数对象缓存池。

首先针对单个整数PyLongObject对象的表示法，CPython3.9有明确的定义

....
/* 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
    digit ob_digit[1];
};
....
typedef struct _longobject PyLongObject;

其最终形式，等价如下

....
struct _longobject {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
    digit ob_digit[1];
};
....
typedef struct _longobject PyLongObject;

我们从源代码的注释中得到一些关键的信息,整数的绝对值等于如下表达式

SUM（for i = 0 through abs（ob_size）-1）ob_digit [i] * 2 **（SHIFT * i）

如果上面的表达式，我们知道ob_size的绝对值是控制ob_digit数组的长度，而SHIFT有一个宏常量PyLong_SHIFT定义(下文会提到)。

  • 负数用ob_size <0表示；
  • 0由ob_size == 0表示
  • 以标准化数字ob_digit [abs(ob_size)-1]（最高有效数字）永远不会为0。 而且，在所有情况下，对于所有有效的i，0 <= ob_digit [i] <=掩码
  • 内存分配函数负责分配额外的内存，因此ob_digit [0]到ob_digit [abs(ob_size)-1]实际上可用的有效负载部分。

综上所述，对于大整数在CPython3.x中的有效负载的存储形式如下图


而对于整数对象的存储方式，CPython3.x中就规定使用2**PyLong_SHIFT进制的字符串来表示大整数，而PyLong_SHIFT的定义在Include/longintrepr.h中找到，PyLong_SHIFT的可能的默认值是30或15,分别表示

  • 把30位大小的数值存储在uint32_t类型的ob_digit数组中
  • 把15位大小的数值存储在uint32_t类型的ob_digit数组中

#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

那么CPython3.x究竟如何实现上面提到的存储整数的算法呢？这个可以查看Objects/longobject.c源文件的PyLong_FromLong函数，从下面的代码我们知道，在PyLong_FromLong函数中，CPython还会调用IS_SMALL_INT这个宏函数对传来C类型的长整形区分是小整数还是大整数，关于小整数的话题，后文再展开。

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;

    if (IS_SMALL_INT(ival)) {
        return get_small_int((sdigit)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_SET_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_SET_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_SET_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;
}

整数对象的初始化

整数对象的创建，我们在前一篇已经说过创建一个PyLongObject需要引用与该类型匹配的PyLong_Type实例，我们查看一下PyLong_Type实例的初始化代码,它位于Objects/longobject.c源文件，

PyTypeObject PyLong_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "int",                                      /* tp_name */
    offsetof(PyLongObject, ob_digit),           /* tp_basicsize */
    sizeof(digit),                              /* tp_itemsize */
    ....
    long_to_decimal_string,                     /* tp_repr */
    &long_as_number,                            /* tp_as_number */
    ....
    (hashfunc)long_hash,                        /* tp_hash */
    ....
    PyObject_GenericGetAttr,                    /* tp_getattro */
    ....
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
        Py_TPFLAGS_LONG_SUBCLASS,               /* tp_flags */
    long_doc,                                   /* tp_doc */
    ....
    long_richcompare,                           /* tp_richcompare */
    ....
    long_methods,                               /* tp_methods */
    0,                                          /* tp_members */
    long_getset,                                /* tp_getset */
    ....
    long_new,                                   /* tp_new */
    PyObject_Del,                               /* tp_free */
};

注意PyLong对象的实例化需要调用PyLong_Type实例的tp_new字段相关的参数，它是一个long_new的函数指针，那么long_new函数的具体定义

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 = {NULL, _keywords, "int", 0};
    PyObject *argsbuf[2];
    PyObject * const *fastargs;
    Py_ssize_t nargs = PyTuple_GET_SIZE(args);
    Py_ssize_t noptargs = nargs + (kwargs ? PyDict_GET_SIZE(kwargs) : 0) - 0;
    PyObject *x = NULL;
    PyObject *obase = NULL;

    fastargs = _PyArg_UnpackKeywords(_PyTuple_CAST(args)->ob_item, nargs, kwargs, NULL, &_parser, 0, 2, 0, argsbuf);
    if (!fastargs) {
        goto exit;
    }
    if (nargs < 1) {
        goto skip_optional_posonly;
    }
    noptargs--;
    x = fastargs[0];
skip_optional_posonly:
    if (!noptargs) {
        goto skip_optional_pos;
    }
    obase = fastargs[1];
skip_optional_pos:
    return_value = long_new_impl(type, x, obase);

exit:
    return return_value;
}

而long_new函数其实最终是调用long_new_impl函数，其具体定义在源文件的Objects/longobject.c源文件，

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 */
   //当x为NULL，底数非NULL返回,以0为参数调用PyLong_FromLong函数
    if (x == NULL) {
        if (obase != NULL) {
            PyErr_SetString(PyExc_TypeError,
                            "int() missing string argument");
            return NULL;
        }
        return PyLong_FromLong(0L);
    }
    //当x非NULL，obase为NULL,调用PyNumber_Long函数
    if (obase == NULL)
        return PyNumber_Long(x);

    base = PyNumber_AsSsize_t(obase, NULL);
    if (base == -1 && PyErr_Occurred())
        return NULL;
    //base只能在属于0或区间[2,36]等整数
    if ((base != 0 && base < 2) || base > 36) {
        PyErr_SetString(PyExc_ValueError,
                        "int() base must be >= 2 and <= 36, or 0");
        return NULL;
    }

    if (PyUnicode_Check(x))
        return PyLong_FromUnicodeObject(x, (int)base);
    else if (PyByteArray_Check(x) || PyBytes_Check(x)) {
        const 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;
    }
}

当使用Python层面的内置类型class int(object)在实例化int(),事实上会调用到C底层的函数接口,会经历如下过程：
int(...) → PyObject → PyLong_Type → long_new → long_new_impl

C底层long_new_impl函数很大程度上反映了Python层面的类int在实例化时的行为。因为针对参数x的不同情况，long_new_impl根据相应的条件去调用PyLong_前缀的函数族中对应的函数来实例化PyLongObject

例如将数字或字符串转换为整数，如果没有参数，则返回0。 如果x是数字，则返回x._int_()。 对于传入的位置参数是浮点数字，这会截断为零。

如果x不是数字或给出base，则x必须是字符串，字节或字节数组，表示给base中的整数文字。 文字可以以“ +”或“-”开头，并用空格包围。 base默认为10。有效base为0和2-36。base为0表示将字符串的基数解释为整数文字。

备注:我这里并没打算罗列所有PyLong_函数族

小型整数

在Python中就引入了小型整数对象池(Small Integer Object Pool),那到底多小的整数为小型整数呢？。还记得，上文我们提到PyLong_FromLong函数时，有提到IS_SMALL_INT的宏函数吗？该函数是用于判断当前传入PyLong_FromLong函数的参数是否为小型整数。

是什么原因导致，CPython底层需要区分小型整数(Small Integer)和大型整数(Big Integer)呢？什么是小型整数？顾名思义就是数值较小的整数。比如1,7,47,52等。我们Python编程中,和小型整数打交道的最多。在CPython中一切对象都是堆中对应的内存数据实体，试想一下我们不太可能为某段整数区间内频繁使用的整数分配N次堆内存，然后再释放堆内存，这样势必令到Python的内存管理效率大大降低。并且会给系统内核的虚拟内存管理带来严重的性能负担。严重拖慢操作系统的性能。

默认情况下，CPython3.9中关于小型整数的相关源代码比较分散，我们先查看一下IS_SMALL_INT宏函数的定义，如下代码片段所示

//位于Objects/longobject.c文件
#define NSMALLPOSINTS           _PY_NSMALLPOSINTS
#define NSMALLNEGINTS           _PY_NSMALLNEGINTS
....

//位于Include/internal/pycore_interp.h文件

//小型整数的右开区间，最大值256
#define _PY_NSMALLPOSINTS           257
//小型整数的左闭区间，为-5
#define _PY_NSMALLNEGINTS           5

// The PyInterpreterState typedef is in Include/pystate.h.
struct _is {
  .....
#if _PY_NSMALLNEGINTS + _PY_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
       -_PY_NSMALLNEGINTS (inclusive) to _PY_NSMALLPOSINTS (not inclusive).
    */
    PyLongObject* small_ints[_PY_NSMALLNEGINTS + _PY_NSMALLPOSINTS];
#endif
};

//位于Objects/longobject.c文件
#if NSMALLNEGINTS + NSMALLPOSINTS > 0

#define IS_SMALL_INT(ival) (-NSMALLNEGINTS <= (ival) && (ival) < NSMALLPOSINTS)
#define IS_SMALL_UINT(ival) ((ival) < NSMALLPOSINTS)

从上面的代码片段我们的知道，CPython预设的小型整数的区间为[-5，257)，该区间内的所有整数为填充到一个有small_ints的数组当中,small_int数组声明位于python核心C代码位于Include/internal/pycore_interp.h文件中，它是结构体_is的一个字段。

显然在Python解释器启动时会调用到_PyLong_Init函数完成small_inits数组的初始化，如下代码所示。

int
_PyLong_Init(PyThreadState *tstate)
{
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
    for (Py_ssize_t i=0; i < NSMALLNEGINTS + NSMALLPOSINTS; i++) {
        sdigit ival = (sdigit)i - NSMALLNEGINTS;
        int size = (ival < 0) ? -1 : ((ival == 0) ? 0 : 1);

        PyLongObject *v = _PyLong_New(1);
        if (!v) {
            return -1;
        }

        Py_SET_SIZE(v, size);
        v->ob_digit[0] = (digit)abs(ival);

        tstate->interp->small_ints[i] = v;
    }
#endif

    if (_Py_IsMainInterpreter(tstate)) {
        _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;
}

请思考一个问题：小型数据真的有意义吗？

你是否为认为小型整数的对象池对于实际的生产环境有实际意义？其实就我个人而言，其实没luan用！你试想一下稍微大型的计算用到整数，它们的字面量不会超过256吗！只不过CPython源代码是这么定义，那就照本宣课说一下。那有更高效的整数初始化方案吗？答案是有的，那就是Cython,通过Cython在Python代码中静态指定需要初始化的整数变量，甚至是整数的数组或整数指针。Cython的整数对象之所有高性能。

  • 因为Cython语法声明的变量，都是原始的C级别的数据类型，它们默认是基于C运行时系统的栈，而非CPython的数据栈或堆。
  • C运行时的栈(stack)提供了原始级别的数据访问，因此存取速度会比基于堆、或CPython内部stack指针构建的数据栈要快不是一两个数量级的问题，而是快十几个数量级。
  • 再者，Cython语法声明的整数对象在编译后的对象初始化的时间开销并是恒定时间开销O(1),Python实例化一个PyLongObject需要的时间开销，最起码也是O(n^2),因为实例化一个PyLongObject的Python语句等价于CPython内部执行5-6个指令码，我们知道每执行一个指令码都要遍历一次Python的解释循环，并执行其中内部C函数。还没有算上CPython运行时栈和堆的开销呢！！

我是基于事实分析问题，不像某些Python的极端分子极力吹捧。回归正题吧，查看一下代码吧，当我们碰巧在Python中碰到一个整数字面量刚好落入small_ints数据所指定的区间内，那么初始化一个PyLongObject时，PyLong_FromLong函数会以O(1)时间开销返回，因为其调用了get_small_int函数。Python极端狂热分子，还不赶快找个心灵安慰～～哈哈。

.....
static PyObject *
get_small_int(sdigit ival)
{
    assert(IS_SMALL_INT(ival));
    PyThreadState *tstate = _PyThreadState_GET();
    PyObject *v = (PyObject*)tstate->interp->small_ints[ival + NSMALLNEGINTS];
    Py_INCREF(v);
    return v;
}
....
static PyLongObject *
maybe_small_long(PyLongObject *v)
{
    if (v && Py_ABS(Py_SIZE(v)) <= 1) {
        sdigit ival = MEDIUM_VALUE(v);
        if (IS_SMALL_INT(ival)) {
            Py_DECREF(v);
            return (PyLongObject *)get_small_int(ival);
        }
    }
    return v;
}
#else
#define IS_SMALL_INT(ival) 0
#define IS_SMALL_UINT(ival) 0
#define get_small_int(ival) (Py_UNREACHABLE(), NULL)
#define maybe_small_long(val) (val)
#endif

结语

基于控制篇幅的原因，这是《CPython实现原理：整数对象》的前篇，关于大型整数的内容，我会放到下篇再说。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,772评论 6赞 477
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,458评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,610评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,640评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,657评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,590评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,962评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,631评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,870评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,611评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,704评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,386评论 4赞 319
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,969评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,944评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,179评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 44,742评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,440评论 2赞 342