Python 整数数据类型的实现

接着之前的 《Python 对象模型》继续看看 Python 的源代码,之前说了,Python 的一切数据都是对象,甚至于不是数据都是对象,例如函数啊,类啊这些这些对象。其实,在 Python 的实现中,套路都差不多,无非是关注这些对象是怎么创建的,然后内部的数据结构是怎么编排的,有什么优化策略这些,所以,我就准备不多看,就看看整数的实现。

对于 Python 整数,我开始学的时候有个很感兴趣的点就是 Python 的整数居然是没有溢出的,例如这些代码你就可以看出来了:

有意思吧,一个整数左移了 100 位都没溢出,我想你肯定不会说内部是用一个 128 位的数据类型来实现的,好像现在 C 语言中也还没这个类型吧?

整数的内部结构

之前一篇文章说过啦,整数的数据结构是 PyLongObject,没说也至少提到过,所以我就直接看这个数据结构好啦:

很简单,可以看到数据是保存到了一个指针(这里定义的是一个元素为1的数组,似乎是 C 语言里面的惯用套路)里头,然后这个数据长度是放在 PyOBject_VAR_HEAD 里面的啦,后面会看到关于他的操作。

新建和删除一个整数

新建和删除一个整数在 Python 里面是有一点点优化的,类似于 Java,对于小整数,Python 会在启动的时候先创建好,后面要用的时候就不用创建了,直接增加引用计数即可,反正你也改变不了一个整数的值(不可变对象),至于小整数的定义,看代码中的这个值:

这里也就是将 [-5, 257) 范围内的整数都定义为小整数。所以创建的时候,如果数字是这个返回就直接返回已经创建好的对象了:

这是定义的一个检查小整数的宏,在创建整数对象的时候都会先检验一遍,然后不是小整数才会做其他整数的操作:

这里 Line 44 就是检查并且返回小整数的宏,实现就很简单了,再来看看其他整数是怎么操作的,我们前面看到了,整数都是被拆到一个个 digit 里面的,digit 的大小不确定,可能是 15 bit 或者 30 bit。所以这里第一步是先确定需要多少个 digitLine49 就是在计算,然后 Line 52 就创建对应长度的对象,因为我们说了,digit 是一个数组,需要调节它的长度。然后 Line 58 就是拆分保存数据了。

这里还有一点没高亮的是 Line 55,这里将这个整数的正负保存在 ob_size 这个字段,而不是保存在 digit 里面,也就是说 digit 里面保存的是数字的绝对值,这样有什么好处?操作方便啊,加减乘除都不需要担心符号的问题,而且拆分也是大胆得拆,不需要考虑符号问题。

整数的加减乘除

整数这么创建的话,加减我们就比较简单得可以猜到了,就是直接加和直接减少,来点简单的代码吧:

可以看到,就两个循环,一个个 digit 得加,唯一需要注意的就是 长度 和 进位 的问题。加减是简单,但是乘除就复杂了,乘法的我还能看得明白一些,除法的我直接就放弃了,很复杂,引用注释的一段话:

/* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
   edn.), section 4.3.1, Algorithm D], except that we don't explicitly
   handle the special case when the initial estimate q for a quotient
   digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
   that won't overflow a digit. */

那就记录点我看懂了的乘法吧,因为它将整数拆成一个个 digit,所以乘法也就是一个个 digit 来乘,我们可以想象一下小学的时候学的乘法:

这是 10进制的嘛,然后我们可以将一个 digit 当成一位,也是可以实现的,但是,就是更复杂了一些,为了减少一些乘法操作,Python 进行了一点点的优化:

  /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
 * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh  + ah*bh + al*bl
 * Then the original product is
 *     ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
 * By picking X to be a power of 2, "*X" is just shifting, and it's
 * been reduced to 3 multiplies on numbers half the size.
 */

这里的目的就是将大的整数的乘法转化成小一半的整数的乘法,从而减少真正乘法的规模和次数,同时,这里的 X 因为是 2 的倍数,所以直接移位就可以了,效率不能更高,所以真正的乘法就变少了。

Reference

  1. Why do some structures end with an array of size 1?
  2. Multiplication algorithm

· EOF ·

最近爬虫很是凶猛,标注下文章的原文地址: https://liuliqiang.info/post/integer-struct-implement-in-python/