python源码解读_python代码解释

准备工作

Python整体结构

python架构主要分为三部分

• python文件
• python解释器
  • scanner词法分析，将代码且分为一个个token
  • parser词法分析建立AST
  • compiler根据AST生成python字节码
  • code Evaluator（虚拟机）执行这些字节码
• 运行时环境
  • 内建对象：list dict
  • 内存分配器：和malloc的一层接口
  • 运行状态信息：维护解释器在执行字节码时的不同状态

源码目录

include：python提供的所有头文件，用于用户通过c或c++来编写自定义模块
Lib：包含所有python自带标准库，用python编写
Modules：c编写的模块
parser：解释器Scanner和Parser部分
Objects：内建对象，list，dict，整数部分
Python：Compiler和执行引擎部分

一些tips: api中以NEW结尾当做c++ new, Malloc结尾的当做c mallor

Python对象

在python记住一句话，万物皆对象

Python内对象

人的视角: 对象是数据和基于这些数据操作的集合
计算机视角: 对象是一片被分配的内存空间(连续或离散)，可以在更高层次上作为一个整体来考虑，这个整体就是对象
python 所有内建类型对象是静态初始化的
python 一个对象一旦被创建，它内存中的大小就是不可变的（通过指针来定向变长数据）

PyObject

// object.h
#define PyObject_HEAD     \
    _PyObject_HEAD_EXTRA    \  // 一般情况下为空
    int ob_refcnt;  // 引用计数
    struct _typeobject *ob_type; //指定一个对象类型的类型对象
typedef struct _object{
    PyObject_HEAD
} PyObject;
1
2
3
4
5
6
7
8

每一个python对象除了PyObject之外还需要额外的内存，PyObject定义了必须要的数据比如PyIntObject

// intobject.h
typedef struct _object{
    PyObject_HEAD
    long ob_ival;
w} PyIntObject;
1
2
3
4
5

对于变长对象python有新的抽象

// object.h
#define PyObject_VAR_HEAD     \
    PyObject_HEAD    \
    long ob_size;       /一般指容器内元素数量
typedef struct _object{
    PyObject_VAR_HEAD
} PyVarObject;
1
2
3
4
5
6
7

类型对象

PyObject占用内存大小是对象的元信息，元信息和对象所属类型密切相关

// object.h
typedef struct _typeobject{
    PyObject_VAR_HEAD
    char *tp_name;  //print 信息"<module>.<name>"
    int tp_basicsize, item_size; //为了分配内存大小
    destructor tp_dealloc;
    printfunc tp_print;
    hashfunc tp_hash;
    ternaryfunc tp_call;
    ...
} PyTypeObject;
1
2
3
4
5
6
7
8
9
10
11

对象的创建

python对象的创建主要有两种方式

• C API(对于python的内建对象, 直接分配内存)
  • 泛型API AOL
  • 类型相关API COL
• 类型对象创建(用户自定义对象，因为不可能事先提供这类C方法)，大致流程如下
  会调用ob_type 所指定的PyTyoeObject类的tp_new方法，如果tp_new是NULL会追溯tp_base所指向的ob_type的tp_new方法，最终定位的tp_new（因为所有类继承object会有保底的tp_new方法）负责内存的申请(类似c++的new)
  之后通过tp_init初始化(类似c++的构造函数)

类型的类型

PyTypeObect 实际也是有ob_type属性的，其为PyType_Type(即type, 负责PyTypeObect的创建，即metaclass)
下图以int 为例说明了这些关系，也就是所知的python里面class,object,type的关系

Python中的整数对象

在Python的所有对象中，整数对象最简单且使用最频繁，故我们首先学习整数对象。关于整数对象的源码在Objects.intobjects.c中，整数对象是通过PyIntObject对象来完成的，在创建一个PyIntObject对象之后，就再也不能改变该对象的值了。定义为:

typedef struct {
    prObject_HEAD;
    long ob_ival;
}PyIntObject;
1
2
3
4

主要是PyIntObject和PyInt_Type，其他和普遍的PyObject, PyTyoeObject没什么，值得关注的有

• python2中稍小一点的数直接用C语言中的long去存储，稍大一点的数（超过long的承受范围）会使用python的long对象去存储，而python3不会作区分，统一用longObect去存储，实现用到了柔性数组，感兴趣可以查一下
• 小整形数组的内存池和大整形对象的内存链的维护,避免频繁malloc

