c struct of python list and dict

python list和dict虽然好用,但是也有坑。

list

list对象c定义是指针数组:
python的list是变长的,并非等同于链表的变长,而是采用指针数组,保证了多种操作的性能平衡,同时支持元素类型的动态性。

1
2
3
4
5
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
  • PyObject_VAR_HEAD为变长对象头,其中的ob_size表示list长度
  • ob_item为容器,存储PyObject对象指针
  • allocated表示已分配多少存储空间

list的生命周期:

  • alloc,根据PyListObject free_lists里面的缓存情况和策略,判断是否创建list对象
  • 为ob_item分配内存
  • append操作,追加元素list.append(obj),根据ob_item预留空间策略判断是否resize,在ob_item尾部添加指针,指向obj
  • =操作,更新元素list[i]=obj,就是数组的指针指向新的value对象
  • insert操作,插入元素list.insert(obj),根据ob_item预留空间策略判断是否resize,查找插入点,将插入点后的元素向后移,在插入点增加指针,指向obj
  • remove操作,删除元素list.remove(obj),查找删除点,删除该位置的指针,将删除点后的元素向前移,根据ob_item预留空间策略判断是否resize
  • pop操作,弹出元素list.pop(obj),将尾部指针返回,并删除尾部指针,根据ob_item预留空间策略判断是否resize
  • 回收ob_item的内存
  • dealloc 根据PyListObject free_lists里面的缓存情况和策略,判断是否销毁list对象

list的append、pop性能优于insert、remove,list的slice操作和extends操作都会有resize。

dict

dict对象c定义是哈希表:
哈希表查找的时间复杂度为O(1),dict采用开放寻址法解决hash冲突,开放寻址法比拉链法能更好地利用CPU cache,cache命中率较高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct {
Py_ssize_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictEntry;
typedef struct _dictobject PyDictObject;
struct _dictobject {
PyObject_HEAD
Py_ssize_t ma_fill; /* # Active + # Dummy */
Py_ssize_t ma_used; /* # Active */
Py_ssize_t ma_mask; /* equal to size of ma_table - 1; calc index*/
PyDictEntry *ma_table;
PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
PyDictEntry ma_smalltable[PyDict_MINSIZE];
};
  • entry的Unused:me_key == me_value == NULL,即未使用的空闲状态
  • entry的Active:me_key != NULL, me_value != NULL,即该entry已被占用
  • entry的Dummy:me_key == dummy, me_value == NULL
  • PyObject_HEAD的ob_size用不上,dict没有长度
  • ma_fill记录Active + Dummy状态的entry数
  • ma_used记录Active状态的entry数
  • ma_mask等于slot总数 - 1
  • ma_table为容器,存储PyDictEntry对象指针
  • ma_lookup是搜索函数,因为Python中key不一定是String,所有搜索函数针对dict key做优化,当遇到string key使用lookdict_string,否则调用默认的lookdict
  • ma_smalltable为小字典容器(小于8个key-value)ma_smalltable,超出后再从内存分配空间

dict的生命周期:

  • alloc,根据PyDictObject free_lists里面的缓存情况和策略,判断是否创建dict对象,关联搜索方法lookdict_string
  • 为ma_table分配内存
  • set操作,添加元素dict[key]=val/dict.set(key, val),将key-val生成PyDictEntry object,检查冲突探测链不存在,计算哈希位置,如果发生冲突,通过二次探测算法,寻找下一个位置,直到找到可用位置,并根据ma_table预留空间策略决定是否resize,添加可用位置的指针,指向PyDictEntry object,并将该位置放入冲突探测链
  • set操作,更新元素dict[key]=val/dict.set(key, val),将key-val生成PyDictEntry object,检查冲突探测链存在,找到该位置,将指针指向新的PyDictEntry object
  • get操作,查找元素dict[key]/dict.get(key),遍历冲突探测链,找到该位置,返回该位置的指针指向的PyDictEntry object的value
  • pop操作,弹出元素dict.pop(key),遍历冲突探测链,找到该位置,返回该位置的指针指向的PyDictEntry object的value,删除对应指针,将PyDictEntry object从Active转换成Dummy,并根据ma_table预留空间策略决定是否resize
  • popitem,随机删除key-val,性能优于pop操作
  • del操作,删除元素del dict[key],遍历冲突探测链,找到该位置,删除对应指针和指向的PyDictEntry object,并根据ma_table预留空间策略决定是否resize
  • 回收ma_table的内存
  • dealloc 根据PyDictObject free_lists里面的缓存情况和策略,判断是否销毁dict对象

tuple、set的解构和list类似,tuple在list基础上加了不可更改限制,只能create,set是在list的基础上加了重复检测方法。