2023年 1月 25日

python源码解读

文章目录

  • 准备工作
    • Python整体结构
    • 源码目录
  • Python对象
    • Python内对象
    • 类型对象
      • 对象的创建
      • 类型的类型
  • Python中的整数对象
    • 小整形对象
    • 大整数对象
  • Python中的字符串对象
    • PyStringObject和PyString_Type
    • 创建PyStringObject对象
    • 字符串对象的intern机制
  • python中的List对象
  • python中的Dict对象

准备工作

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_typetp_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

主要是PyIntObjectPyInt_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