forked from zpoint/CPython-Internals
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlong_cn.md
More file actions
215 lines (131 loc) · 7.83 KB
/
Copy pathlong_cn.md
File metadata and controls
215 lines (131 loc) · 7.83 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
# int
感谢 @MambaWong 指出之前本章节存在的问题 [#22](https://github.com/zpoint/CPython-Internals/issues/22) 已改正
# 目录
* [相关位置文件](#相关位置文件)
* [内存构造](#内存构造)
* [内部元素如何存储](#内部元素如何存储)
* [整数 0](#整数-0)
* [整数 1](#整数-1)
* [整数 -1](#整数-1)
* [整数 1023](#整数-1023)
* [整数 32767](#整数-32767)
* [整数 32768](#整数-32768)
* [小端大端](#小端大端)
* [第一个保留位](#第一个保留位)
* [small ints(缓冲池)](#small-ints)
# 相关位置文件
* cpython/Objects/longobject.c
* cpython/Include/longobject.h
* cpython/Include/longintrepr.h
# 内存构造
在 python3 之后, 就只有一个叫做 **int** 的类型了, python2.x 的 **long** 类型在 python3.x 里面就叫做 **int** 类型
**int** 在内存空间上的构造和 [tuple 元素在内存空间的构造](https://github.com/zpoint/CPython-Internals/blob/master/BasicObject/tuple/tuple_cn.md#%E5%86%85%E5%AD%98%E6%9E%84%E9%80%A0) 非常相似
很明显, 只有 **ob_digit** 这一个位置可以用来存储真正的整数, 但是 cpython 如何按照字节来存储任意长度的整型的呢?
我们来看看
# 内部元素如何存储
## 整数 0
注意, 当要表示的整数的值为 0 时, **ob_digit** 这个数组为空, 不存储任何东西, **ob_size** 中的 0 就直接表示这个整数的值为 0, 这是一种特殊情况
```python3
i = 0
```
## 整数 1
**ob_digit** 可以有两种不同的定义, 具体是 uint32_t 还是 unsigned short 取决于操作系统
```c
#if PYLONG_BITS_IN_DIGIT == 30
typedef uint32_t digit;
typedef int32_t sdigit;
typedef uint64_t twodigits;
typedef int64_t stwodigits; /* signed variant of twodigits */
#define PyLong_SHIFT 30
#define _PyLong_DECIMAL_SHIFT 9 /* max(e such that 10**e fits in a digit) */
#define _PyLong_DECIMAL_BASE ((digit)1000000000) /* 10 ** DECIMAL_SHIFT */
#elif PYLONG_BITS_IN_DIGIT == 15
typedef unsigned short digit;
typedef short sdigit; /* signed variant of digit */
typedef unsigned long twodigits;
typedef long stwodigits; /* signed variant of twodigits */
#define PyLong_SHIFT 15
#define _PyLong_DECIMAL_SHIFT 4 /* max(e such that 10**e fits in a digit) */
#define _PyLong_DECIMAL_BASE ((digit)10000) /* 10 ** DECIMAL_SHIFT */
```
我把源代码里的 **PYLONG_BITS_IN_DIGIT** 的值写死成了 15, 这样我下面所有的示例都是以 **unsigned short** 定义的 **digit**
当我们需要表示整数 1 的时候, **ob_size** 的值变成了1, 这个时候 **ob_size** 表示 **ob_digit** 的长度, 并且 **ob_digit** 里以 **unsigned short** 的表示方式存储了整数1
```python3
i = 1
```
## 整数 -1
当 i 变成 -1 时候, 唯一的和整数 1 的区别就是储存在 **ob_size** 里的值变成了 -1, 这里的负号表示这个整数的正负性, 不影响到 **ob_digit** 里面的值
```python3
i = -1
```
## 整数 1023
对于 PyLongObject 来说, 最基本的存储单位是 **digit**, 在我这里是 2个 byte 的大小(16个bit). 1023 只需要占用最右边的10个bit 就够了, 所以 **ob_size** 里的值仍然是 1
## 整数 32767
整数 32767 的存储方式依旧和上面的存储无大致上的差别
## 整数 32768
我们发现, cpython 并不会占用掉一个 **digit** 的所有的 bit 去存储一个数, 第一个 bit 会被保留下来, 我们后面会看到这个保留下来的 bit 有什么作用
## 小端大端
注意, 因为 **digit** 作为 cpython 表示整型的最小存储单元, **digit** 里面的 byte 存储的顺序和你的机器的顺序一致
而 **digit** 和 **digit** 之间则是按照 权重最重的 **digit** 在最右边 原则存储的(小端存储)
我们来看一看整数值 -262143 的存储方式
负号依旧存储在 **ob_size** 里面
整数值 262143(2^18 = 262144) 的二进制表示应该是 00000011 11111111 11111111
## 第一个保留位
为什么 **digit** 的最左边一位需要保留下来呢? 为什么 **ob_digit** 里面的 **digit** 的顺序是按照小端的顺序存储的呢?
我们尝试跑一个简单的加法来理解一下
```python3
i = 1073741824 - 1 # 1 << 30 == 1073741824
j = 1
```
```python3
k = i + j
```
首先, 相加之前会初始化一个中间变量我这里叫做 temp, 他的类型也是 **PyLongObject**, 并且大小为 max(size(i), size(j)) + 1
第一步, 把两个数 **ob_digit** 里的第一个坑位里的 **digit** 加起来, 并加到 **carray** 里
第二步, 把 temp[0] 里的值设置为 (carry & PyLong_MASK)
第三步, 右移 carray, 值保留下最左边的一位(这一位其实就是之前两个数相加的进位)
第四步, 把两边下一个 **ob_digit** 的对应位置的值加起来, 并把结果与 **carray** 相加
第五步, 把 temp[1] 里的值设置为 (carry & PyLong_MASK)
第六步, 再次右移
回到步骤四, 直到两边都没有剩余的 **digit** 可以相加为止, 把最后的 carray 存储到 temp 最后一格
temp 这个变量此时按照 **PyLongObject** 的方式存储了前面两个数的和, 现在细心地你应该发现了, 第一个保留位是为了用来相加或者相减的时候作进位/退位 用的, 并且当 **digit** 和 **digit** 之间按照小端的方式存储的时候, 你做加减法的时候只需要从左到右处理即可
减法的操作和加法类似, 有兴趣的同学可以自己参考源代码
## small ints
cpython 同时也使用了一个全局变量叫做 small_ints 来单例化一部分常见范围的整数, 这么做可以减少频繁的向操作系统申请和释放的次数, 并提高性能
```c
#define NSMALLPOSINTS 257
#define NSMALLNEGINTS 5
static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
```
我们来看看
```python3
c = 0
d = 0
e = 0
print(id(c), id(d), id(e)) # 4480940400 4480940400 4480940400
a = -5
b = -5
print(id(a), id(b)) # 4480940240 4480940240
f = 1313131313131313
g = 1313131313131313
print(id(f), id(g)) # 4484604176 4484604016
```
