Python源码剖析

由于python很多地方都用字典类型实现，对速度要求高，所以： 1、python的字典通过散列表实现，搜索的时间复杂读为O(1)（C++的STL的map是用红黑树来实现，搜索的时间复杂度为O(log2N)） 2、通过开放定址法处理冲突 （SGI STL的散列map通过开链法处理冲突） 开放定址法在发生冲突时，通过探测函数继续寻找可用的节点，直到找到可用的为止，这就形成了多条以探测函数为索引的探测链。 则删除节点时，不能直接去除，而只能做标记（伪删除）。否则会打断所在的探测链，使得其后面的探测链节点不能被索引到。 每个节点entry的结构： typedef struct { /* Cached hash code of me_key. Note that hash codes are C longs. * We have to use Py_ssize_t instead because dict_popitem() abuses * me_hash to hold a search finger. */ Py_ssize_t me_hash; PyObject *me_key; PyObject *me_value; } PyDictEntry; 每个entry都有三种状态： Unused：me_key == NULL && me_value == NULL Active： me_key != NULL && me__key != dummy && me_value != NULL Dummy：me_key == dummy && me_value == NULL 字典对象的定义： typedef struct _dictobject PyDictObject; struct _dictobject { PyObject_HEAD Py_ssize_t ma_fill; /* # Active + # Dummy */ Py_ssize_t ma_used; /* # Active */ /* The table contains ma_mask + 1 slots, and that's a power of 2. * We store the mask instead of the size because the mask is more * frequently needed. */ Py_ssize_t ma_mask; /* ma_table points to ma_smalltable for small tables, else to * additional malloc'ed memory. ma_table is never NULL! This rule * saves repeated runtime null-tests in the workhorse getitem and * setitem calls. */ PyDictEntry *ma_table; PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash); PyDictEntry ma_smalltable[PyDict_MINSIZE]; }; 每个字典对象都有PyDict_MINSIZE（默认为8）个初始申请了的节点的ma_smalltable，ma_table开始会指向ma_smalltable 哈希函数lookdict： 通过直接把key和ma_mask做与运算求得哈希值，其中的技巧(trick)： ma_mask是散列表容量减一，表示散列表索引的最大值(0~ma_mask) 把key和ma_mask做与运算，得到的值肯定小于等于ma_mask，则索引值肯定在散列表内 散列表容量都设为2的幂，使得ma_mask的二进制位肯定都是1，则可以减少与运算得到的冲突，即： 如果不全为1，例如ma_mask是110，则对于key为10和11会得到相同的索引值，因为最低为被掩盖，索引值最低位肯定为0，增加了冲突率 在搜索时，用freeslot记录搜索到的dummy节点， 在搜索到key相同的节点前搜索到Unused节点时，如果freeslot不为空，即之前找到一个可用的dummy节点，则返回这个freeslot的节点，否则返回Unused节点 散列表装载率大于2／3时，发生冲突的概率会大大增加 缓存池 PyDictObject也使用跟PyListObject一样的缓存池机制：回收已申请的dict对象，来给新创建的dict对象用

Python 拥有两套垃圾回收机制。除了引用计数，还有个专门处理循环引用的 GC。 通常提到垃圾回收时，都是指这个 "Reference Cycle Garbage Collection"。 能引发循环引用用问题的，都是那种容器类对象，比如 list、set、object 等。对于这类对象，虚拟机在为其分配内存时，会额外添加⽤用于追踪的 PyGC_Head。这些对象被添加到特殊链表里，以便GC 进行管理。 同 .NET、JAVA 一样，Python GC 同样将要回收的对象分成 3 级代龄。GEN0 管理新近加入的年轻对象，GEN1 则是在上次回收中依然存活的对象，剩下 GEN2 存储的都是生命周期极长的家伙。每级代龄都有一个最大容量阀值，每次 GEN0 对象数量超出阀值时，都将引发垃圾回收操作。 =================================================== 包含 __del__ 方法的循环引用对象，永远不会被 GC 回收，直至进程终止。 *因 IPython 对 GC 存在干扰，对GC的测试最好在原生 shell 中进行。 *连空的__del__也不行，GC就是没办法！ =================================================== 其他有可能影响垃圾回收的因素： *对象变量名，Python的内存回收顺序与字典先后顺序有关，如官网说：

==================================================== 对于不能处理的__del___，Python的实现过程是这样的： *将所有在unreachable链表当中的带有__del__方法的对象及其包含的子对象放到finalizer链表当中：

