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 == NULLActive： me_key != NULL && me__key != dummy && me_value != NULLDummy：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的内存回收顺序与字典先后顺序有关，如官网说：

Warning Due to the precarious circumstances under which __del__() methods are invoked, exceptions that occur during their execution are ignored, and a warning is printed to sys.stderr instead. Also, when __del__() is invoked in response to a module being deleted (e.g., when execution of the program is done), other globals referenced by the __del__() method may already have been deleted or in the process of being torn down (e.g. the import machinery shutting down). For this reason, __del__() methods should do the absolute minimum needed to maintain external invariants. Starting with version 1.5, Python guarantees that globals whose name begins with a single underscore are deleted from their module before other globals are deleted; if no other references to such globals exist, this may help in assuring that imported modules are still available at the time when the __del__() method is called.

====================================================对于不能处理的__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这个列表当中，留给程序设计者去决定怎么释放这些对象。

作者使用的是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;
}

一个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中嵌套的PyCodeObjectco_lnotab是字节码指令在源码中的偏移hWFILE结构体：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的偏移第三列是当前的字节码第四列是当前字节码需要的参数