准备回顾一下python源代码，不过不准备说的太细，尽量勾勒框架，不引用代码。

0. python中对象的概念

python中所有东西都是对象，进一步地，这些对象可以分为类型对象（type）or实例对象，有时一个对象即可以是类型，也可以是实例。所有这些对象中，除了内置的类型对象外，别的都生存于堆上，内置的类型对象则静态分配内存。

每个对象头部都有一个PyObject_HEAD（其实对于某些需要被gc管理的对象，它的头部先为PyGC_Head，再为PyObject_HEAD）。变长对象在HEAD后还有一个ob_size表示变长对象元素个数的多少，非字节数。

类型的信息都在它的type对象里，源码中为struct _typeobject，也就是PyTypeObject。比如实例化一个类型，那会先找它的tp_new（找不到的话在父类找），在tp_new中根据该type的tp_basesize进行分配内存，再调用tp_init进行初始化。对类型的实例做运算，比如相加其实也是找type对象中相应的函数指针。type对象中的信息到后来基本都会在类型的dict中和相应的key对应起来。

1. int的实现

int比较简单，关键在于如何高效地实现。python首先有小整数对象。默认在[-5, 257)。如果超出范围则使用通用的缓冲池，对于大整数则有PyIntBlock，用来作缓冲池。一个block大小大概为1000个字节，去掉头部（8字节），可以存82个整数对象。block之间通过指针相连，首指针为block_list，free_list则维护着一条可以链表，free_list链表的下一项由未用的PyIntObject的ob_type来维持。

一些细节：当无可以用缓冲池可用时python会调用fill_free_list来创建一个新的block，并将其插入block_list，再把free_list指向这个block的objects中的最后一个元素。当某个block中的某个int被释放时，它将自己的ob_type指向free_list，并修改free_list等于它的地址，其实就是一个头部插入，这样把多个block间的objects数组联系起来防止出现内存泄漏。一个值得注意的地方是小整数对象池其实也是生活在block里面，在是整个python环境初始化的时候生成。这里可以看出，为int分配的内存是永远也不会被python释放的，所有的int对象使用的内存大小和同时存在的int数量的最大值有关。

2. string的实现

string复杂一些，它是变长对象。对变长对象内存的管理。每个string对象除了头部外还保存了hash值（ob_shash，避免重复计算，初始-1）、是否已经被intern机制处理过（ob_sstate）、指向实际内存的指针(ob_sval)，ob_sval指向的应该是一段ob_size+1长度的内存（为了兼容C，字符串要以'\0'结尾）。在从char *创建string时还是比较直接的，就是检查一些边界情况、初始化hash等，最后逐个拷贝char。python中有一个nullstring指向空字符串，通过intern机制共享，所以不会同时存在多个空字符串。

传统缓冲池。相当于int小整数缓冲池，对单个的char，python也会维持一个缓冲池。创建单个char的string时，如果缓冲池里已有，则直接返回。如果没有，根据char创建string，再对它进行intern，再存入缓冲池。

intern机制。python会维持一个dict，用来保存当前已经被创建的string，如果新创建的string已经在这个dict，也就是已经被intern机制处理过了，那么就会直接返回dict中的值。也就是说一般两个相同的字符串的id是相同的。要注意的是，无论字符串有没有存在于这个dict中，python都会创建一个新要string，原因是因为保存在dict中只能是PyObject，因此肯定要创建一个python对象。intern后的string有两种状态，mortal和immortal，区别在于后者永远不会被gc回收。

要提到的是，创建string时使用的是PyObject_Malloc开头的分配函数，一般来讲它不会每次都从os分配内存，而是从python维持的一个内存池中分配。

3. list的实现

list不仅是变长对象，还是可变对象。在变长头部之外PyListObject还保存了一个PyObject **ob_item指针，一个int allocated。ob_item就是指向实际成员的指针，allocated代表了list当前申请的内存能装多少个PyObject，变长头内的ob_size则代表list中已有多少个PyObject。当创建一个list时，需要指定list的大小（参数size），要申请的内存可以分为两部分，一个是list本身，一个是指向成员变量的指针。如果list缓冲池可用（numfree > 0)，那就从缓冲池中给list分配一块内存，否则使用PyObject_GC_NEW来分配空间（和string不同，因为list中的成员可以指向其它python对象，这个函数和python垃圾回收的三色标记法有关）。然后再根据size大小分配一段连续的内存来保存指向各个成员的指针，新创建的list中的ob_size和allocated都为size。

