《深度剖析CPython解释器》5.解密Python中的整数在底层是如何实现
的，以及为什么。。。
楔⼦
这次我们来分析⼀下Python中的整数是如何实现的，我们知道Python中的整数是不会溢出的，换句话说，它可以计算⽆穷⼤的数。只要你的内存⾜够，它就能计算，但是对于C来说显然是不⾏的，可Python底层⼜是C实现的，那么它是怎么做到整数不会溢出的呢？
既然想知道答案，那么看⼀下Python中的整型在底层是怎么定义的就⾏了。
int实例对象的底层实现
Python中的整数底层对应的结构体是PyLongObject，它位于longobject.h中。
//longobject.h
typedef struct _longobject PyLongObject; /* Revealed in longintrepr.h */
//longintrepr.h
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
//合起来可以看成
typedef struct {
祝福孩子
PyObject_VAR_HEAD
digit ob_digit[1];
} PyLongObject;
//如果把这个PyLongObject更细致的展开⼀下就是
typedef struct {
Py_ssize_t ob_refcnt; //引⽤计数
struct _typeobject *ob_type; //类型
Py_ssize_t ob_size; //维护的元素个数
digit ob_digit[1]; //digit类型的数组，长度为1
} PyLongObject;
别的先不说，就冲⾥⾯的ob_size我们就可以思考⼀番。⾸先Python中的整数有⼤⼩、但应该没有长度的概念吧，那为什么会有⼀个ob_size 呢？从结构体成员来看，这个ob_size指的应该就是ob_digit数组的长度，⽽这个ob_digit数组显然只能是⽤来维护具体的值了。⽽数组的长度不同，那么对应的整数占⽤的内存也不同。所以答案出来了，整数虽然没有我们⽣活中的那种长度的概念，但它是个变长对象，因为不同的整数占⽤的内存可能是不⼀样的。
因此这个ob_size它指的是底层数组的长度，因为Python中整数对应的值在底层是使⽤数组来存储的。尽管它没有字符串、列表那种长度的概念，或者说⽆法对整型使⽤len⽅法，但它是个变长对象。
那么下⾯的重点就在这个ob_digit数组了，我们要从它的⾝上挖掘信息，看看Python中整数对应的值(⽐如123)，是怎么放在这个数组⾥⾯的。
不过⾸先我们要看看这个digit是个什么类型，它同样定义在longintrepr.h中
//PYLONG_BITS_IN_DIGIT是⼀个宏，如果你的机器是64位的，那么它会被定义为30，32位机器则会被定义为15
洋参的功效//⾄于这个宏是做什么的我们先不管
#if PYLONG_BITS_IN_DIGIT == 30
typedef uint32_t digit;
// ...
#elif PYLONG_BITS_IN_DIGIT == 15
typedef unsigned short digit;
// ...
#endif
⽽我们的机器现在基本上都是64位的，所以PYLONG_BITS_IN_DIGIT会等于30，因为digit等价于uint32_t(unsigned int)，所以它是⼀个⽆符号32位整型。
所以ob_digit这个数组是⼀个⽆符号32位整型数组，长度为1。当然这个数组具体多长则取决于你要存储的Python整数有多⼤，因为C中数组的长度不属于类型信息，你可以看成是长度n，⽽这个n是多少要取决于你的整数⼤⼩。显然整数越⼤，这个数组就越长，那么占⽤空间就越
⼤。
搞清楚了PyLongObject⾥⾯的所有成员，那么下⾯我们就来分析ob_digit是怎么存储Python中的整数，以及Python中的整数为什么不会溢出。
不过说实话，关于Python的整数不会溢出这个问题，其实相信很多⼈已经有答案了，因为底层是使⽤数组存储的嘛，⽽数组的长度⼜没有限制，所以当然不会溢出啦。
另外，还存在⼀个问题，那就是digit是⼀个⽆符号32位整型，那负数怎么存储？别着急，我们会举栗说明，将上⾯的疑问⼀⼀解答。
⾸先如果你是Python的设计者，要保证整数不会溢出，你会怎么办？我们把问题简化⼀下，假设有⼀个8位的⽆符号整数类型，我们知道它能表⽰的最⼤数字是255，但这时候如果我想表⽰256，要怎么
办？
可能有⼈会想，那⽤两个数来存储不就好了。⼀个存储255，⼀个存储1，将这两个数放在数组⾥⾯。这个答案的话，虽然有些接近，但其实还有很⼤偏差：那就是我们并不能简单地按照⼤⼩拆分的，256拆分为255和1，要是265就拆分成255和10，⽽是要通过⼆进制的⽅式，我们来简单看⼀下。
我们知道8位整数最⼤就是 2 ^ 8 - 1，也就是它的⼋位全部都是1，结果是255
妈妈我想对你说作文400字所以255对应的数组就是: [255], 因为此时⼀个8位整数就能存下
但如果是256，那么8位显然存不下了，此时就还需要⼀个位
所以这个时候会使⽤两个8位整数, 但并不是简单的相加, ⽽是使⽤⼀个新的8位整数来模拟更⾼的位
⽽Python底层也是类似这种做法，但是考虑的会更加全⾯。下⾯就以Python中的整数为例，看看底层数组的存储⽅式。
整数0：
注意：当要表⽰的整数为0时，ob_digit这个数组为空，不存储任何值，ob_size为0，表⽰这个整数的值为0，这是⼀种特殊情况。
整数1：
当然存储的值为1时，ob_size的值就是1，此时ob_digit数组就是[1]。
整数-1：
我们看到ob_digit数组没有变化，但是ob_size变成了-1，没错，整数的正负号是通过这⾥的ob_size决定的。ob_digit存储的其实是绝对值，⽆论n取多少，-n和n对应的ob_digit是完全⼀致的，但是ob_size则互为相反数。所以ob_size除了表⽰数组的长度之外，还可以表⽰对应整数的正负。
所以我们之前说整数越⼤，底层的数组就越长。更准确的说是绝对值越⼤，底层数组就越长。所以Python在⽐较两个整型的⼤⼩时，会先⽐较ob_size，如果ob_size不⼀样则可以直接⽐较出⼤⼩来。显然ob_size越⼤，对应的整数越⼤，不管ob_size是正是负，都符合这个结论，可以想⼀下。
整数2 ^ 30 -1：
如果想表⽰2 ^30 - 1(^这⾥代指幂运算，当然对于Python程序猿来说两个星号也是幂运算，表达的意义是⼀样的)，那么也可以使⽤⼀个digit表⽰。虽然如此，但为什么突然举2 ^ 30 - 1这个数字呢？答案是，虽然digit是4字节、32位，但是Python只⽤30个位。
之所以这么做是和加法进位有关系，如果32个位全部⽤来存储其绝对值，那么相加产⽣进位的时候，可能会溢出，⽐如有⼀个将32个位全部占满的整数(2 ^ 32 - 1)，即便它只加上1，也会溢出。这个时候为了解决这个问题，就需要先强制转换为64位再进⾏运算。
但如果只⽤30个位的话，那么加法是不会溢出的，或者说相加之后依旧可以⽤32位整数保存。因为30个位最⼤就是2 ^ 30 - 1，即便两个这样的值相加，结果也是(2 ^ 30 - 1) * 2，即：2 ^ 31 - 2。⽽32个位的话最⼤是2 ^ 32 - 1，所以肯定不会溢出的；如果⼀开始30个位就存不下，那么数组中会有两个digit。
所以虽然将32位全部⽤完，可以只⽤⼀个digit表⽰更多、更⼤的整数，但是可能⾯临相加之后⼀个digit存不下的情况，于是只⽤30个位，如果数值⼤到30个位存不下的话，那么就会多使⽤⼀个digit。可能有⼈发现了，如果是⽤31个位的话，那么相加产⽣的最⼤值就是2 ^ 32 - 2，结果依旧可以使⽤⼀个32位整型存储啊，那Python为啥要牺牲两个位呢？答案是为了乘法运算。
// 还记得这个宏吗？PYLONG_BITS_IN_DIGIT指的就是Python使⽤digit的位数
// 我们看到在32位机器上，digit相当于2字节、16位的整型，⽽它⽤了15位，只牺牲了⼀个位
// 64 位机器上则牺牲两个位
#if PYLONG_BITS_IN_DIGIT == 30
typedef uint32_t digit;
// ...
#elif PYLONG_BITS_IN_DIGIT == 15
typedef unsigned short digit;
// ...
#endif
整数2 ^ 30：
问题来了，我们说digit只⽤30位，所以2 ^ 30 - 1是⼀个digit能存储的最⼤值，那么现在是2 ^ 30，所以数组中就要有两个digit了。
我们看到此时就⽤两个digit来存储了，此时的数组⾥⾯的元素就是0和1，⽽且充当⾼位的放在后⾯，因为我们说了使⽤新的digit来模拟更⾼的位。由于⼀个digit只⽤30位，那么数组中第⼀个digit的最低
位就是1，第⼆个digit的最低位就是31，第三个digit的最低位就是61，以此类推，所以如果ob_digit为[a, b, c]，那么对应的整数就为: a * 2 ** 0 + b * 2 ** 30 + c * 2 ** 60，如果ob_digit不⽌3个，那么就按照30个位往上加，⽐如ob_digit还有第四个元素d，那么就再加上d * 2 ** 90即可。
再⽐如我们反推⼀下，如果a = 88888888888，那么底层数组ob_digit中的值是多少？
import numpy as np
a = 88888888888
# 我们说1个digit⽤30个位, 那么n个digit所能表⽰的最⼤整数就是2 ** (30 * n) - 1, ⾄于原因的话其实很好理解，但我们还是可以严格推导⼀下
# 我们以n = 2为例, 显然两个digit最⾼能表⽰ (2 ** 30 - 1) + (2 ** 30 - 1) * 2 ** 30,
# 它等于 (2 ** 30 - 1) + (2 ** 60 - 2 ** 30) = 2 ** 60 - 1, 因此两个digit最⼤可以表⽰ 2 ** 60 - 1
合并单元格快捷键# 同理你可以n取3, 看看(2 ** 30 - 1) + (2 ** 30 - 1) * 2 ** 30 + (2 ** 30 - 1) * 2 ** 60是不是等于2 ** 90 - 1
# 或者试试更⼤的数, 结论都是成⽴的
print(np.log2(a)) # 36.37128404230425
# 36超过了30个位、但⼩于90个位, 因此需要两个digit
# 我们说 "整数 = ob_digit[0] + ob_digit[1] * 2 ** 30 + ob_digit[2] * 2 ** 60 + ..."
# 但是对于ob_digit长度为2的情况下, 这⾥的a = ob_digit[0] + ob_digit[1] * 2 ** 30
print(a // 2 ** 30) # 82
print(a - 82 * 2 ** 30) # 842059320
# 说明此时底层对应的ob_digit数组就是[842059320, 82]
我们修改解释器源代码重新编译，通过在创建整数的时候打印ob_digit⾥⾯的元素的值，也印证了这个结论。
这个时候，我们可以分析整数所占的字节了。相信所有⼈都知道可以使⽤sizeof计算⼤⼩，但是这⼤⼩到底是怎么来的，估计会⼀头雾⽔。因为Python中对象的⼤⼩，是根据底层的结构体计算出来的。
我们说ob_refcnt、ob_type、ob_size这三个是整数所必备的，它们都是8字节，加起来24字节。所以任何⼀个整数所占内存都⾄少24字节，⾄于具体占多少，则取决于ob_digit⾥⾯的元素都多少个。
因此Python中整数所占内存 = 24 + 4 * ob_digit数组长度
import sys
# 如果是0的话, ob_digit数组为空, 所以此时就是24字节
sizeof(0)) # 24
# 如果是1的话, ob_digit数组有⼀个元素, 所以此时是24 + 4 = 28字节
sizeof(1)) # 28
sizeof(2 ** 30 - 1)) # 28
# ⼀个digit只⽤30位, 所以最⼤能表⽰2 ** 30 - 1
# 如果是2 ** 30, 那么就需要两个元素, 所以是24 + 4 * 2 = 32字节
# 如果是两个digit, 那么能表⽰的最⼤整数就是2 ** 60 - 1
sizeof(2 ** 30)) # 32
sizeof(2 ** 60 - 1)) # 32
"""
相信下⾯的不需要解释了
"""
sizeof(1 << 60)) # 36
sizeof((1 << 90) - 1)) # 36
sizeof(1 << 90)) # 40
⼩整数对象池
由于分析过了浮点数以及浮点类型对象，因此int类型对象的实现以及int实例对象的创建啥的就不说了，可以⾃⼰去源码中查看，我们后⾯会着重介绍它的⼀些操作。还是那句话，Python中的API设计的很优美，都⾮常的相似，⽐如创建浮点数可以使⽤PyFloat_FromDouble、PyFloat_FromString等等，
那么创建整数也可以使⽤PyLong_FromLong、PyLong_FromDouble、PyLong_FromString等等，直接去Objects 中对应的源⽂件中查看即可。
这⾥说⼀下Python中的⼩整数对象池，我们知道Python中的整数属于不可变对象，运算之后会创建新的对象。
>>> a = 666
>>> id(a)
2431274354736
>>> a += 1
>>> id(a)
2431274355024
>>>
所以这种做法就势必会有性能缺陷，因为程序运⾏时会有⼤量对象的创建和销毁。根据浮点数的经验，
我们猜测Python应该也对整数使⽤了缓存池吧。答案是差不多，只不过不是缓存池，⽽是⼩整数对象池。
Python将那些使⽤频率⾼的整数预先创建好，⽽且都是单例模式，这些预先创建好的整数会放在⼀个静态数组⾥⾯，我们称为⼩整数对象池。如果需要使⽤的话会直接拿来⽤，⽽不⽤重新创建。注意：这些整数在Python解释器启动的时候，就已经创建了。
所以这种做法就势必会有性能缺陷，因为程序运⾏时会有⼤量对象的创建和销毁。根据浮点数的经验，我们猜测Python应该也对整数使⽤了缓存池吧。答案是差不多，只不过不是缓存池，⽽是⼩整数对象池。⼩整数对象池的实现位于longobject.c中。
#ifndef NSMALLPOSINTS
#define NSMALLPOSINTS 257
啤酒虾
#endif
#ifndef NSMALLNEGINTS
#define NSMALLNEGINTS 5
#endif
static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
NSMALLPOSINTS宏规定了对象池中正数的个数 (从 0 开始，包括 0 )，默认 257 个；
NSMALLNEGINTS宏规定了对象池中负数的个数，默认5个；
small_ints是⼀个整数对象数组，保存预先创建好的⼩整数对象；
以默认配置为例，Python解释器在启动的时候就会预先创建⼀个可以容纳262个整数的数组，并会依次初始化 -5 到 256(包括两端)之间的262个PyLongObject。所以⼩整数对象池的结构如下：
但是为什么要实现缓存从-5到256之间的整数呢？因为Python认为这个范围内的整数使⽤频率最⾼，⽽缓存这些整数的内存相对可控。因此这只是某种权衡，很多程序的开发场景都没有固定的正确答案，需要根据实际情况来权衡利弊。
>>> a = 256
>>> b = 256
>>> id(a), id(b)
(140714000246400, 140714000246400)
>>>
>>> a = 257
>>> b = 257
>>> id(a), id(b)
(2431274355184, 2431274354896)
>>>
256位于⼩整数对象池内，所以全局唯⼀，需要使⽤的话直接去取即可，因此它们的地址是⼀样的。但是257不再⼩整数对象池内，所以它们的地址不⼀样。
我们上⾯是在交互式下演⽰的，但如果有⼩伙伴不是通过交互式的话，那么会得到出乎意料的结果。
写中秋的诗
a = 257
b = 257
print(id(a) == id(b)) # True
可能有⼈会好奇，为什么地址⼜是⼀样的了，257明明不在⼩整数对象池中啊。虽然涉及到了后⾯的内容，但是提前解释⼀下也是可以的。主要区别就在于⼀个是在交互式下执⾏的，另⼀个是通过 python3 xxx.py的⽅式执⾏的。
⾸先Python的编译单元是函数，每个函数都有⾃⼰的作⽤域，在这个作⽤域中出现的所有常量都是唯⼀的，并且都位于常量池中，
由co_consts指向。虽然我们上⾯的不是函数，⽽是在全局作⽤域中，但是全局你也可以看成是⼀个函数，它也是⼀个独⽴的编译单元。同⼀个编译单元中，常量只会出现⼀次。
当a = 257的时候，会创建257这个整数、并放⼊常量池中；所以b = 257的时候就不会再创建了，因为常量池中已经有了，所以会直接从常量池中获取，因此它们的地址是⼀样的，因为是同⼀个PyLongObject。
女生标准体重算法# Python3.6下执⾏, 该系列的所有代码都是基于Python3.8, 但是这⾥先使⽤Python3.6, ⾄于原因, 后⾯会说
def f1():
a = 256
b = 257
return id(a), id(b)
def f2():
a = 256
b = 257
调经止痛片return id(a), id(b)
print(f1()) # (140042202371968, 140042204149712)
print(f2()) # (140042202371968, 140042204255024)
此时f1和f2显然是两个独⽴的编译单元，256属于⼩整数对象池中的整数、全局唯⼀，因此即便不在同
⼀个编译单元的常量池中，它的地址也是唯⼀的，因为它是预先定义好的，所以直接拿来⽤。但是257显然不是⼩整数对象池中的整数，⽽且不在同⼀个编译单元的常量池中，所以地址是不⼀样的。
⽽对于交互式环境来说，因为我们输⼊⼀⾏代码就会⽴即执⾏⼀⾏，所以任何⼀⾏可独⽴执⾏的代码都是⼀个独⽴的编译单元。注意：是可独⽴执⾏的代码，⽐如变量赋值、函数、⽅法调⽤等等；但如果是if、for、while、def等等需要多⾏表⽰的话，⽐如：if 2 > 1:，显然这就不是⼀⾏可独⽴执⾏的代码，它还依赖你输⼊的下⾯的内容。
>>> if 2 > 1: # 此时按下回车，我们看到不再是>>>, ⽽是..., 代表还没有结束, 还需要你下⾯的内容
... print("2 > 1")
... # 此时这个if语句整体才是⼀个独⽴的编译单元
2 > 1
>>>
但是像a = 1、foo()、lst.appned(123)这些显然它们是⼀⾏可独⽴执⾏的代码，因此在交互式中它们是独⽴的编译单元。
>>> a = 257 # 此时这⾏代码已经执⾏了，它是⼀个独⽴的编译单元
>>> b = 257 # 这⾏代码也是独⽴的编译单元，所以它⾥⾯的常量池为空，因此要重新创建
>>> id(a), id(b) # 由于它们是不同常量池内的整数，所以id是不⼀样的。
(2431274355184, 2431274354896)
但是问题来了，看看下⾯的代码，a和b的地址为啥⼜⼀样了呢？666和777明显也不在常量池中啊。
>>> a = 666;b=666
>>> id(a), id(b)
(2431274354896, 2431274354896)
>>> a, b = 777, 777
>>> id(a), id(b)
(2431274354800, 2431274354800)
>>>
显然此时应该已经猜到原因了，因为上⾯两种⽅式⽆论哪⼀种，都是在同⼀⾏，因此整体会作为⼀个编译单元，所以地址是⼀样的。