在Python中，整数的使用是很广泛的，对应的，它的创建和释放也将会很频繁，那么如何设计一个高效的机制，使得整数对象的使用不会成为Python的瓶颈？在Python中是使用整数对象的缓冲池机制来解决此问题。使用缓冲池机制，那意味着运行时的整数对象并不是一个个独立的，而是相关联结成一个庞大的整数对象系统了。

小整形对象

// [intobject.c]
#ifndef NSMALLPOSINTS
#define NSMALLPOSINTS           257
#endif
#ifndef NSMALLNEGINTS
#define NSMALLNEGINTS           5
#endif
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
/* References to small integers are saved in this array so that they
   can be shared.
   The integers that are saved are those in the range
   -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
*/
static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在实际的编程中，数值比较小的整数，比如1,2,等等，这些在程序中是频繁使用到的，而Python中，所有的对象都存活在系统堆上，也就是说，如果没有特殊的机制，对于小整数对象，Python将一次次的malloc在堆上申请空间，然后free，这样的操作将大大降低了运行效率。

那么如何解决呢？Python中，对小整数对象使用了对象池技术。
那么又有一个问题了，Python中的大对象和小对象如何区分呢？嗯，Python中确实有一种方法，用户可以调整大整数和小整数的分界点，从而动态的确定小整数的对象池中应该有多少个小整数对象，但是调整的方法只有自己修改源代码，然后重新编译。

大整数对象

对于小整数，小整数对象池中完全的缓存PyIntObject对象，对于其它对象，Python将提供一块内存空间，这些内存空间将由这些大整数轮流使用，也就是谁需要的时候谁使用。