创建list后给list里的某个位置赋值比较简单，就是简单的設定指针而已。添加操作要复杂一些，首先会调整list的大小，使得allocate>=size>=allocate/2。如果该等式已经满足，那么不更改list大小，如果不满足的话通过new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize得出新的allocated大小，再通过PyMem_Resize来调整保存成员指针的内存。resize后则使用最简单的策略移动从插入到结尾的成员指针，再设置该位置上的成员。删除成员时实际删除后的也要进行resize操作，和插入时类似。实际删除的操作则由list_ass_slice来实现，它有两种用法，一是更改list中的某一段为特定的值，另一种就是删除list中的某一段。list中每删除一个元素都会造成内存拷贝。一个值得注意的细节是由于从list中删除或是更改的对象需要减少引用计数，但减少引用计数时又会循环调用一些list函数，可能会造成list索引值的破坏，因而函数中得用一个temp数组保留从list中剥离的成员，等删除工作完成，list结构已经确定的情况下再逐一减少其引用。

当list被销毁时，对其成员逐个减少引用，然后检查缓冲区是否已经满，如果没有的话就将该list放入缓冲区，这样下次再创建list的时候就不用为list对象本身再分配对象了。

4. dict的实现

python中的dict是用hash表实现，解决冲突的方法是开放定址法，即二次探测，删除时使用伪删除技术（顺便说下在一致性假设下，如果用k来表示hash表的使用率的话，那么一次成功查找需要的比较次数为1/k * ln(1/(1-k))，插入时的比较次数最多为1/(1-k)）。

在一个dict中，每个(key,value)对组成一个entry，entry中还另外存储了key的hash值。对每个entry来说有三种状态unused（key,value皆为NULL，初始状态），active（key,value不为NULL，存储了元素），dump（对应于伪删除技术，key=dummy,value=NULL）。dict实际上就是entry的集合，定义如下：

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。使用PyDict_New来创建一个新dict时，其实就是分配相应的内存，将ma_fill，ma_used设为0，ma_mask设为7（8-1），ma_table指向ma_smalltable，ma_lookup默认为lookdict_string。在实现dict时python也使用了缓冲池，方法和list基本一样。

ma_lookup这个函数指针确定了散裂函数和冲突发生时的二次散裂函数，在dict中进行搜索有两种方法，lookdict_string和lookdict，后一种是更一般的方法。由于python中dict用的非常广泛，而这些dict中大多数key都是string，因而专门提供了一个搜索方法来进行加速，其实两种方法的本质都是一样的。搜索的具体过程如下：1. 获得探测链中当前应该检测的entry；2. 如果是unused状态，那搜索失败，应该返回一个可用的（可以被设置值）的entry，所以如果freeslot不为空（之前找到了dummy态的entry）就返回freeslot指向的entry，否则返回当前entry；3. 如果entry为dummy态且freeslot未设置，则设置freeslot，继续查找下一个；4. 依次检查当前entry的key和查找的key是否引用相同、值相同，若不是继续查找下一个。需要注意的是，dict使用哪种方法进行查找取决于待查找的key，如果是string的话则利用lookdict_string，和本身已经有的entry中的key无关。

dict的插入和删除基于之前的搜索，很好理解。当插入时先搜索该key，得到一个entry，再根据它的状态来修改它达到插入的上目的。删除操作也类似。需要注意的是插入元素的时候，会检查ma_fill/(ma_mask+1)是否大于2/3，如果装载率的确大于这个值并且有unused或dummy的entry被填充的时候，就会调整dict的大小，新的大小最小为minsize=ma_userd*(ma_used>50000?2:4)，显然改变dict大小会造成内存移动，因此这时候可以丢弃dummy的entry。新的dict大小从8开始逐次*2增长，直到大于minsize。接下来就是一些初始化动作，逐个检查entry并插入新的dict等。

这段时间又懒下来了，加上事情也比较忙，完全荒废了这里啊，罪过罪过。

这一系列文章是我根据《Python源码剖析——深度探索动态语言核心技术》学习python源代码的笔记，书中分析的是python2.5的代码，我下载的是python2.6的，有些许不同，不过大致一样。

先来看看python总体的架构吧。如下图(从源码剖析中截图，以下如果未有说明的话都是从书中截的)。

在左边是python和各种模块、库及第三方模块。模块一般是由python编写而成，不过在一些对速度要求比较严格的地方，也可以用C写，python和C的兼容性是相当好的恩。不过这一块并不是学习的主要部分，它对应着python docs里的Library Reference，而书中主要讲解的是Language Reference的部分。图的右边是python的运行环境，可以理解为系统运行一个进程时堆栈，寄存器等所保存的上下文环境。中间是python虚拟机，所有的代码都是在它上面运行的。在虚拟机的上层，scanner, parser, compiler其实和一般的编译过程没有太大区别，只不是一般的C编译器最终是将代码翻译成机器码，再由操作系统作为运行环境来执行；而python则是把代码翻译成字节码，以python虚拟机来作为运行环境而执行。python解释器和python运行环境是我们学习的重点。

