探索CPython源码：任意精度整数的实现

Python部落(python.freelycode.com)组织翻译，禁止转载，欢迎转发。

你是否曾经注意到Python支持任意大小的整数？本文将对其机制进行回顾。

Python使用C语言的结构体来表现所有的类型。以下的数据结构负责所有的整数对象：

将宏展开后，简化版的结构体如下所示：

ob_refcnt字段负责垃圾回收机制中的引用计数，而ob_type则是指向描述整数类型的结构体的一个指针。

通常，在C和C++这一类语言中，整数的精度被限制在64位，但Python内置了对任意精度整数的支持。在Python3中，已经不会有简单整数类型，所有的整数都用大整数类来表示。

如何存储任意大小的整数？

一种方案是把整数表示为数字的链表。为了提高效率，我们需要把十进制的数字转换为2³⁰进制数值系统，这样每个元素代表0到2³⁰-1范围内的一个值。根据不同的平台， Python使用包含30位数值的32位无符号整数链表或者15位数值的16位无符号整数链表。使用这种方法也带了了额外的需求，我们无法使用整数的所有位。上例结构体中ob_digit的值负责这些链表。

为了减少不必要的开销，CPyhton在处理-2³⁰到2³⁰范围内的整数有一个“捷径”。这些数字以只有一个元素的列表的形式存储，只要这个数字能被表示为32位定长的数字。

值得注意的是，不像经典的方法，一个整数的标志被单独存储在ob_size的值中。这个值存储了ob_digit链表的大小。所以如果你想要修改长度为2的链表标志，需要将ob_digit设置为-2。

源代码的注释如下：

123456789101112131415将会表示成如下形式：

将现在的表示转换回去的算法为:

常用整数的优化

范围在-5到256之间的小整数对象通常在初始化时就已经进行了预分配。由于Python的整数对象是不可修改的，我们可以将其用作单体。每当需要 创建一个小整数对象时，Python只需要将指针移动到预分配的对象上。这样就为常用整数的调用节省了时间和空间上的开销。

有趣的是，PyLongObject结构体分配的整数都占用了28字节，这样一来比64位C整数多占用了三倍的内存。

数字系统转换

接下来我们看看Python中如何将数字转换为链表。

例如，我们需要将一个无符号64位长整型转换成Python整数的表述。需要注意的是，这是标准C类型最可能直接转换成我们的PyLongObject对象了。更大的数字可以由字符或者字节链表转换而来。

以下是由C语言转换为Python的简单算法：

为了验证结论，我们可以看一下全局表现：

计算

基础的计算操作的实现和学校中学的数学非常相似，仅有一点不同-链表中的每个元素都被看做一个单独的“数字”。

每个运算操作都会产生一个最小对象。例如，当你想执行c += 10 时，大概会有以下步骤：

• 获取一个预分配的整数对象10的地址（正如上文所说，由于10是一个小整数，我们不需要再创建一个整数对象）。

• 创建一个新的整数对象用来存储运算结果。

• 将c和10相加，把结果存储在新创建的对象。

• 将变量c替换为对新创建对象的引用。

• 将旧的c的引用计数减去1，这样垃圾回收器可以将其回收。

例如，让我们看一下使用carring的加法：

深入思考

还有很多细节在一篇文章里无法交代清楚。你可以在CPython(1,2,3)源代码中了解更多关于整数的知识。

我有继续这个系列的计划，在未来几篇博客中我将会描述类和函数对象的内部。

英文原文：http://rushter.com/blog/python-integer-implementation/
译者：mrwoody