最近突然涌起兴趣去阅读 CPython 源码,网上也看了不少解析的文章,后来网上看到《Python源码剖析》评价不错,可惜现在已经绝版,只能从豆瓣阅读购买了一本电子书观摩 。

我从网上下载的是最新的 Python 2.7 源码,这本书配套的解说代码是 Python 2.5 的,这是一个遗憾,但是大体上相差不大,刚好昨天遇到一处。

昨天看到 Python int 实现的原理,这里不详细表述,有兴趣的可以去看看书。其中整数加法 (int_add) 的实现,虽然代码只有几行,但是其中隐藏的知识点还是非常多的,花了点时间回顾了一些基础知识,在这里也简单总结下。

以下是 2.5 里面加法的实现,也是书中提供的例子,这里直接引用过来作为参考对比,注释是作者加入的。

static PyObject* int_add(PyIntObject *v, PyIntObject *w)
{
    register long a, b, x;
    CONVERT_TO_LONG(v, a);
    CONVERT_TO_LONG(w, b);
    x = a + b;
    //[1] : 检查加法结果是否溢出
    if ((x^a) >= 0 || (x^b) >= 0)
        return PyInt_FromLong(x);
    return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
}

下面是 2.7 中的代码对比,大体都没有变化:

static PyObject *
int_add(PyIntObject *v, PyIntObject *w)
{
    register long a, b, x;
    CONVERT_TO_LONG(v, a);
    CONVERT_TO_LONG(w, b);
    /* casts in the line below avoid undefined behaviour on overflow */
    x = (long)((unsigned long)a + b);
    if ((x^a) >= 0 || (x^b) >= 0)
        return PyInt_FromLong(x);
    return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
}

在此之前,先简单介绍下上面的逻辑:
1)首先 int_add 函数是 Python 中 int 加法的实现函数,参数是两个 Python 整数对象,PyIntObject;
2)接着使用预先定义好的宏(不是重点,这里不具体展开),从整数对象中取出 value,这个value就是整数的值,类型是 long;
3)接下来做整数加法,判断是否溢出,如果没有发生溢出,则将新建一个整数对象,最后结果返回;
4)如果加法过程中发生溢出,则使用更长的类型(PyLong_Type)来做这个加法运算;

这个函数的精髓在与加法的处理,不是简单求和返回,可以看出 2.5 和 2.7代码的区别:

// 2.5
x = a + b;

// 2.7
x = (long)((unsigned long)a + b);

为什么 2.7 要搞得怎么复杂,又是转换成 unsigned long 最后又转换为 long,实际上原因是因为一个历史包袱,在C语言的定义中有符号数(signed)的加法溢出是 undefined behavior,所以这里先变成无符号数的加法,如果溢出就是简单做个截断(取模)。注意,无符号数和有符号数运算,有符号数会隐式转换成无符号数。

接下来我们看对溢出额判断,(x^a) >= 0 || (x^b) >= 0,为什么使用异或来判断。这里先梳理下,什么情况下会发生加法溢出:
1)如果两个不同符号的数字相加,不会发生溢出,比如 5 + (-128);
2)如果两个相同符号的数字相加,可能会发生溢出,比如正正相加溢出后变成负数,负负相加后变成整数;
这里实际上就是利用了这两点来作为判断依据,如果加法运算结果和原来的任意一个数字符号一致就没有溢出,使用异或来判断性能更好。关于溢出的判断还有其他方法,网上也有不少小伙伴提供了更多思路

这里还有一个隐含的点,在 Python 里整数对象是不可变的,这个要注意,相加之后是返回一个新的对象:

>>> a = 1
>>> id(a)
38821992L
>>> a += 1
>>> id(a)
38821968L

继续看书。

转载请注明转自: 团子的小窝 , 本文固定链接: CPython 源码中整数加法的实现