CPython中的整数类型实现

在Habré上已经有关于CPython的内存管理器 Pandas的实现细节的文章，我写了关于字典的实现的文章。

看来您可以编写一个常规的整数类型？ 但是，并非所有事情都那么简单，整数类型也不是那么明显。

如果您想知道为什么x * 2比x << 1快 。

以及如何提高以下技巧：

>>> 42 == 4 True >>> 42 4 >>> 1 + 41 4 

然后，您应该阅读这篇文章。

python中没有原始类型-所有变量都是对象，并在动态内存中分配。 同时，整数仅由一种类型（我们不考虑小数 ）表示-PyLongObject。 其实现和声明位于文件longobject.h，longintrepr.h和longobject.c中。

 struct _longobject { PyObject_VAR_HEAD //       digit ob_digit[1]; //   }; 

在CPython中的任何对象中都有两个字段：ob_refcnt-对象引用的计数器和ob_type-指向对象类型的指针；对于可以更改其长度的对象，添加了ob_size字段-当前分配的大小（使用的大小可能较小）。

因此，整数类型由可变长度的数组表示，这些数组由不同的数字组成，因此python开箱即用地支持长算术，在第二种语言版本中，存在另一种类型的“普通”整数。“长”整数是使用字母L创建的，或者使用导致普通程序溢出；在第三版中，它决定拒绝它。

  # python2 num1 = 42 print num1, type(num1) # 42 <type 'int'> num2 = 42L print num2, type(num2) # 42 <type 'long'> num3 = 2 ** 100 print num3, type(num3) # 1267650600228229401496703205376 <type 'long'> 

_longobject结构存储的整数值等于：

$$

$$\ sum_ {i = 0} ^ {abs（ob \ _size）-1} {ob \ _digit_i * 2 ^ {SHIFT * i}}$$

将64位系统上的32位无符号类型（uint32_t）和32位上的16位无符号short类型用作位。

实现中使用的算法对上一个公式的SHIFT进行了严格限制，特别是应将其除以15，因此，现在cpython支持64和32位系统的两个值：分别为30和15。 对于负值，ob_size为负值，ob_size = 0的数字为零。

在执行算术运算时，解释器检查操作数的当前长度，如果它们都由一位组成，则执行标准算术。

 static PyObject * long_add(PyLongObject *a, PyLongObject *b) { ... //   -     if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) { //      return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b)); } ... }; 

乘法具有相似的结构，此外，解释器实现了Karatsuba算法和快速平方 ，但是，并不是针对每个“长乘法”都执行乘法运算，而是仅对足够大的数字执行运算，数字的位数由两个常数给出：

 //     #define KARATSUBA_CUTOFF 70 //      #define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF) 

 static PyObject * long_mul(PyLongObject *a, PyLongObject *b) { ... //   -     if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) { // stwodigits -  ,    // int64_t  64-   long  32-. stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b); return PyLong_FromLongLong((long long)v); } ... // ""    O(N^2),     . i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF; if (asize <= i) { if (asize == 0) return (PyLongObject *)PyLong_FromLong(0); else return x_mul(a, b); } ... }; 

但是，移位命令不检查“短”整数的情况；对于长运算，总是执行它们。 因此，乘以2快于移位。 有趣的是，除法要比右移慢，这也不能检查一位整数的情况。 但是除法更复杂：有一种方法首先计算商，然后将余数NULL传递给它，如果您需要计算一件事，即该方法也必须检查这种情况，所有这些都会增加开销。

比较功能对于“短”整数也没有特殊情况。

 static int long_compare(PyLongObject *a, PyLongObject *b) { Py_ssize_t sign; // ,        //        if (Py_SIZE(a) != Py_SIZE(b)) { sign = Py_SIZE(a) - Py_SIZE(b); } else { Py_ssize_t i = Py_ABS(Py_SIZE(a)); //  ""        while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]) ; if (i < 0) sign = 0; else { sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i]; if (Py_SIZE(a) < 0) sign = -sign; } } return sign < 0 ? -1 : sign > 0 ? 1 : 0; } 

数字数组（列表）

创建整数类型变量时，解释器应在动态内存中分配足够的空间，然后设置引用计数器（类型ssize_t），指向PyLongObject类型的指针，位数组的当前大小（也为ssize_t）并初始化数组本身。 对于64位系统，最小结构大小为：2 * ssize_t +指针+数字= 2 * 8 + 8 + 4 = 28字节。 创建数字列表时会出现其他问题：由于数字不是原始类型，并且python中的列表存储了对对象的引用，因此这些对象不在动态内存中按顺序排列。

这种安排减慢了阵列上的迭代速度：实际上，执行随机访问，这使得无法预测转换。

为了避免过多分配动态内存，这会减慢运行时间并导致内存碎片，因此在cpython中实现了优化：在启动阶段，预先分配了一个小整数数组：从-5到256。

 #ifndef NSMALLPOSINTS #define NSMALLPOSINTS 257 //     python    . #endif #ifndef NSMALLNEGINTS #define NSMALLNEGINTS 5 #endif 

结果，cpython中的数字列表在内存中表示如下：



借助本文和标准ctypes模块，有机会从脚本中获取预选的小整数列表：

免责声明：以下代码按原样提供，在运行此代码后，作者不承担任何责任，也不能保证解释器的状态以及您和您的同事的心理健康。

 import ctypes #  PyLongObject class IntStruct(ctypes.Structure): #   _fields_ = [("ob_refcnt", ctypes.c_long), ("ob_type", ctypes.c_void_p), ("ob_size", ctypes.c_long), ("ob_digit", ctypes.c_int)] def __repr__(self): return ("IntStruct(ob_digit={self.ob_digit}, ob_size={self.ob_size}, " "refcount={self.ob_refcnt})").format(self=self) if __name__ == '__main__': #    42 int42 = IntStruct.from_address(id(42)) print(int42) int_minus_2 = IntStruct.from_address(id(-2)) print(int_minus_2) # ob_digit=2, ob_size=-1 #       int42.ob_digit = 4 print(4 == 42) # True print(1 + 41) # 4 

诚实的PyLongObject存储在此列表中，也就是说，它们有一个参考计数器，例如，您可以找出脚本和解释器使用了多少个零。

从整数的内部实现可以看出，cpython中的算术不能很快，其他语言按顺序遍历数组，将数字读入寄存器并直接调用多个处理器指令，cpython在整个内存中被标记，执行相当复杂的方法。 在单位整数的最简单情况下（调用一条指令就足够了），解释器必须比较大小，然后在动态内存中创建一个对象，填充服务字段并返回指向它的指针;此外，这些操作需要GIL锁。 现在您了解了为什么numpy库问世以及为什么它如此流行。

我想突然用有关布尔类型的信息来结束有关cpython中整个类型的文章。

事实是，很长一段时间以来，在python中，布尔变量没有单独的类型，所有逻辑函数都返回0和1。但是， 他们决定引入一种新类型。 同时，它被整体实现为子类型。

 PyTypeObject PyBool_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) //       // ,       //     ob_size "bool", //   sizeof(struct _longobject), //    ... &PyLong_Type, //   ... bool_new, //  }; 

而且，布尔类型的每个值都是单例，布尔变量是指向True或False实例的指针（没有类似的实现方式）。

 struct _longobject _Py_FalseStruct = { PyVarObject_HEAD_INIT(&PyBool_Type, 0) { 0 } }; struct _longobject _Py_TrueStruct = { PyVarObject_HEAD_INIT(&PyBool_Type, 1) { 1 } }; static PyObject * bool_new(PyTypeObject *type, PyObject *args, PyObject *kwds) { PyObject *x = Py_False; long ok; if (!_PyArg_NoKeywords("bool", kwds)) return NULL; if (!PyArg_UnpackTuple(args, "bool", 0, 1, &x)) return NULL; ok = PyObject_IsTrue(x); if (ok < 0) return NULL; return PyBool_FromLong(ok); } PyObject *PyBool_FromLong(long ok) { PyObject *result; if (ok) result = Py_True; else result = Py_False; Py_INCREF(result); return result; } 

PyObject_IsTrue（x）是一种用于计算布尔值的棘手机制，您可以在bool函数的部分或文档中找到它 。

这样的遗产会带来一些有趣的效果，例如True和1的完全相等，无法在字典和集合中将True和1作为键，以及对布尔类型的算术运算的可接受性：

 >>> True == 1 True >>> {True: "true", 1: "one"} {True: 'one'} >>> True * 2 + False / (5 * True) - (True << 3) -6.0 >>> False < -1 False 

python语言的灵活性和可读性非常出色，但是，必须牢记所有这些都是有代价的，例如，多余的抽象和开销是我们通常不会考虑或猜测的形式。 我希望本文能使您在解释器的源代码上消除“战争迷雾”，甚至可以诱使您对其进行研究。 解释器代码非常易于阅读，几乎就像python本身的代码一样，对其进行研究不仅可以使您了解如何实现解释器，还可以学习有趣的算法和系统解决方案，还可以编写更高效的代码或成为cpython本身的开发人员。