让我们从python中的对象开始吧。python中一切都是对象。从内建的int、string到用户自定义的class，这些都是对象。进一步的，它们的类型也是对象。对于一般的对象来说，它们是不能被静态初始化的，并且都是在堆上，但有一些例外，就是内建的类型对象，比如int类型这个对象，它们是被静态初始化并在栈上分配内存的。python中的对象一旦被创建，在内存中的大小就再也不变化了，这样是为了保证设计的简单性，其实这种思想在各种地方都是有体现，比如hbase对外提供的接口，也就是get, put, scan不多几个，如果在保证可扩展性和可靠性的前提下还要设计诸如关系型数据库中的那些比如事务性，原子性等，那将会相当复杂。

对象所对应的类型定义在object.h中。代码如下

typedef struct _object
{
    PyObject_HEAD
} PyObject;

#ifdef Py_TRACE_REFS
/* Define pointers to support a double-linked list of all live heap objects. */
#define _PyObject_HEAD_EXTRA       \
    struct _object *_ob_next;
    struct _object *ob_prev;

#define _PyObject_EXTRA_INIT 0, 0,

#else
#define _PyObject_HEAD_EXTRA
#define _PyObject_EXTRA_INIT
#endif

/* PyObject_HEAD defines the initial segment of every PyObject. */
#define PyObject_HEAD                  \
    _PyObject_HEAD_EXTRA           \
    Py_ssize_t ob_refcnt;                  \
    struct _typeobject *ob_type;

上面的代码可以简化为

typedef struct _object
{
    int ob_refcnt;
    struct _typeobject *ob_type;
} PyObject;

ob_refcnt是用来实现引用户数的gc。ob_type指向了这个对象的类型对象，换句话说，它存储了这个对象的类型。对象可以分为两种，一种是定长对象，比如int，另一种是变长的对象，比如list。对于前一种，只用在实际的对象中再分配一个固定的区域用来存储值就可以了，但这种方法对后一种对象就失效了，因此python中定义了表示变长对象的结构体。

#define PyObject_VAR_HEAD          \
    PyObject_HEAD                         \
    Py_ssize_t ob_size;

typedef struct
{
    PyObject_VAR_HEAD
} PyVarObject;

可以看出来，其实就是将一般的对象包装了一下，加了一个ob_size。表示所容纳的元素个数，比如一个list里面有5个string的话，那这个size就为5。从这里我们可以看出，只需要一个PyObject *指针就可以引用任何一个对象。这对于python实现各种语言特性很关键。接下来我们来看看_typeobject中到底有什么。

typedef struct _typeobject
{
    PyObject_VAR_HEAD
    const char * tp_name; /* For printing, in format "<module>.<name>" */
    Py_ssize_t tp_basicssize, tpitemsize; /* For allocation */

    /* Methods to implement standard operations */
    destructor tp_dealloc;
    printfunc tp_print;
    ....

    /* Method suites for stadard classes */
    PyNumberMethods *tp_as_number;
    PYSequenceMethods *tp_as_sequence;
    PyMappingMethods *tp_as_mapping;

    /* More stadard operations (here for binary compatibility) */
    hashfunc tp_hash;
    ....
} PyTypeObject;

首先可以看到，这个类型变量也是一个对象，因为它有PyObject_VAR_HEAD，接下来的tp_name是它的类型名。tp_basicsize和tb_itemsize给定了分配内存时的相关信息。在这个结构体中还主要定义了三类方法，一是基本操作，比如打印对象，析构对象等。一类是对于在用运算符做运算时所应该调用的函数，比如加减、取键值等等。还有一类比如使用hash(oneobject)时调用的函数。其实这个类中还有很多信息，不过为了简明起见，先列出这些。

我们已经知道，一切都是对象，每个对象都有类型。那么对一个int来说，它的类型是，这是一个对象，再精确一点，是一个类型对象，分配在栈上的静态初始化的对象，那么，这个类型对象的类型是什么呢？答案是。在源码中就是PyType_Type。

PyTypeObject PyType_Type =
{
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "type", /* tp_name */
    sizeof(PyHeapTypeObject), /* tp_basicsize */
    sizeof(PyMemberDef), /*tp_itemsize*/
    ...
}

看看整数对象是怎么和它联系起来的。

PyTypeObject PyInt_Type =
{
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "int",
    ...
}

下图可以更好地说明这个问题

python运行时整数对象及其类型之间的关系