比如，在Python中有一个PyIntBlock结构，维护了一块内存，其中保存了一些PyIntObject对象，维护对象的个数也可以做动态的调整。在Python运行的某个时刻，有一些内存已经被使用，而另一些内存则处于空闲状态，而这些空闲的内存必须组织起来，那样，当Python需要新的内存时，才能快速的获得所需的内存，在Python中使用一个单向链表(free_list）来管理所有的空闲内存。

// [intobject.c]
#define BLOCK_SIZE      1000    /* 1K less typical malloc overhead */
#define BHEAD_SIZE      8       /* Enough for a 64-bit pointer */
#define N_INTOBJECTS    ((BLOCK_SIZE - BHEAD_SIZE) / sizeof(PyIntObject))

struct _intblock {
    struct _intblock *next;
    PyIntObject objects[N_INTOBJECTS];
};

typedef struct _intblock PyIntBlock;

static PyIntBlock *block_list = NULL;
static PyIntObject *free_list = NULL;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

创建
如果小整数对象池机制被激活，则尝试使用小整数对象池；如果不能使用小整数对象池，则使用通用整数对象池。
可以创建int的代码理解这两块的使用

// [intobject.c]
PyObject *
PyInt_FromLong(long ival)
{
    register PyIntObject *v;
#if NSMALLNEGINTS + NSMALLPOSINTS > 0 /* 尝试使用小整数对象池 */
    if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
        v = small_ints[ival + NSMALLNEGINTS];
        Py_INCREF(v);
        return (PyObject *) v;
    }
#endif
    if (free_list == NULL) {
        if ((free_list = fill_free_list()) == NULL)
            return NULL;
    }
    /* Inline PyObject_New */
    v = free_list;
    free_list = (PyIntObject *)v->ob_type;  /* 有一个看似不合适但是比较方便的地方，freelist会通过 ob_type存放可用空间的pyObject的地址(类似链表的next)，而不是 PyTyoeObject */
    (void)PyObject_INIT(v, &PyInt_Type);
    v->ob_ival = ival;
    return (PyObject *) v;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

下面是关于freelist的申请，和freelist和block_list的维护有关的代码

// [intobject.c]
static PyIntObject *
fill_free_list(void)
{
    PyIntObject *p, *q;
    /* 申请大小为sizeof（PyIntBlock）的内存空间，并链接到已有的block list中 */
    p = (PyIntObject *) PyMem_MALLOC(sizeof(PyIntBlock));
    ((PyIntBlock *)p)->next = block_list;
    block_list = (PyIntBlock *)p;
    /* 将PyIntBlock中的PyIntObject数组——objects转变成单向链表*/
    p = &((PyIntBlock *)p)->objects[0];
    q = p + N_INTOBJECTS;
    while (--q > p)
        q->ob_type = (struct _typeobject *)(q-1); /* 上一段代码中所提到的不合适的地方
    Py_TYPE(q) = NULL;
    return p + N_INTOBJECTS - 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这样，freelist会指向可以分配内存的地址，但是如果由之前分配的PyIntObject被释放了，freelist需要将被释放的地址重新使用才可以，这个是通过PyIntObect的析构函数来实现的

// [intobject.c]
static void
int_dealloc(PyIntObject *v)
{
    if (PyInt_CheckExact(v)) {   // 如果不是派生类这么执行，保证freelist的完整性
        v->ob_type = (struct _typeobject *)free_list;
        free_list = v;
    }
    else                        // 如果是派生类，则执行正常的析构流程
        v->ob_type->tp_free((PyObject *)v);
}
1
2
3
4
5
6
7
8
9
10
11

Python中的字符串对象

PyStringObject和PyString_Type

//[stringobject.h]
typedef struct{
    PyObject_VAR_HEAD
    long ob_shash;
    int ob_sstate;
    char ob_sval[1];
} PyStringObject;
//[stringobject.c]
PyTypeObject PyString_Type = {
    PyObject_HEAD_INIT(&PyType_Type)
    0,
    "str",
    sizeof(PyStringObject), // basic size
    sizeof(char), //itemsize
    // ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• ob_sval指的是一段长度为ob_size+1个字节的内存，必须满足ob_sval[ob_size] == ‘\0’
• ob_shash是缓存的该对象的hash值
• ob_sstate标记了该对象是否已经经过intern机制的处理

创建PyStringObject对象

//[stringobject.c]
// 从原生字符串创建
PyObject* PyString_FromString(const char *str) {
    register size_t size;
    register PyStringObejct *op;
    
    size = strlen(str);
    if (size > PY_SSIZE_T_MAX) {
        return NULL;
    }
    if (size == 0 && (op = nullstring )!= NULL) {  // intern机制： 和下面的一个分支都是为了缓存特定的对象，一个是空字符串，一个是单个字符字符串，第一次使用后会存在，之后不必再次创建PyObject对象（这些对象之前都被初始化成了NULL）
        return (PyObject *) op;
    }
    if (size == 1 && (op = characters[*str & UCHAR_MAX]) != NULL) {
        return (PyObject *) op;
    }
    op = (PyStringObject *)PyObject_MALLOC(sizeof(PyStringObject) + size); // 加上包含'\0'的额外内存
    PyObject_INIT_VAR(ob, &PyString_Type, size);
    op->ob_shash=-1;
    op->ob_sstate=SSTATE_NOT_INTERNED;
    memcpy(op->ob_sval, str, size+1);
    if (size==0) {
        PyObject *t = (PyObject *) op;
        PyString_InternInPlace(&t);
        op = (PyStringObject *) t;
        nullstring = op;
    } else if (size == 1) {
        PyObject *t = (PyObject *) op;
        PyString_InternInPlace(&t);
        op = (PyStringObject *) t;
        characters[*str & UCHAR_MAX] = op;
    }
    return (PyObejct *) op;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

字符串对象的intern机制

//[stringobject.c]
void PyString_InternInPlace(PyObject **p) {
    register PyStringObject *s = (PyStringObject *)(*p);
    PyObject *t;
    if (!PyString_CheckExact(s)) return;
    if (PyString_CHECK_INTERNED(s)) return;
    if (interned == NULL) {
        interned = PyDict_New();
    }
    t = PyDict_GetItem(interned, (PyObject *) s);
    if (t) {
        Py_INCREF(t);
        Py_DECREF(*p);
        *p = t;
        return;
    }
    PyDict_SetItem(interned, (PyObject *)s, (PyObject *)s);
    s->ob_refcnt -= 2;  // 减去key 和 value的引用
    PyString_CHECK_INTERNED(s) = SSTATE_INTERNED_MORTAL;  // 当析构时会根据这个属性，做出在interned中删除的操作
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

characters 是静态变量static PyStringObject *characters[UCHAR_MAX+1]; 开始都是NULL指针
= join字符串效率比 + 好， 因为PyStringObject 是不可变对象（varObject只是因为是变长的），两者申请内存不同
join 计算所有 PyStringObject 的size 得出需要分配的内存，一次分配
= 而concat(+) 需要分配n-1次内存，并且伴有析构

python中的List对象

// [listobject.h]
typedef struct{
    PyObject_VAR_HEAD
    PyObject **ob_item; // list[0] 实际就是ob_item[0]
    int allocated;   // 类似cap, 而ob_size是当前的元素数量
} PyListObject;

1
2
3
4
5
6
7

实际的操作和c++ vector类似略。有一个比较特别的是free_list的维护

// [listobject.c]
// list只有这一个创建入口
PyObject* PyList_New(int size) {
    PyListObject *op;
    size_t nbytes;
    nbytes = size * sizeof(PyObject *);
    if (nbytes / sizeof(PyObject *) != (size_t) size)
        return PyErr_NoMemory();
    if (num_free_lists) {
        num_free_lists--;  //记录当前free_lists的最大值
        op = free_lists[num_free_lists];
        _Py_NewReference((PyObejct *) op);
    } else {
        op = PyObject_GC_New(PyListObject, &PyList_Type);
    }
    if (size <=0)
        op->ob_item = NULL;
    else {
        op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
        memset(op->ob_item, 0, nbytes);
    }
    op->ob_size=size;
    op->allocated = size;
    return (PyObject *) op;
}

# define MAXFREELISTS 80
static PyListObject *free_lists[MAXFREELISTS];
static int num_free_lists=0;

// 创建和更新是在释放PyListObject时候维护的
static void list_dealloc(PyListObject *op){
    int i;
    if (op->ob_item!=NULL) {
        i=op->ob_size;
        while (--i>=0) {
            Py_XDECREF(op->ob_item[i]);
        }
        PyMem_FREE(op->ob_item);
    }
    if (num_free_lists < MAXFREELISTS && PyList_CheckExact(op))
        free_lists[num_free_lists++] = op; //保存当前释放元素的list
    else
        op->ob_type->tp_free((PyObject *) op);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

python中的Dict对象

实现是散列表，采用二次探针解决冲突

//[dictobject.h]
typedef struct{
    Py_ssize_t me_hash;
    PyObejct *me_key;
    Pyobject *me_value;
} PyDictEntry;

1
2
3
4
5
6
7

entry 会有三种状态 dummy状态是探测连上的元素伪删除后的状态

//[dictobject.h]
#define PyDict_MINSIZE 8
typedef struct _dictobject PyObject;
struct _dictobject{
    PyObject_HEAD
    Py_ssize_t ma_fill;   // active + dummy个数
    Py_ssize_t ma_used;   // active
    Py_ssize_t ma_mask;   // 所有的entry个数，之所以这样命名因为hash值会和这个值取&
    PyDictEntry *ma_table; // entry数量小于8个时会指向 ma_smalltable
    PyDictEntry *(*ma_lookup) (PyDictObject *mp. PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
}
1
2
3
4
5
6
7
8
9
10
11
12

其他包括缓冲池之类的会和list类似，lookup这块会多点东西。
python提供了两种搜索策略，一个lookdict一个lookdict_string

//[dictobhect.c]
static dictentry* lookdict(dictobject *mp, PyObejct *key, register long hash){
/** 返回永远不是NULL，而是一个me_value为NULL的entry可以直接被使用, 如果没找到但是有dummy的entry会返回这个dummy
*/
    register size_t i;
    register size_t perturb;
    register dictentry *freeslot;
    register size_t mask = mp->ma_mask;
    dictentry *ep0 = mp->ma_table;
    register dictentry *ep;
    
    register int restore_error;
    register int checked_error;
    register int cmp;
    PyObject *err_type, *err_value, *err_tb;
    PyObject *startkey;
    
    i = hash & mask;
    ep = &ep0[i];
    if (ep->me_key==NULL || ep->me_key == key)
        return ep;
    if (ep->me_key==dummy)
        freeslot = ep;
    else{
        if (ep->me_hash == hash){
            startkey = ep->me_key;
            cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); // 确定值是否相等，lookdict_string的差别在于这边使用的方法
            if (cmp > 0)
                return ep;
        }
        freelot = NULL;
    }
    // 二次探寻
    for （perturb=hash;;perturb >>= PERTURB_SHIFT{
        i = (i<<2) + i + perturb + 1;
        ep = &ep0[i & mask];
        if (ep->me_key == NULL)
            return freeslot == NULL ? ep: freeslot;
        if (ep->mp_key == key)
            return eq;
        if (ep->me_hash == hash && ep->me_key != dummy){
            startkey = ep->me_key;
            cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); 
            if (cmp > 0)
                return ep;
        }
        if (ep->me_key == dummy && freeslot == NULL)
            freeslot = ep;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50