深入理解Python虚拟机：整数（int）的实现原理及源码分析

深入理解Python虚拟机：整数（int）的实现原理及源码分析Howtorealize整型数据int主要是分析int类型的表示和int类型的巧妙设计。int类型在cpython中的实现数据结构如下：Py_ssize_t*ob_size；/变量部分的项目数*/}PyVarObject;typedefstruct_object{_PyObject_HEAD_EXTRAPy_ssize_tob_refcnt;struct_typeobject*ob_type;}PyObject;上面的数据结构以图的形式如下图所示：ob_refcnt，表示对象的引用计数，这对垃圾回收很有用。后面我们会深入分析虚拟机的垃圾回收部分。ob_type，表示这个对象的数据类型。在python中，有时候需要判断数据的数据类型，比如isinstance，type。这两个关键字将使用此字段。ob_size，该字段表示整数对象数组ob_digit中有多少个元素。digit类型其实是uint32_t类型的宏定义，代表32位整型数据。深入分析PyLongObject字段的语义首先，我们知道python中整数是不会溢出的，这也是PyLongObject使用数组的原因。在CPython的内部实现中，整数有0、正数、负数。对于这一点，CPython中有如下规定：ob_size，存放的是数组的长度。当ob_size大于0时，它存储正数。当ob_size小于0时存储为负数。ob_digit，存储整数的绝对值。前面我们提到，ob_digit是一个32位的数据，但是cpython内部只使用了前30位，只是为了避免溢出问题。下面通过几个例子来深入理解上面的规则：上图中ob_size大于0，表示该数为正数，ob_digit指向一个int32数据，数的值等于10，所以上面的数字代表一个整数10。同理，ob_size小于0，ob_digit等于10，所以上图中的数据代表-10。上面以ob_digit数组长度为2为例，上面表示的数据如下：$$1\cdot2^0+1\cdot2^1+1\cdot2^2+...+1\cdot2^{29}+0\cdot2^{30}+0\cdot2^{31}+1\cdot2^{32}$$因为我们只使用每个数组元素的前30位，所以当涉及到第二个整数数据时它正好对应$2^{30}$，就可以理解上面结果对应的整个计算过程了。上面也很简单：$$-(1\cdot2^0+1\cdot2^1+1\cdot2^2+...+1\cdot2^{29}+0\cdot2^{30}+0\cdot2^{31}+1\cdot2^{32})$$小整数池为了避免频繁创建一些常用的整数，加快程序执行速度，我们可以先缓存一些常用的整数，必要时返回这个即可数据直接。CPython中的相关代码如下：（小整数池缓存数据范围为[-5,256]）#defineNSMALLPOSINTS257#defineNSMALLNEGINTS5staticPyLongObjectsmall_ints[NSMALLNEGINTS+NSMALLPOSINTS];我们使用如下代码进行测试，看是否使用了小整数池中的数据。如果是，则id()的返回值与小整数池中的数据相同。内置函数id返回python对象的内存地址。>>>a=1>>>b=2>>>c=1>>>id(a),id(c)(4343136496,4343136496)>>>a=-6>>>c=-6>>>>id(a),id(c)(4346020624,4346021072)>>>a=257>>>b=257>>>id(a),id(c)(4346021104,4346021072)>>>来自上面的结果我们可以看到对于[-5,256]区间内的值，id的返回值确实是一样的，不在这个区间内的返回值是不同的。我们也可以利用这个特性来实现一个小技巧，就是找到一个PyLongObject对象占用的内存空间，因为我们可以用这两个数据的首内存地址-5和256，然后减去这个地址得到261一个PyLongObject占用内存空间的大小（注意小整数池中虽然有262个数据，但是最后一个数据是内存的首地址，不是尾地址，所以只有261个数据），所以我们可以查到一个PyLongObject对象的内存大小。>>>a=-5>>>b=256>>>(id(b)-id(a))/26132.0>>>从上面的输出我们可以看出一个PyLongObject对象占用了32个字节。我们可以使用下面的C程序来检查PyLongObject实际占用的内存空间。#include"Python.h"#includeintmain(){printf("%ld\n",sizeof(PyLongObject));return0;}上面程序的输出结果如下：上面两个两个结果是相等的，从而也验证了我们的想法。从小整数池中获取数据的核心代码如下：staticPyObject*get_small_int(sdigitival){PyObject*v;断言（-NSMALLNEGINTS<=ival&&ivalob_digit[i]+b->ob_digit[i];//保存数据的低30位z->ob_digit[i]=carry&PyLong_MASK;//右移进位30位，如果上面的加法中有进位，可以在下一次加法中使用（注意上面的进位）//用+=代替=进位>>=PyLong_SHIFT;//PyLong_SHIFT=30}//将剩下的a的长度保存下来（因为a的大小比b大）for(;iob_digit[i];z->ob_digit[i]=进位&PyLong_MASK;进位>>=PyLong_SHIFT；}//保存最后的高进位z->ob_digit[i]=carry;返回long_normalize(z);//long_normalize的主要作用是保证ob_size保存的是数据的实际长度，因为它可以是正数加上负数，变小}PyLongObject*_PyLong_New(Py_ssize_tsize){PyLongObject*result;/*所需的字节数是：offsetof(PyLongObject,ob_digit)+sizeof(digit)*size。此代码的先前版本使用sizeof(PyVarObject)而不是offsetof，但在PyVarObject标头和数字之间存在填充的情况下，这有可能不正确。*/if(size>(Py_ssize_t)MAX_LONG_DIGITS){PyErr_SetString(PyExc_OverflowError,“整数位数太多”）；返回空值；}//offsetof会调用gcc的一个内置函数__builtin_offsetof//offsetof(PyLongObject,ob_digit)这个函数是获取PyLongObject对象字段的ob_digit之前的所有字段占用的内存空间大小result=PyObject_MALLOC(offsetof(PyLongObject,ob_digit)+size*sizeof(digit));如果（！结果）{PyErr_NoMemory（）;返回空值；}//将对象结果的引用计数设置为1Py_ssize_ti=j;while(i>0&&v->ob_digit[i-1]==0)--i;如果(i!=j)Py_SIZE(v)=(Py_SIZE(v)<0)？-(i):我;returnv;}本文总结主要介绍了cpython内部如何实现整型数据int，分析了int类型的表示，设计int使用digit来表示32位整型数据，并且为了避免溢出的问题，只使用前30名。在cpython的内部实现中，整数有0、正数、负数。对此有如下规定：ob_size，存放数组的长度。当ob_size大于0时，它存储正数。当ob_size小于0时，它存储的是一个负数。ob_digit，存储整数的绝对值。另外，为了避免频繁创建一些常用的整数，cpython使用了小整数池的技术，先缓存一些常用的整数。最后，本文还介绍了整数加法的实现，即连续进行加法运算，然后进行进位运算。cpython使用这种方法的主要原理是大整数的加减乘除。本文主要介绍加法运算。有兴趣的可以自行阅读其他源程序。本文是深入理解python虚拟机系列文章之一。文章地址为：https://github.com/Chang-LeHung/dive-into-cpython更多精彩内容合集可访问：https://github.com/Chang-LeHung/CSCore关注公众号：废柴研究僧，多学点计算机（Java，Python，计算机系统基础，算法和数据结构）。