python集合对象底层实现源码分析PySetObject(set)

PySetObject

本文参考的是 3.8.0a0 版本的代码，详见  cpython 源码分析 基本篇

以后都在 github 更新，请参考 图解 python set

set 的实现方式和 dict 有点类似，但是稍微简单一些，我们来看看 set 的 memory layout

我们来看下 set_lookkey 这个函数

/* Objects/setobject.c57 - 133 行
*/static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
{/* 给定一个 key, 和一个 hash 值，返回这个 hash 在这个集合 so 里对应的 entry */setentry *table;setentry *entry;size_t perturb;size_t mask = so->mask;size_t i = (size_t)hash & mask; /* 把 hash 高于 mask 长度的位清零，留下长度低于 mask 位数 */size_t j;int cmp;entry = &so->table[i]; /* 取出集合的第 i 个 entry */if (entry->key == NULL) /* 如果第 i 个 entry 是空的值，直接返回 */return entry;perturb = hash;while (1) {/* 第i个 entry 不为空, 开始循环匹配，直到找到相等的 entry 为止 */if (entry->hash == hash) {/* 如果 entry 里的 hash 值相同，判断 key 是否相同 */PyObject *startkey = entry->key;/* startkey cannot be a dummy because the dummy hash field is -1 */assert(startkey != dummy);if (startkey == key) /* key 地址相同，返回entry */return entry;if (PyUnicode_CheckExact(startkey)&& PyUnicode_CheckExact(key)&& _PyUnicode_EQ(startkey, key)) /* key 为string，且 string 值相同，返回 entry */return entry;table = so->table;Py_INCREF(startkey);cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); /* 判断 entry 里存储的 key 和传入的 key 的结果 */Py_DECREF(startkey);if (cmp <0) /* start key 和 传入的 key 不相等 */return NULL;if (table != so->table || entry->key != startkey) /* unlikely */return set_lookkey(so, key, hash);if (cmp > 0) /* start key 和 传入的 key 相等 */return entry;mask = so->mask; /* 避免寄存器溢出? */}/* 当前的 entry 的 hash 值和 传入的 hash 值不匹配，需要重新寻找一个位置 关于 LINEAR_PROBES 的作用可以看下面的介绍*/if (i + LINEAR_PROBES <= mask) {/* 判断 i 后面是否还有 LINEAR_PROBES 个空间，如果有则进行横向搜索 */for (j = 0 ; j hash == 0 && entry->key == NULL)return entry;if (entry->hash == hash) {PyObject *startkey = entry->key;assert(startkey != dummy);if (startkey == key)return entry;if (PyUnicode_CheckExact(startkey)&& PyUnicode_CheckExact(key)&& _PyUnicode_EQ(startkey, key))return entry;table = so->table;Py_INCREF(startkey);cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);Py_DECREF(startkey);if (cmp <0)return NULL;if (table != so->table || entry->key != startkey)return set_lookkey(so, key, hash);if (cmp > 0)return entry;mask = so->mask;}}}/* 横向的 LINEAR_PROBES 无法搜索到对应的 entry, 重新进行 hash, 返回到 while 开始处 */perturb >>= PERTURB_SHIFT;i = (i * 5 + 1 + perturb) & mask;entry = &so->table[i];if (entry->key == NULL)return entry;}
}


LINEAR_PROBES

当当前hash对应的 entry 的值不匹配时，传统的思路，直接重新生成一个 hash 值，在对应的新的 hash 值上找到一个新的位置，但是这样做的话对 cpu 的 cache 影响较大，如果两个位置间隔过于分散/随机，cpu 这一次读取了这个 entry 和附近的entry 到 cache 中，下一次又需要重新读取，浪费 cpu cycle

当前的算法引入一个 LINEAR_PROBES，在当前 entry 向前 LINEAR_PROBES 个位置进行寻找，如果找不到才重新进行 hash 计算，以提高 cpu cache 的稳定性，所以在 set 的 hash entry 是随机值和连续值的结合体

static int set_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash): Objects/setobject.c 137-258行，经历和上边代码注释的 set_lookkey 函数相似的搜索过程，找对已经有值/空的 entry, 并把 entry 设置为传入的 key 的过程

static void set_insert_clean(setentry *table, size_t mask, PyObject *key, Py_hash_t hash): Objects/setobject.c 268-293行，找到一个空的 entry, 并把 key 插入 

下面我们来看下  set_table_resize

/* Objects/setobject.c303 - 381 行
*/
static int
set_table_resize(PySetObject *so, Py_ssize_t minused)
{setentry *oldtable, *newtable, *entry;Py_ssize_t oldmask = so->mask;size_t newmask;int is_oldtable_malloced;setentry small_copy[PySet_MINSIZE];assert(minused >= 0);/* 找到第一个大于 minused 的值 */size_t newsize = PySet_MINSIZE;while (newsize <= (size_t)minused) {newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1.}/* 给新的表创建空间 */oldtable = so->table;assert(oldtable != NULL);is_oldtable_malloced = oldtable != so->smalltable;if (newsize == PySet_MINSIZE) {/* 我们在进行缩小 set 的操作 */newtable = so->smalltable;if (newtable == oldtable) {if (so->fill == so->used) {/* fill 和 used 相等，没有被标记删除的数据，不需要做任何操作了 */return 0;}/* 把 so->table 临时拷贝到 small_copy 中，并把 oldtable 指向 small_copy */assert(so->fill > so->used);memcpy(small_copy, oldtable, sizeof(small_copy));oldtable = small_copy;}}else {newtable = PyMem_NEW(setentry, newsize);if (newtable == NULL) {PyErr_NoMemory();return -1;}}/* 清空 newtable */assert(newtable != oldtable);memset(newtable, 0, sizeof(setentry) * newsize);so->mask = newsize - 1;so->table = newtable;/* 利用上面的 set_insert_clean 把非标记成删除数据的 key 全部复制到新的 table 上 */newmask = (size_t)so->mask;if (so->fill == so->used) {for (entry = oldtable; entry <= oldtable + oldmask; entry++) {if (entry->key != NULL) {set_insert_clean(newtable, newmask, entry->key, entry->hash);}}} else {so->fill = so->used;for (entry = oldtable; entry <= oldtable + oldmask; entry++) {if (entry->key != NULL && entry->key != dummy) {set_insert_clean(newtable, newmask, entry->key, entry->hash);}}}if (is_oldtable_malloced)PyMem_DEL(oldtable);return 0;
}


static int set_contains_entry(PySetObject *so, PyObject *key, Py_hash_t hash): Objects/setobject.c 382-391行，利用 set_lookkey 方法检查这个 key 是否在该 set 中 

static int set_discard_entry(PySetObject *so, PyObject *key, Py_hash_t hash): Objects/setobject.c 396-413行，把对应的 entry 标记为删除

static int set_add_key(PySetObject *so, PyObject *key): Objects/setobject.c 415-427行，调用 set_add_entry 把对应的 key 插入 set 的 table 中

之后的函数也很好理解，就不逐一说