说明
- python源码版本：3.8.3
参考：
python源码剖析
https://yq.aliyun.com/users/1709307684254463
int
在源码实现中，python3之前用int和long两种类型来表示数字，而python3开始则统一使用long来表示数字（尽管在使用python时，显示的是int，实际上在底层是long类型）
int定义
struct _longobject {
// python变长对象头
PyObject_VAR_HEAD
// digit定义：typedef uint32_t digit;
// ob_digit是一个单一元素，内容为uint型，并且是可变大小的数组（单一元素的数组放在一个struct的尾端，则数组大小是可变的），存放的是具体的数值
digit ob_digit[1];
};
从int的定义看出存放int具体数值的数据类型实际上是一个数组，因此python中int的大小没有限制，而数组里存放的数组都是无符号数字，那么正负数如何区分呢？实际上其将判断正负数、零的标识存放在了头部PyObject_VAR_HEAD的ob_size中，而ob_digit中只存储其绝对值数值，后面从int对象的创建逻辑当中可以看到这些
创建int对象
int对象的创建方式会根据传入的数值或者类型转换等情况来决定，例如：小于C中long类型大小的数值，一般基于PyLong_FromLong方法创建，而大于该数的则可能基于PyLong_FromString方法创建，这里简单介绍下通过long方式创建的逻辑：
// 通过数值创建python中int对象方法，例如：a = 100
PyObject *
PyLong_FromLong(long ival)
{
PyLongObject *v;
// abs_ival中存放绝对值数值
unsigned long abs_ival;
unsigned long t; /* unsigned so >> doesn't propagate sign bit */
int ndigits = 0;
// 数值标记：正数(1)，负数(-1)，零(0)
int sign;
// 检查如果是小整数，则直接返回缓冲池的小整数对象，后面会介绍，在python3.8中缓冲池范围是[-5, 257)
CHECK_SMALL_INT(ival);
// 将数值和正负数的标识分开
if (ival < 0) {
abs_ival = 0U-(unsigned long)ival;
sign = -1;
}
else {
abs_ival = (unsigned long)ival;
sign = ival == 0 ? 0 : 1;
}
// 对于小于PyLong_SHIFT位的数进入快速通道，PyLong_SHIFT的值基于当前系统中定义指针的大小确定
// （指针在32位中size为4，64位中为8，因此例如32位平台下32768以下的数字都可以进入该通道）
if (!(abs_ival >> PyLong_SHIFT)) {
// 创建一个数值指向区域size为1*sizeof(digit)的long对象
v = _PyLong_New(1);
if (v) {
// 可以看出ob_size用来标识是正数、负数还是0
Py_SIZE(v) = sign;
// ob_digit[0]里存入的是无符号的数值
v->ob_digit[0] = Py_SAFE_DOWNCAST(
abs_ival, unsigned long, digit);
}
return (PyObject*)v;
}
// 对于指针大小为4字节的情况（例如32位系统），申请对象空间的方式
#if PyLong_SHIFT==15
/* 2 digits */
if (!(abs_ival >> 2*PyLong_SHIFT)) {
v = _PyLong_New(2);
if (v) {
Py_SIZE(v) = 2*sign;
v->ob_digit[0] = Py_SAFE_DOWNCAST(
abs_ival & PyLong_MASK, unsigned long, digit);
v->ob_digit[1] = Py_SAFE_DOWNCAST(
abs_ival >> PyLong_SHIFT, unsigned long, digit);
}
return (PyObject*)v;
}
#endif
// 对于较大的数值，需要获取位数，然后申请对应大小的long对象
t = abs_ival;
// 获取数值所需的位数
while (t) {
++ndigits;
t >>= PyLong_SHIFT;
}
// 后面的逻辑跟之前的创建方式基本一样
v = _PyLong_New(ndigits);
if (v != NULL) {
digit *p = v->ob_digit;
Py_SIZE(v) = ndigits*sign;
t = abs_ival;
while (t) {
*p++ = Py_SAFE_DOWNCAST(
t & PyLong_MASK, unsigned long, digit);
t >>= PyLong_SHIFT;
}
}
return (PyObject *)v;
}
小整数缓冲池
在python中对于int数据，其定义了缓冲池，对常用范围的小整数都进行了缓存处理，从而提高数值使用的效率，缓冲池部分源码如下：
// 定义小整数的缓冲池
// #define NSMALLPOSINTS 257
// #define NSMALLNEGINTS 5
static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
// 获取小整数对象
static PyObject *
get_small_int(sdigit ival)
{
PyObject *v;
assert(-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS);
// 在符合小整数的范围内，返回直接缓冲池中的对象
v = (PyObject *)&small_ints[ival + NSMALLNEGINTS];
Py_INCREF(v);
...
return v;
}
// 如果是小整数，则直接从小整数缓冲池当中获取对象
#define CHECK_SMALL_INT(ival) \
do if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \
return get_small_int((sdigit)ival); \
} while(0)
可以看出在[-5, 257)之间是存在缓存的，证明如下：
>>> id(-5)
1665722640
>>> id(-5)
1665722640
# -5的id都一样
>>> id(-6)
2331088351536
>>> id(-6)
2331088351312
# -6的id发生了变化
>>> id(256)
1665730992
>>> id(256)
1665730992
# 256的id都一样
>>> id(257)
2331088351312
>>> id(257)
2331088351536
# 257的id发生了变化
因此对于小整数使用较多的场景，我们可以通过修改小整数的缓冲池范围来进行优化
加法逻辑
由于python中的int属于不可变类型数据，因此在进行加法运算时，会创建一个新的int对象来存储计算的结果值，并且由于int中数据的存储是基于数据，因此在计算时实际上模拟了从低位开始逐位相加运算的方式来进行运算，而通过这种存储和计算方式，一般也就不用担心大数计算时的溢出等问题了，源码逻辑如下：
// 加法运算逻辑
static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
PyLongObject *z;
Py_ssize_t i;
digit carry = 0;
// 如果a比b小，就交换两个数，以保证a是大的那个数
if (size_a < size_b) {
{ PyLongObject *temp = a; a = b; b = temp; }
{ Py_ssize_t size_temp = size_a;
size_a = size_b;
size_b = size_temp; }
}
// 以最大的那个值的size+1为新创建的long对象大小
z = _PyLong_New(size_a+1);
if (z == NULL)
return NULL;
// 低位开始逐位相加（两个数中小的那个数的最高位及以下位相加）
for (i = 0; i < size_b; ++i) {
carry += a->ob_digit[i] + b->ob_digit[i];
z->ob_digit[i] = carry & PyLong_MASK;
carry >>= PyLong_SHIFT;
}
// 高位只剩下a的值，直接将a的值填充
for (; i < size_a; ++i) {
carry += a->ob_digit[i];
z->ob_digit[i] = carry & PyLong_MASK;
carry >>= PyLong_SHIFT;
}
// 新创建的对象保存对应结果
z->ob_digit[i] = carry;
// long_normalize将数值前面的0删除（并没有真正删除释放，而是改变其允许指向数值的范围大小）
return long_normalize(z);
}
list
结构定义
typedef struct {
// python变长对象的头部分，其中list的真实数据的长度就存在头部的ob_size里
PyObject_VAR_HEAD
// 存放所有数据的数组，每个数据都是PyObject类型
PyObject **ob_item;
// list申请的内存大小
Py_ssize_t allocated;
} PyListObject;
缓冲池
// #define PyList_MAXFREELIST 80
// list缓冲池空间定义，可以看出大小是80
static PyListObject *free_list[PyList_MAXFREELIST];
// 缓冲池中已使用的数量
static int numfree = 0;
当创建了一个list对象后，将会存入缓冲区，如果这个list对象没有被使用，将会留在缓冲区，等到下一次创建list对象时，如果缓冲区里存在list对象，则直接返回该对象
创建list对象
例如对于a = [1,2,3]的字节码指令如下：
0 LOAD_CONST 1 (1)
2 LOAD_CONST 2 (2)
4 LOAD_CONST 3 (3)
6 BUILD_LIST 3
8 STORE_FAST 0 (a)
前三个指令依次将1、2、3压入栈中，然后通过BUILD_LIST创建一个list并从栈中取出的数据存入，其中build_list的操作源码如下：
// BUILD_LIST指令操作
case TARGET(BUILD_LIST): {
// 创建一个空的list对象（里面没有存放数据，但是已经分配了对应大小的内存，oparg就是list需要的长度）
PyObject *list = PyList_New(oparg);
if (list == NULL)
goto error;
while (--oparg >= 0) {
// 依次从栈中取出list需要存入的元素（对应上面的指令就是依次取出3、2、1），然后存入到list的指令位置当中
PyObject *item = POP();
PyList_SET_ITEM(list, oparg, item);
}
PUSH(list);
DISPATCH();
}
其中通过PyList_New函数创建一个list对象，源码如下：
PyObject *
PyList_New(Py_ssize_t size)
{
PyListObject *op;
if (size < 0) {
PyErr_BadInternalCall();
return NULL;
}
// 如果缓冲池里存在list对象，则取出
if (numfree) {
// 缓冲池list对象数量-1
numfree--;
// 获取缓冲池的对应list对象
op = free_list[numfree];
_Py_NewReference((PyObject *)op);
} else {
// 否则创建一个list空间大小的对象
op = PyObject_GC_New(PyListObject, &PyList_Type);
if (op == NULL)
return NULL;
}
// 如果list里没有内容，则ob_item（实际存放list内容的地方）设置为空
if (size <= 0)
op->ob_item = NULL;
// list中存在内容，则申请对应大小的空间给ob_item
else {
op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
if (op->ob_item == NULL) {
Py_DECREF(op);
return PyErr_NoMemory();
}
}
// 设置list数据长度
Py_SIZE(op) = size;
// 设置list容量大小，可以看出list初始化时的分配的容量大小跟数据长度是一样的
op->allocated = size;
_PyObject_GC_TRACK(op);
return (PyObject *) op;
}
我们可以进行测试：
>>> id([1,2,3])
7002632
>>> id([1,2,3,4])
7002632
# 可以看出都是复用缓冲池的list对象
>>> id([1,2,3,4,5])
7002632
>>> a = [1,2,3]
>>> id(a)
7002632
# 将对象赋值指向后
>>> id([1,2,3])
8095848
# 可以看出创建了一个新的list对象
append逻辑
static int
app1(PyListObject *self, PyObject *v)
{
// 获取当前list尺寸
Py_ssize_t n = PyList_GET_SIZE(self);
assert (v != NULL);
if (n == PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"cannot add more objects to list");
return -1;
}
// 更新list尺寸，使list能够存入n+1数量的数据，如果失败则返回-1
if (list_resize(self, n+1) < 0)
return -1;
Py_INCREF(v);
// 设置第n个位置的值为v
PyList_SET_ITEM(self, n, v);
return 0;
}
int
PyList_Append(PyObject *op, PyObject *newitem)
{
if (PyList_Check(op) && (newitem != NULL))
return app1((PyListObject *)op, newitem);
PyErr_BadInternalCall();
return -1;
}
extend主逻辑
...
// 插入数据是否可迭代判断
iterable = PySequence_Fast(iterable, "argument must be iterable");
if (!iterable)
return NULL;
// 计算要插入的数据长度
n = PySequence_Fast_GET_SIZE(iterable);
if (n == 0) {
/* short circuit when iterable is empty */
Py_DECREF(iterable);
Py_RETURN_NONE;
}
// 获取list当前长度
m = Py_SIZE(self);
/* It should not be possible to allocate a list large enough to cause
an overflow on any relevant platform */
assert(m < PY_SSIZE_T_MAX - n);
// 当前list长度+插入长度判断，只申请一次
if (list_resize(self, m + n) < 0) {
Py_DECREF(iterable);
return NULL;
}
/* note that we may still have self == iterable here for the
* situation a.extend(a), but the following code works
* in that case too. Just make sure to resize self
* before calling PySequence_Fast_ITEMS.
*/
/* populate the end of self with iterable's items */
src = PySequence_Fast_ITEMS(iterable);
dest = self->ob_item + m;
// 遍历设置值
for (i = 0; i < n; i++) {
PyObject *o = src[i];
Py_INCREF(o);
dest[i] = o;
}
Py_DECREF(iterable);
Py_RETURN_NONE;
...
insert逻辑
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
Py_ssize_t i, n = Py_SIZE(self);
PyObject **items;
if (v == NULL) {
PyErr_BadInternalCall();
return -1;
}
if (n == PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"cannot add more objects to list");
return -1;
}
// 尺寸判断
if (list_resize(self, n+1) < 0)
return -1;
if (where < 0) {
where += n;
// 负值索引如果加上长度还<0，则置为0
if (where < 0)
where = 0;
}
// 索引大于最大长度，则设置为往后面添加
if (where > n)
where = n;
items = self->ob_item;
// insert位置后面的数据都后挪一位
for (i = n; --i >= where; )
items[i+1] = items[i];
Py_INCREF(v);
// 插入数据
items[where] = v;
return 0;
}
append/extend/insert效率问题
通过前面三种添加方式的源码实现可以看出：insert的逻辑中，需要对插入部分后面的数据进行后移操作，以及对插入位置进行一些范围处理，所以效率上会比append差一些；在append里每添加一条数据都需要进行尺寸判断，不够则重新申请，而extend则是一口气算出最终需要的尺寸，只需要申请一次即可，所以效率上append会比extend差一些，特别是在添加的数据量越大时越明显，所以在数据量大的情况下三者的效率应该是：insert<append<extend（如果数据特别少，那么因为append逻辑最简单，所以效率应该是extend<insert<append），如下代码可以验证：
from time import time
l = 10000000
data = [i for i in range(l)]
def count_time(func):
def wrapper():
s = time()
func()
print(func.__name__, ":", time() - s)
wrapper()
@count_time
def insert():
li = []
for i in range(l):
li.insert(i, data[i])
@count_time
def append():
li = []
for i in range(l):
li.append(data[i])
@count_time
def extend():
li = []
li.extend(data)
# insert : 2.52603816986084
# append : 1.7159614562988281
# extend : 0.21300077438354492
而如果我们用Python去实现可变序列（MutableSequence）相关的类型时，由于Python无法进行像C那样底层的操作，所以extend的实现实际上就是遍历append而已，此时append和extend的效率就没有多大的差别了，源码如下：
def extend(self, values):
'S.extend(iterable) -- extend sequence by appending elements from the iterable'
for v in values:
self.append(v)
list尺寸更新逻辑
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated, num_allocated_bytes;
Py_ssize_t allocated = self->allocated;
// 如果数据量在总大小的一半以上，且小于总大小，则无需重新计算尺寸
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SIZE(self) = newsize;
return 0;
}
// 新内存大小分配规则
new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
// 最大长度限制
if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
PyErr_NoMemory();
return -1;
}
if (newsize == 0)
new_allocated = 0;
// 内存大小计算
num_allocated_bytes = new_allocated * sizeof(PyObject *);
// 内存申请
items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
if (items == NULL) {
PyErr_NoMemory();
return -1;
}
// list存放数据的地方
self->ob_item = items;
// list中存放的数据长度
Py_SIZE(self) = newsize;
// list内存分配的长度
self->allocated = new_allocated;
return 0;
}
remove逻辑
static PyObject *
list_remove(PyListObject *self, PyObject *value)
/*[clinic end generated code: output=f087e1951a5e30d1 input=2dc2ba5bb2fb1f82]*/
{
Py_ssize_t i;
// 遍历所有值，找到第一个要删除的，将其删除，然后返回
for (i = 0; i < Py_SIZE(self); i++) {
PyObject *obj = self->ob_item[i];
// 引用+1
Py_INCREF(obj);
// PyObject_RichCompareBool会根据第三个参数来进行比较，这里比较的是是否相等
// 相等则返回1，不相等返回0，还有相关判断会返回-1
int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
// 操作完毕，引用-1
Py_DECREF(obj);
if (cmp > 0) {
// 删除第i个操作，该方法逻辑较多，其中删除的逻辑可以参考动态数组的删除方式
if (list_ass_slice(self, i, i+1,
(PyObject *)NULL) == 0)
Py_RETURN_NONE;
// Py_RETURN_NONE源码：
// #define Py_RETURN_NONE return Py_INCREF(Py_None), Py_None
// 将None引用+1，并返回None
return NULL;
}
// cmp小于0属于其他情况
else if (cmp < 0)
return NULL;
}
// 遍历完都没有找到要删除的，则会抛出异常
PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
return NULL;
}
包含逻辑(x in list)
static int
list_contains(PyListObject *a, PyObject *el)
{
PyObject *item;
Py_ssize_t i;
int cmp;
// 遍历取出内容进行比较，当找到时停止遍历
for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i) {
item = PyList_GET_ITEM(a, i);
Py_INCREF(item);
cmp = PyObject_RichCompareBool(el, item, Py_EQ);
Py_DECREF(item);
}
return cmp;
}
索引逻辑(index)
static PyObject *
list_index_impl(PyListObject *self, PyObject *value, Py_ssize_t start,
Py_ssize_t stop)
/*[clinic end generated code: output=ec51b88787e4e481 input=40ec5826303a0eb1]*/
{
Py_ssize_t i;
// 负值索引（如：list[-1]）的实质就是`list[len(list) + (-1)]`
if (start < 0) {
start += Py_SIZE(self);
if (start < 0)
start = 0;
}
// stop会自动调整到>=0
if (stop < 0) {
stop += Py_SIZE(self);
if (stop < 0)
stop = 0;
}
// 遍历查找
for (i = start; i < stop && i < Py_SIZE(self); i++) {
PyObject *obj = self->ob_item[i];
Py_INCREF(obj);
int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
Py_DECREF(obj);
// 找到了则将索引转成long类型返回
if (cmp > 0)
return PyLong_FromSsize_t(i);
else if (cmp < 0)
return NULL;
}
PyErr_Format(PyExc_ValueError, "%R is not in list", value);
return NULL;
}
修改逻辑(li[i] = x)
int
PyList_SetItem(PyObject *op, Py_ssize_t i,
PyObject *newitem)
{
PyObject **p;
// list类型检查
if (!PyList_Check(op)) {
Py_XDECREF(newitem);
PyErr_BadInternalCall();
return -1;
}
// 范围检查
if (!valid_index(i, Py_SIZE(op))) {
Py_XDECREF(newitem);
PyErr_SetString(PyExc_IndexError,
"list assignment index out of range");
return -1;
}
// 找到对应位置进行修改操作
p = ((PyListObject *)op) -> ob_item + i;
Py_XSETREF(*p, newitem);
// Py_XSETREF源码：
// #define Py_XSETREF(op, op2) \
// do { \
// PyObject *_py_tmp = _PyObject_CAST(op); \
// (op) = (op2); \
// Py_XDECREF(_py_tmp); \
// } while (0)
// 解释：将旧的内容替换成新的内容，并将旧的内容引用计数-1
return 0;
}
dict
python中大部分的运行机制当中都采用了dict来进行数据的管理，所以为了最高效的查询性能，dict底层选择了基于哈希表实现。其中在python3.6之前，dict的实现里将数据存在了hash表里，所以之前的dict是无序且十分消耗内存的，而在python3.6以后，官方对dict进行了很大地改进（主要是将数据和hash部分分离），包括从无序变为有序，在一定程度上减少了内存的消耗，以及部分操作性能的提升等，具体参考：https://zhuanlan.zhihu.com/p/73426505
dict定义
在python3.6之前，字典的数组中的对应位置都存放着完整的键值对信息-(hash, key, value)，这种字典类型被称为combined型，后来为了提升性能，将完整的键值对信息存放到另一个数组entries当中，而对于原来字典的数组里，对应位置只存放了键值对在entries中的索引，这种字典类型被称为split型，这里主要对split型字典进行介绍，官方提供的内存布局如下：
+---------------+
| dk_refcnt | key集合的引用数
| dk_size | key集合的大小
| dk_lookup | 字典查询方法
| dk_usable | 字典中key集合可用大小
| dk_nentries | 字典对应的entries集合的内容数量
+---------------+
| dk_indices | key集合（哈希表部分），存放所有key在entries中对应的索引
| |
+---------------+
| dk_entries | 存放所有的键值对数据信息
| |
+---------------+
基于上面的布局，源码中对于dict的结构定义如下：
// dict总体结构
typedef struct {
// 通用对象头
PyObject_HEAD
// 键值对的数量
Py_ssize_t ma_used;
// 版本标记
uint64_t ma_version_tag;
// key集合，哈希表就存在这里面
PyDictKeysObject *ma_keys;
// entries集合，split中，所有的键值对都存在ma_values里，而combined型的ma_values将会是null
PyObject **ma_values;
} PyDictObject;
// key集合结构
typedef struct _dictkeysobject PyDictKeysObject;
struct _dictkeysobject {
// key集合的引用数
Py_ssize_t dk_refcnt;
// 哈希表索引数组的大小
Py_ssize_t dk_size;
// 字典查询方法
dict_lookup_func dk_lookup;
// 字典中key集合可用大小
Py_ssize_t dk_usable;
// entries中键值对的数量
Py_ssize_t dk_nentries;
// 每个键对应存放数据位置的索引
char dk_indices[];
};
// entries集合中单个元素的结构
typedef struct {
Py_hash_t me_hash;
PyObject *me_key;
// 在split型中，value存放在ma_values中，所以只有combined型的时候，me_value才存放value
PyObject *me_value;
} PyDictKeyEntry;
dict的几种状态
在python3.6之前，dict中的键值对主要有以下三种状态：
- Unused：此时key为null，即还未使用当前位置，此时索引值被设为
-1 - Active：如果当前位置设置了键值对，那么就会进入该状态，表示正在使用中，此时索引值就是所在位置的索引
- Dummy：当被使用的key删除时，将会进入该状态，用于避免探测链断开而导致索引出错的问题，此时索引值为
-2
在python3.6以后，由于索引和键值对分开存储，于是便取消了Dummy态，而使用Pending态来进行代替：
- Pending：同样是删除键值对以后进入的状态，此时索引不变，但是对应索引存储的value将会被删除，从而等待新的对应索引的key插入
几种状态的源码定义如下：
#define DKIX_EMPTY (-1)
#define DKIX_DUMMY (-2)
#define DKIX_ERROR (-3)
dict基本配置
// 哈希表的起始尺寸为8
#define PyDict_MINSIZE 8
// 哈希表相对于索引数量的尺寸
#define ESTIMATE_SIZE(n) (((n)*3+1) >> 1)
// 当需要更新dict尺寸时，尺寸大小为索引数*3
#define GROWTH_RATE(d) ((d)->ma_used*3)
dict缓冲池
// dict缓冲池大小，可以看出尺寸和list缓冲池一样是80
#ifndef PyDict_MAXFREELIST
#define PyDict_MAXFREELIST 80
#endif
// 可以发现对dict对象和dict中的key集合对象都有进行缓冲池操作
static PyDictObject *free_list[PyDict_MAXFREELIST];
static int numfree = 0;
static PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST];
static int numfreekeys = 0;
创建dict
// 空字典的key集合
static PyDictKeysObject empty_keys_struct = {
1, /* dk_refcnt */
1, /* dk_size */
lookdict_split, /* dk_lookup */
0, /* dk_usable (immutable) */
0, /* dk_nentries */
// 可以看到初始化的哈希表里都是Unused状态
// #define DKIX_EMPTY (-1)
{DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY,
DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY}, /* dk_indices */
};
// 空的entries
static PyObject *empty_values[1] = { NULL };
// 空的key集合
#define Py_EMPTY_KEYS &empty_keys_struct
// dict对象创建入口
PyObject *
PyDict_New(void)
{
// 引用+1
dictkeys_incref(Py_EMPTY_KEYS);
// 通过空集合和空entries创建一个空字典
return new_dict(Py_EMPTY_KEYS, empty_values);
}
// 创建一个dict对象
static PyObject *
new_dict(PyDictKeysObject *keys, PyObject **values)
{
PyDictObject *mp;
assert(keys != NULL);
// 缓存池操作，和list的差不多
if (numfree) {
mp = free_list[--numfree];
assert (mp != NULL);
assert (Py_TYPE(mp) == &PyDict_Type);
_Py_NewReference((PyObject *)mp);
}
else {
mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
if (mp == NULL) {
dictkeys_decref(keys);
if (values != empty_values) {
free_values(values);
}
return NULL;
}
}
// 初始化操作，设置keys、values等内容，注意这里的keys和values的内容还都是空的
mp->ma_keys = keys;
mp->ma_values = values;
mp->ma_used = 0;
mp->ma_version_tag = DICT_NEXT_VERSION();
ASSERT_CONSISTENT(mp);
return (PyObject *)mp;
}
dict添加
// 添加/设置逻辑
int
PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
{
PyDictObject *mp;
Py_hash_t hash;
if (!PyDict_Check(op)) {
PyErr_BadInternalCall();
return -1;
}
assert(key);
assert(value);
mp = (PyDictObject *)op;
// 获取对象的哈希值，如果不是可哈希的，则无法执行setitem操作
if (!PyUnicode_CheckExact(key) ||
(hash = ((PyASCIIObject *) key)->hash) == -1)
{
hash = PyObject_Hash(key);
if (hash == -1)
return -1;
}
// 如果哈希表是一个空表，则直接往空字典插入数据
if (mp->ma_keys == Py_EMPTY_KEYS) {
return insert_to_emptydict(mp, key, hash, value);
}
// 添加或修改操作函数
return insertdict(mp, key, hash, value);
}
// dict添加和更新的主逻辑
static int
insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
{
PyObject *old_value;
PyDictKeyEntry *ep;
Py_INCREF(key);
Py_INCREF(value);
if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
if (insertion_resize(mp) < 0)
goto Fail;
}
// 寻找对应key的索引
Py_ssize_t ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value);
// 异常情况处理
if (ix == DKIX_ERROR)
goto Fail;
assert(PyUnicode_CheckExact(key) || mp->ma_keys->dk_lookup == lookdict);
MAINTAIN_TRACKING(mp, key, value);
if (_PyDict_HasSplitTable(mp) &&
((ix >= 0 && old_value == NULL && mp->ma_used != ix) ||
(ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {
if (insertion_resize(mp) < 0)
goto Fail;
ix = DKIX_EMPTY;
}
// 如果对应的key的映射为空，则代表添加数据
if (ix == DKIX_EMPTY) {
assert(old_value == NULL);
if (mp->ma_keys->dk_usable <= 0) {
if (insertion_resize(mp) < 0)
goto Fail;
}
// 寻找哈希表中当前key的插入位置
Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
// ep指向entries的最后一位（索引为dk_nentries处）
ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
// 设置indices中对应entries的索引，可以看到设置的entries索引就是entries的数量，因为键值对每次都是往entries的最后一位添加的
dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
// 设置新加入entries的键值对数据
ep->me_key = key;
ep->me_hash = hash;
if (mp->ma_values) {
assert (mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
mp->ma_values[mp->ma_keys->dk_nentries] = value;
}
else {
ep->me_value = value;
}
// 添加成功操作
mp->ma_used++;
mp->ma_version_tag = DICT_NEXT_VERSION();
mp->ma_keys->dk_usable--;
mp->ma_keys->dk_nentries++;
assert(mp->ma_keys->dk_usable >= 0);
ASSERT_CONSISTENT(mp);
return 0;
}
// 如果不是添加操作，并且指定entries的value和当前传入的value不同，则需要更新value
if (old_value != value) {
// split型表的操作
if (_PyDict_HasSplitTable(mp)) {
// 直接更新entries中对应索引的value
mp->ma_values[ix] = value;
// 当前位置属于pending状态（已删除状态），则说明之前没有使用，现在使用了，所以使用数+1
if (old_value == NULL) {
assert(ix == mp->ma_used);
mp->ma_used++;
}
}
// combined型表的操作
else {
assert(old_value != NULL);
// 由于key、value都是存在哈希表中，直接修改哈希表对应位置的value
DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
}
mp->ma_version_tag = DICT_NEXT_VERSION();
}
Py_XDECREF(old_value);
ASSERT_CONSISTENT(mp);
Py_DECREF(key);
return 0;
Fail:
Py_DECREF(value);
Py_DECREF(key);
return -1;
}
// 查找hash值在哈希表中的映射
static Py_ssize_t
find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash)
{
assert(keys != NULL);
const size_t mask = DK_MASK(keys);
size_t i = hash & mask;
// 获取哈希表索引
Py_ssize_t ix = dictkeys_get_index(keys, i);
// 哈希冲突处理
for (size_t perturb = hash; ix >= 0;) {
perturb >>= PERTURB_SHIFT;
i = (i*5 + perturb + 1) & mask;
ix = dictkeys_get_index(keys, i);
}
return i;
}
dict查询
源码逻辑如下：
// 查询函数主逻辑
static Py_ssize_t _Py_HOT_FUNCTION
lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
Py_hash_t hash, PyObject **value_addr)
{
assert(mp->ma_values == NULL);
// key不为字符串时，直接调用lookdict函数查询
if (!PyUnicode_CheckExact(key)) {
mp->ma_keys->dk_lookup = lookdict;
return lookdict(mp, key, hash, value_addr);
}
// 字符串的索引情况，逻辑上基本和lookdict函数相同（分析在下面），但是简化了一些操作
PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
size_t mask = DK_MASK(mp->ma_keys);
size_t perturb = (size_t)hash;
size_t i = (size_t)hash & mask;
for (;;) {
Py_ssize_t ix = dictkeys_get_index(mp->ma_keys, i);
assert (ix != DKIX_DUMMY);
if (ix == DKIX_EMPTY) {
*value_addr = NULL;
return DKIX_EMPTY;
}
PyDictKeyEntry *ep = &ep0[ix];
assert(ep->me_key != NULL);
assert(PyUnicode_CheckExact(ep->me_key));
if (ep->me_key == key ||
(ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
*value_addr = ep->me_value;
return ix;
}
perturb >>= PERTURB_SHIFT;
i = mask & (i*5 + perturb + 1);
}
Py_UNREACHABLE();
}
// 字典非字符串查询的逻辑实现
static Py_ssize_t _Py_HOT_FUNCTION
lookdict(PyDictObject *mp, PyObject *key,
Py_hash_t hash, PyObject **value_addr)
{
size_t i, mask, perturb;
PyDictKeysObject *dk;
PyDictKeyEntry *ep0;
top:
// 字典对应的所有key
dk = mp->ma_keys;
// 字典对应的所有结果
ep0 = DK_ENTRIES(dk);
// 防止哈希越界的mask（类似对哈希取余作用），DK_MASK定义如下：
// #define DK_MASK(dk) (((dk)->dk_size)-1)
mask = DK_MASK(dk);
// 对应的哈希值
perturb = hash;
// 哈希映射到字典的位置
i = (size_t)hash & mask;
for (;;) {
// 获取映射位置存放的索引（即在entries中的索引）
Py_ssize_t ix = dictkeys_get_index(dk, i);
// 索引位置存储索引值不存在的情况
if (ix == DKIX_EMPTY) {
// 设置返回的value为空
*value_addr = NULL;
return ix;
}
// 索引位置对应的entry索引存在
if (ix >= 0) {
// 到entry集中取出对应位置的entry结果
PyDictKeyEntry *ep = &ep0[ix];
assert(ep->me_key != NULL);
// 如果entry中的key和查询的key相同，说明是要查找的数据
if (ep->me_key == key) {
// 设置对应的返回value
*value_addr = ep->me_value;
return ix;
}
// 如果key不同哈希却相同的情况
if (ep->me_hash == hash) {
PyObject *startkey = ep->me_key;
Py_INCREF(startkey);
// 比较两个key是否相等，1代表相等，0代表不等，-1代表比较失败
int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
// 比较失败的情况，说明是异常情况，返回一个错误状态
if (cmp < 0) {
*value_addr = NULL;
return DKIX_ERROR;
}
if (dk == mp->ma_keys && ep->me_key == startkey) {
// 比较相等
if (cmp > 0) {
*value_addr = ep->me_value;
return ix;
}
}
// 如果能到这里（哈希相同，key却不同），说明字典在使用期间发生了改变，因此需要重新查询
else {
/* The dict was mutated, restart */
goto top;
}
}
}
// 不是对应的key，则通过下面探测函数继续寻找下一个位置
perturb >>= PERTURB_SHIFT;
i = (i*5 + perturb + 1) & mask;
}
Py_UNREACHABLE();
}
// 获取对应key的索引中存放的entry索引（具体内容存放的地方）
static inline Py_ssize_t
dictkeys_get_index(PyDictKeysObject *keys, Py_ssize_t i)
{
// 字典大小
Py_ssize_t s = DK_SIZE(keys);
Py_ssize_t ix;
// 基于字典大小，选择对应的数据类型存放索引值
if (s <= 0xff) {
// 获取到存放所有key的地方
int8_t *indices = (int8_t*)(keys->dk_indices);
// 获取当前key对应的索引
ix = indices[i];
}
else if (s <= 0xffff) {
// 基本和前面一样，只是存放索引的类型不同
int16_t *indices = (int16_t*)(keys->dk_indices);
ix = indices[i];
}
#if SIZEOF_VOID_P > 4
else if (s > 0xffffffff) {
int64_t *indices = (int64_t*)(keys->dk_indices);
ix = indices[i];
}
#endif
else {
int32_t *indices = (int32_t*)(keys->dk_indices);
ix = indices[i];
}
// 结果必须是索引存储的值存在或者为空
assert(ix >= DKIX_DUMMY);
return ix;
}
dict删除
dict的删除操作并不会真正将entries中对应的索引删除，而是进行一种伪删除操作-将entries中对应位置的内容清空（否则需要对后面的数据进行前挪操作，并且还要更新后面几个数据的key，效率上的问题可想而知...），源码逻辑如下：
// 删除操作逻辑
static int
delitem_common(PyDictObject *mp, Py_hash_t hash, Py_ssize_t ix,
PyObject *old_value)
{
PyObject *old_key;
PyDictKeyEntry *ep;
Py_ssize_t hashpos = lookdict_index(mp->ma_keys, hash, ix);
assert(hashpos >= 0);
// 使用数-1
mp->ma_used--;
mp->ma_version_tag = DICT_NEXT_VERSION();
ep = &DK_ENTRIES(mp->ma_keys)[ix];
// 设置对应位置为dummy态
dictkeys_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
// 因为存在dummy态，所以需要修改索引方式为支持dummy态的
ENSURE_ALLOWS_DELETIONS(mp);
old_key = ep->me_key;
// 设置entries中对应位置的key和value为空
ep->me_key = NULL;
ep->me_value = NULL;
Py_DECREF(old_key);
Py_DECREF(old_value);
ASSERT_CONSISTENT(mp);
return 0;
}
// 删除主逻辑
int
PyDict_DelItem(PyObject *op, PyObject *key)
{
Py_hash_t hash;
assert(key);
// 可hash校验
if (!PyUnicode_CheckExact(key) ||
(hash = ((PyASCIIObject *) key)->hash) == -1) {
hash = PyObject_Hash(key);
if (hash == -1)
return -1;
}
return _PyDict_DelItem_KnownHash(op, key, hash);
}
int
_PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
{
Py_ssize_t ix;
PyDictObject *mp;
PyObject *old_value;
if (!PyDict_Check(op)) {
PyErr_BadInternalCall();
return -1;
}
assert(key);
assert(hash != -1);
mp = (PyDictObject *)op;
// 找到对应的entries索引
ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
// 异常情况处理
if (ix == DKIX_ERROR)
return -1;
// 如果索引的entry位置内容为空，则报错
if (ix == DKIX_EMPTY || old_value == NULL) {
_PyErr_SetKeyError(key);
return -1;
}
// Split table doesn't allow deletion. Combine it.
if (_PyDict_HasSplitTable(mp)) {
if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
return -1;
}
ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
assert(ix >= 0);
}
// 伪删除逻辑
return delitem_common(mp, hash, ix, old_value);
}
update主逻辑
static int
dict_merge(PyObject *a, PyObject *b, int override)
{
PyDictObject *mp, *other;
Py_ssize_t i, n;
PyDictKeyEntry *entry, *ep0;
assert(0 <= override && override <= 2);
if (a == NULL || !PyDict_Check(a) || b == NULL) {
PyErr_BadInternalCall();
return -1;
}
// 左边的转字典类型
mp = (PyDictObject*)a;
// 如果右边的是字典类型，且可以用字典的方法迭代
if (PyDict_Check(b) && (Py_TYPE(b)->tp_iter == (getiterfunc)dict_iter)) {
// 右边的也转字典类型
other = (PyDictObject*)b;
// 如果两个字典是同一个或者右边的字典为空，则直接返回
if (other == mp || other->ma_used == 0)
return 0;
// 如果左边的字典为空，到时候就直接将右边的内容覆盖到左边的字典里
if (mp->ma_used == 0)
override = 1;
// 如果左边字典允许使用的数量比右边已使用的key数量小，则进行扩容操作
if (USABLE_FRACTION(mp->ma_keys->dk_size) < other->ma_used) {
if (dictresize(mp, ESTIMATE_SIZE(mp->ma_used + other->ma_used))) {
return -1;
}
}
// 获取entries数组进行迭代
ep0 = DK_ENTRIES(other->ma_keys);
for (i = 0, n = other->ma_keys->dk_nentries; i < n; i++) {
PyObject *key, *value;
Py_hash_t hash;
entry = &ep0[i];
key = entry->me_key;
hash = entry->me_hash;
// split/combined型获取value方式兼容
if (other->ma_values)
value = other->ma_values[i];
else
value = entry->me_value;
if (value != NULL) {
int err = 0;
Py_INCREF(key);
Py_INCREF(value);
// 如果覆盖模式的话，则直接将右边字典的key设置进去（如果左边字典有该key，则会被覆盖）
if (override == 1)
err = insertdict(mp, key, hash, value);
// 如果在左边的字典里没找到对应的key，则插入数据
else if (_PyDict_GetItem_KnownHash(a, key, hash) == NULL) {
if (PyErr_Occurred()) {
Py_DECREF(value);
Py_DECREF(key);
return -1;
}
err = insertdict(mp, key, hash, value);
}
// 如果左边的字典里有该key，且override为2，则不允许覆盖，报错
else if (override != 0) {
_PyErr_SetKeyError(key);
Py_DECREF(value);
Py_DECREF(key);
return -1;
}
// 所以如果override==0，那么如果左边有该key，则不进行任何操作
Py_DECREF(value);
Py_DECREF(key);
if (err != 0)
return -1;
// 字典update期间被修改导致的entries发生改变
if (n != other->ma_keys->dk_nentries) {
PyErr_SetString(PyExc_RuntimeError,
"dict mutated during update");
return -1;
}
}
}
}
// 左边不为字典类型的情况
else {
PyObject *keys = PyMapping_Keys(b);
PyObject *iter;
PyObject *key, *value;
int status;
if (keys == NULL)
return -1;
// 获取key的迭代器
iter = PyObject_GetIter(keys);
Py_DECREF(keys);
if (iter == NULL)
return -1;
// 迭代key进行赋值操作
for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
// 非覆盖的情况
if (override != 1) {
// 如果左边的字典里存在该key
if (PyDict_GetItemWithError(a, key) != NULL) {
// 如果override==2，则报错
if (override != 0) {
_PyErr_SetKeyError(key);
Py_DECREF(key);
Py_DECREF(iter);
return -1;
}
// 如果override==0，则直接跳到下一个key
Py_DECREF(key);
continue;
}
// 当线程当中存在异常
else if (PyErr_Occurred()) {
Py_DECREF(key);
Py_DECREF(iter);
return -1;
}
}
// 如果覆盖模式，则直接设置对应的键值对
value = PyObject_GetItem(b, key);
if (value == NULL) {
Py_DECREF(iter);
Py_DECREF(key);
return -1;
}
status = PyDict_SetItem(a, key, value);
Py_DECREF(key);
Py_DECREF(value);
if (status < 0) {
Py_DECREF(iter);
return -1;
}
}
Py_DECREF(iter);
if (PyErr_Occurred())
return -1;
}
// 对combined/split型字典的相关检查
ASSERT_CONSISTENT(a);
return 0;
}
// update字典
int
PyDict_Update(PyObject *a, PyObject *b)
{
// update字典主逻辑，依次传入2个字典，第三个参数代表是否覆盖（0-不覆盖，1-覆盖，2-有相同key则报错）
return dict_merge(a, b, 1);
}
迭代器
迭代原理
通用迭代器的本质（有些特殊对象会根据自身迭代特点，实现特定格式的迭代器，这里主要介绍最常用的迭代器）就是在内部定义了一个索引，代表迭代到的位置，然后再将一个指针指向要迭代的序列（同时对序列引用+1），当进行next遍历时则取出当前序列对应索引位置的值，并将索引+1，源码如下：
// 迭代器定义
typedef struct {
PyObject_HEAD
// 迭代到的位置索引
Py_ssize_t it_index;
// 指向迭代的序列
PyObject *it_seq; /* Set to NULL when iterator is exhausted */
} seqiterobject;
// 创建一个迭代器
PyObject *
PySeqIter_New(PyObject *seq)
{
seqiterobject *it;
if (!PySequence_Check(seq)) {
PyErr_BadInternalCall();
return NULL;
}
it = PyObject_GC_New(seqiterobject, &PySeqIter_Type);
if (it == NULL)
return NULL;
// 初始化索引为0
it->it_index = 0;
// 对指向的序列引用+1
Py_INCREF(seq);
// 指向要迭代的序列
it->it_seq = seq;
_PyObject_GC_TRACK(it);
return (PyObject *)it;
}
// next逻辑
static PyObject *
iter_iternext(PyObject *iterator)
{
seqiterobject *it;
PyObject *seq;
PyObject *result;
assert(PySeqIter_Check(iterator));
it = (seqiterobject *)iterator;
seq = it->it_seq;
if (seq == NULL)
return NULL;
if (it->it_index == PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"iter index too large");
return NULL;
}
// 取出序列中对应索引的值
result = PySequence_GetItem(seq, it->it_index);
if (result != NULL) {
// 索引+1
it->it_index++;
return result;
}
if (PyErr_ExceptionMatches(PyExc_IndexError) ||
PyErr_ExceptionMatches(PyExc_StopIteration))
{
PyErr_Clear();
it->it_seq = NULL;
Py_DECREF(seq);
}
return NULL;
}
例如list转迭代器时，会将list的引用计数+1，并在内部维护一个变量存放当前索引的位置，当对list迭代完成时，会将list的引用计数-1，从而释放list，举例：
class MyList(list):
def __del__(self):
print("list被回收...")
l = MyList([1,2,3])
# 迭代器使用到了list，因此list的引用+1
it = iter(l)
# list的引用-1
del l
# 迭代list
for i in it:
print(i)
# list迭代完成，list引用-1
print("end...")
# 可以看到list的回收在end之前，即迭代器完成了对list的全部迭代以后，就会释放list，即使后面还会用到这个迭代器
print(it)
# 1
# 2
# 3
# list被回收...
# end...
# <list_iterator object at 0x000002530C65DE80>
迭代器其他接口
python中为通用迭代器提供了一些额外的接口，如：获取迭代器的长度、修改当前索引到的位置，源码如下：
// 获取迭代器长度
static PyObject *
iter_len(seqiterobject *it, PyObject *Py_UNUSED(ignored))
{
Py_ssize_t seqsize, len;
if (it->it_seq) {
if (_PyObject_HasLen(it->it_seq)) {
// 获取指向的序列长度
seqsize = PySequence_Size(it->it_seq);
if (seqsize == -1)
return NULL;
}
else {
Py_RETURN_NOTIMPLEMENTED;
}
// 迭代器的长度就是序列的长度减去当前迭代的位置索引
len = seqsize - it->it_index;
if (len >= 0)
return PyLong_FromSsize_t(len);
}
return PyLong_FromLong(0);
}
// 修改索引位置
static PyObject *
iter_setstate(seqiterobject *it, PyObject *state)
{
Py_ssize_t index = PyLong_AsSsize_t(state);
if (index == -1 && PyErr_Occurred())
return NULL;
if (it->it_seq != NULL) {
if (index < 0)
index = 0;
it->it_index = index;
}
Py_RETURN_NONE;
}
// 对外接口定义
static PyMethodDef seqiter_methods[] = {
{"__length_hint__", (PyCFunction)iter_len, METH_NOARGS, length_hint_doc},
{"__reduce__", (PyCFunction)iter_reduce, METH_NOARGS, reduce_doc},
{"__setstate__", (PyCFunction)iter_setstate, METH_O, setstate_doc},
{NULL, NULL} /* sentinel */
};
- 获取迭代器长度示例：
a = [1,2,3]
b = iter(a)
# 获取迭代器的剩余长度
print(b.__length_hint__())
next(b)
print(b.__length_hint__())
# 3
# 2
- 修改索引位置示例：
a = [1,2,3]
b = iter(a)
print(next(b))
# 迭代索引重新设为0
b.__setstate__(0)
print(next(b))
# 1
# 1
待更新...