gc_list_init(&finalizers);
move_finalizers(&unreachable, &finalizers);
move_finalizer_reachable(&finalizers);

*接下来在delete_garbage里调用unreachable链表当中的对象的tp_clear方法，该方法会将引用环打破，使得对象能够正常析构掉。

m += handle_weakrefs(&unreachable, old); 
delete_garbage(&unreachable, old);

*所有的GC回收也在这里完成了，接下来还有一部分代码是统计成功回收的对象个数，统计finalizers带有里面__del__方法无法回收的垃圾对象 个数，并且将finalizers所有对象移动到garbage这个列表当中，留给程序设计者去决定怎么释放这些对象。

一个Code Block算一个名字空间，一个Code Block指一个名字 空间或者作用域 一个名字空间对应编译出一个PyCodeObject，对应一个pyc文件 PyCodeObject是python的编译结果， 运行结束后，可以把一个PyCodeObject保存为pyc文件，下次运行可以直接从pyc文件中读取该PyCodeObject，而不用再编译 pyc文件只是PyCodeObject的硬盘表现 /* Bytecode object */ typedef struct { PyObject_HEAD int co_argcount; /* #arguments, except *args */ int co_nlocals; /* #local variables */ int co_stacksize; /* #entries needed for evaluation stack */ int co_flags; /* CO_..., see below */ PyObject *co_code; /* instruction opcodes */ PyObject *co_consts; /* list (constants used) */ PyObject *co_names; /* list of strings (names used) */ PyObject *co_varnames; /* tuple of strings (local variable names) */ PyObject *co_freevars; /* tuple of strings (free variable names) */ PyObject *co_cellvars; /* tuple of strings (cell variable names) */ /* The rest doesn't count for hash/cmp */ PyObject *co_filename; /* string (where it was loaded from) */ PyObject *co_name; /* string (name, for reference) */ int co_firstlineno; /* first source line number */ PyObject *co_lnotab; /* string (encoding addr<->lineno mapping) See Objects/lnotab_notes.txt for details. */ void *co_zombieframe; /* for optimization only (see frameobject.c) */ PyObject *co_weakreflist; /* to support weakrefs to code objects */ } PyCodeObject; co_code是这个PyCodeObject的字节码 co_consts记录这个PyCodeObject内的所有常量对象（指除了PyStringObject的所有对象，PyStringObject保存在co_names和 co_varnames），所以这里包内了这个PyCodeObject中嵌套的PyCodeObject co_lnotab是字节码指令在源码中的偏移h WFILE结构体： typedef struct { FILE *fp; int error; /* see WFERR_* values */ int depth; /* If fp == NULL, the following are valid: */ PyObject *str; char *ptr; char *end; PyObject *strings; /* dict on marshal, list on unmarshal */ int version; } WFILE; 其中的strings是用于管理intern的PyStringObject的， 在保存PyStringObject时，strings是dict对象，记录intern了的PyStringObject的值到一个索引值的映射， 读取PyStringObject时，string是一个list对象，记录已经读到的intern了的PyStringObject索引和它内容的关系 字节码： 字节码定义在opcode.h，大于90的是有入参的字节码 可以通过dis.dis来解析pyc文件的字节码： 第一列是字节码对应pcy文件的第几行 第二列是字节码在co_code的偏移 第三列是当前的字节码 第四列是当前字节码需要的参数

作者使用的是Python 2.5的源码，与现在我用的（2.7.3）略有不同。 比如在int_print中添加PyObject_Print的部分，书中是放在fprintf(fp, "%ld", v->ob_ival)一句前面——后来的Python在这一句前后添加了Py_BEGIN_ALLOW_THREADS和Py_END_ALLOW_THREADS两个宏，如果把PyObject_Print加在这两个宏之间运行时会出现"Fatal Python error: PyEval_SaveThread: NULL tstate"的错误，原因我暂时还不知道。解决方法就是把这句话放到第一个宏的前面。如下：

static int
int_print(PyIntObject *v, FILE *fp, int flags)
     /* flags -- not used but required by interface */
{
    long int_val = v->ob_ival;

    // Added by Yao Li
    PyObject* str = PyString_FromString("Blahblahblah...");
    PyObject_Print(str, stdout, 0);
    printf("\n");

    Py_BEGIN_ALLOW_THREADS
    fprintf(fp, "%ld", int_val);
    Py_END_ALLOW_THREADS
    return 0;
}