Python源码剖析——01内建对象

时间:2022-10-28 16:33:00

《Python源码剖析》笔记


第一章:对象初识


对象是Python中的核心概念,面向对象中的“类”和“对象”在Python中的概念都为对象,具体分为类型对象和实例化对象。

Python实现方式为ANSI C,其所有内建类型对象加载方式为静态初始化。

在Python中,对象一旦被创建其内存大小不可变,故可变对象其中会维护指向其他内存的指针。这是因为运行期间对象内存大小改变会影响其他内存的分布,造成很多不必要的麻烦。

1、PyObject和PyVarObject


[Include/object.h]

typedef struct _object {
_PyObject_HEAD_EXTRA
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
} PyObject;

PyObject是所有对象的一部分,每个对象都应包含它。

ob_refcnt是一个引用计数,以此完成垃圾回收机制。当引用计数为0时释放内存。

ob_type指针指向一个对象的类型对象,表示一个对象的类型。

_PyObject_HEAD_EXTRA在release模式下无意义,不解释。

[Include/object.h]

#define PyObject_VAR_HEAD      PyVarObject ob_base;

typedef struct {
PyObject ob_base;
Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;

所有可变长的对象都应包含PyVarObject,诸如字符串。

显然PyVarObject头部也包含一个PyObject,所以其实每个对象在内存中都有相同的头部,以此可统一其引用。

ob_size指明了容纳元素的个数。

2、对象创建及类型对象


Python对象的创建可分为两种:使用Python C API创建和使用类型对象创建。

C API分为两类:AOL(Abstract Object Layer)和COL(Concrete Object Layer)。前者可以创建任何Python对象,由Python内部机制确定最终调用什么,后者只能创建一个具体类型的对象。C API创建的对象都是内建对象,显然内建对象已经由Python直接定义,故直接分配内存即可。

对于用户自定义类型对象,可以使用类型对象创建。分配内存时会去找tp_new,如果为NULL,则去基类tp_base中找,如此递归下去一定能找到一个tp_new操作,即可申请内存。然后递归返回指向tp_init进行初始化。

由上我们可以发现,类型对象其实保存了每种对象的元信息(申请、释放内存,hash值,大小等等),通过类型对象我们可以实现很多该类型可以进行的操作。

而Python判断一个对象是否是类型对象是通过PyType_Type完成的,它是所有类型对象的父类对象。

3、对象行为规则


Python中定义了类型对象PyTypeObject,其包含很多信息,包括类型名tp_name,分配内存大小tp_basicsize、tp_itemsize,相关操作等等。

其中包含三个重要的指针tp_as_number,tp_as_sequence,tp_as_mapping指向三个函数族。他们规定了对象支持的数值行为、序列行为和关联行为。

4、Python的多态


上面说了,Python对象都有PyObject*变量,通过这个指针去维护这个对象。我们并不知道一个对象的类型是什么,但是PyObject中的ob_type指示了他的类型,那么就调用对应类型实现的操作,就可以实现多态。

比如 实现一个Print函数。

void Print(PyObject* obj){
obj->ob_type->tp_print(obj);
}

5、垃圾回收机制


在PyObject讲到了使用引用计数来实现垃圾回收机制,每增加或减少一次引用,使用宏给ob_refcnt加减1。ob_refcnt是一个32位整数,所以正常情况相下是足够的。如果ob_refcnt归0,那么析构这个对象。但是析构并不意味着释放内存,为了提高效率,Python使用了内存池管理内存,所以析构后只是归还到内存池。

对类型对象的引用不会加减引用计数,所以类型对象不会被析构。


第二章:整数对象


typedef struct {
PyObject_HEAD
long ob_ival;
} PyIntObject;

由上定义能看出,Python的整型其实就是封装的C的long。

1、小整数对象及对象池


在程序编码过程中,小整数对象是最常用到的,如果不能很好的处理,那么不断在堆上申请释放内存,程序的效率将大大降低。因此,Python给小整数对象开辟了一个专门的内存空间,对于小整数范围内的调用使用小整数对象池。

#ifndef NSMALLPOSINTS
#define NSMALLPOSINTS 257
#endif
#ifndef NSMALLNEGINTS
#define NSMALLNEGINTS 5
#endif
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
#endif

如上规定小整数的范围为[-NSMALLNEGINTS,NSMALLPOSINTS),其指针存放于small_ints*调用。

2、大整数对象及对象池


显然大整数太多了,不可能全都放到内存中,但是随便申请释放内存还是效率太低。

对此,Python提供了一块内存——通用整数对象池给大整数轮流使用。

#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;

Python在设计通用整数对象池时,令block_list指向一串PyIntBlock组成的单向链表(一直指向最新创建的PyIntBlock),free_list指向空闲可分配的内存空间。

每个PyIntBlock对象都包含一个数组用来存储PyIntObject对象。

如果对象池空闲内存不足,那么就申请一个新的PyIntBlock节点,创建节点时会将objects数组变为一个单向链表,将block_list指向这个新的PyIntBlock对象,free_list指向新的空闲内存空间。

设想现在如果某个已经占了内存的对象销毁了,如果不对他重新进行安排,那么按照上面的思路,这块内存永远不会利用第二次,等于内存泄露。所以在一个对象销毁时,我们要把这个没被占用的空闲块重新加到free_list中。由上我们已经知道free_list其实是一个空闲链表的头,那么我们把这个刚销毁的空闲块重新插入free_list的头部,就把它成功回收了。

以上可以看到,由通用整数对象池申请的内存在Python结束以前都不会释放,会一直留在内存池中。

3、小整数对象池初始化


小整数对象池在_PyInt_Init中完成初始化。但是,小整数的内存其实也是在block_list中维护的,把小整数插入free_list,指针指向内存就完成了初始化。

4、整数创建


先判断是否在小整数对象池的范围内,是就返回对应的对象;不是就插入到通用整数对象池中。


第三章:字符串对象


字符串是一个变长不可变对象,即在对象定义时其真实长度不定(相反Int在定义时就知道是long的长度),但是创建之后不能够增删其内部元素。

typedef struct {
PyObject_VAR_HEAD
long ob_shash;
int ob_sstate;
char ob_sval[1];
} PyStringObject;

ob_shash是字符串的哈希值缓存,在很多地方会用到(比如intern的键值)。

ob_sstate标记是否经过intern处理。

ob_sval其实是一个指向真正字符串内存的指针。

字符串长度记录在PyVarObject的ob_size中,所以字符串中间可能有'\0'。

1、创建


最常规的创建PyStringObject的方法为PyString_FromString。

Python会判断参数指针指向的字符串大小是否超出最大值,然后判断是否为空串(空串有专门定义的nullstring),然后memcpy将字符串拷贝到ob_sval并进行一些初始化。

2、intern


Python字符串的intern机制就是不重复申请内存存储相同的字符串。

intern的核心在于interned集合,interned集合本质是一个以(PyObject,PyObject)为键值对的字典PyDictObject,interned集合保存了已经创建过的PyStringObject。当创建一个字符串时,我们会先通过intern机制查找是否已经存在此字符串,有就直接返回已存在的该对象。在这过程中,其实Python总是会对每个字符串新创建一个PyStringObject对象,对于已经存在于intern的这个对象,在随后的查找中,新创建的PyStringObject对象引用计数会-1又很快会被销毁。

特别的,这里interned中插入的键值的引用计数是无效的,否则里面的对象永远不可能被销毁,所以在插入后Python会手动引用计数-=2。在对象被销毁时,会在interned删除。

字符串的intern机制由PyString_InternInPlace完成。首先进行类型检查,PyString_InternInPlace只支持PyStringObject对象。然后判断是否已经interned了,有则直接返回字典中的对象,临时创建的PyStringObject引用减一直接销毁;没有则进行intern。

3、字符缓冲池


static PyStringObject *characters[UCHAR_MAX + 1];

对于一个字节的字符对象,Python提供了字符缓冲池characters。当我们使用intern机制时,会将单个字符插入到缓冲池中。

4、Tip:+和join的效率问题


字符串对象是不可变对象,创建之后就不能改变元素长度。

+的实现是每两个字符串相加,就申请新的内存保存新的PyStringObject。如果使用+进行字符串对象的运算操作,那么对n个字符串+就要申请n-1此内存。

而使用join合并一个字符串列表,就能一次性申请最终总长度大小的字符串长度,那么只需要申请一次内存,效率大大提高。所以Python建议使用join代替+操作进行运算。


第四章:List对象


typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;

ob_item指向了真实元素列表的内存(数组)。

allocated指示出了当前容器的最大容量,而当前容器的长度在ob_size中已经定义。

List和C++中的vector的实现很像,初始方面,两者都是先开辟出一块固定大小的内存,而不是根据传进来的参数去申请对应个数,显然前者的效率更加高。

1、List的维护


设置元素前会进行索引的有效性,然后销毁内存原来的东西,替换成新的值。

插入元素时,需要考虑当前allocated是否足够容纳插入后的数量。这里和C++的vector处理几乎差不多。当allocated足够时,那么就后移元素空出插入位置,然后插入;如果容量不够,则申请一块新的内存,然后拷贝过去再插入。特别的,当newsize 小于 (allocated >> 1)时,Python还会收缩内存空间。

删除元素时,几乎又和vector一样。遍历整个List,然后判断迭代到的元素是否相同,相同,则使用list_ass_slice(本质就是使用memmove进行内存的移动)将后面整个剩余列表往前移动一格。

2、对象缓冲池


[listobject.c]

#ifndef PyList_MAXFREELIST
#define PyList_MAXFREELIST 80
#endif
static PyListObject *free_list[PyList_MAXFREELIST];
static int numfree = 0;

List也提供了一个对象池供申请内存使用,py2.5默认情况下维护80个PyListObject对象。

由上定义可知,free_list是一个指针数组,初始的时候为NULL。当free_list存在空闲块时,可以使用对象池中的空闲块存储PyListObject;否则,直接申请内存。

那么问题来了,初始化后free_list根本没分配内存,怎么得到内存空间?其实缓冲池的内存不是它自己去申请的,而是废物利用。在使用list_dealloc对PyListObject进行销毁时,会判断free_list满没满,没满就不直接free这个对象,而是把它析构之后放到free_list继续使用。

static void
list_dealloc(PyListObject *op)
{
...
if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
free_list[numfree++] = op;
else
Py_TYPE(op)->tp_free((PyObject *)op);
Py_TRASHCAN_SAFE_END(op)
}

第五章:Dict对象


PyDictObject对象是一种关联式容器,使用键值对(称为entry或者slot)关联。在Python本身的实现中大量采用了Dict,使用散列表(hash table)实现,搜索的时间复杂度可以达到O(1)。在冲突解决方面,Python采用了开放地址法,当发生冲突时使用二次探测函数得到新的值,去判断是否冲突,如此往复直到插入。这样,冲突的值就形成一个探测序列。

1、entry/slot


typedef struct {
Py_ssize_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictEntry;

entry定义如上,me_hash缓存散列值,me_key为键,me_value为值。entry分为三个状态:Unused,Active,Dummy。前面讲到了冲突时会沿着探测序列走,那么遇到Unused状态时会停止往下寻找。Unused表示无效,三个值都为NULL;Active表示有效,三个值都为对应的值;Dummy出现在删除某个entry时,因为探测序列节点连接前后,所以直接Unused会使得探测序列断开,所以给出一种Dummy状态,表示当前这个失效但是后面可能还有有效的,此时me_key指向dummy对象(dummy对象是一个PyDictObject对象,作为一种标志),me_value=NULL。

2、PyDictObject


#define PyDict_MINSIZE 8
typedef struct _dictobject PyDictObject;
struct _dictobject {
PyObject_HEAD
Py_ssize_t ma_fill; /* # Active + # Dummy */
Py_ssize_t ma_used; /* # Active */
Py_ssize_t ma_mask;
PyDictEntry *ma_table;
PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

ma_fill表示当前Active和Dummy的点加起来的总数。

ma_used表示Active状态的数量。

ma_mask表示entry的数量为ma_mask+1。

ma_lookup是搜索策略。

ma_table指向一片存储entry的内存。当entry数量少于PyDict_MINSIZE时,使用PyDictObject内部申请的ma_smalltable,ma_table指向这个数组;如果不足,则申请额外空间,再指向那片空间。故ma_table总是有效的。

3、搜索


dict的搜索策略分为两种:lookdict和lookdict_string,后者是前者的一个特化。

先讲lookdict。lookdict在搜索时,把hash值和ma_mask相与,那么得到的值就是一个能映射到ma_table里的值了。这样我们就得到了第一个散列值,如果第一个不符合,我们使用二次探测函数重新hash,沿着探测序列继续往下找。

[探测函数]
i = (size_t)hash & mask;
ep = &ep0[i]; [二次探测函数]
i = (i << 2) + i + perturb + 1;
ep = &ep0[i & mask];

找到时,我们返回这个entry;没找到,如果存在Dummy的情况我们就返回第一个Dummy废物利用(由freeslot指针进行维护);否则最后走到的Unused,这样做提高了后续插入的效率。

lookdict_string是lookdict的一个特化版本,因为lookdict是对PyObject通用,所以比较复杂。因为Python中大量使用了Dict实现,所以很有必要单独列出一个lookdict_string,删掉原版一些多余的内容并进行优化,大大提高Python的效率。

在比较key是否相同时,我们进行双重比较。先进行引用相同的比较,即直接查看两个对象是否就是同一块内存的对象,是则直接返回entry的value。否则进行值比较,先进行hash值比较,相同再进行详细的比较,值相同则返回entry的value。

4、插入和删除


插入时,先开始搜索,搜索成功则直接把原键的值替换成新的;搜索失败会返回一个Unused或者Dummy态的entry,修改即可。更新维护的数据。在插入后,要进行一步操作,调整维护的ma_table的大小。一般认为,当使用的数据大于总容量的2/3时(装载率>2/3),效率会大大降低,那么每次结束之后我们都要查看是否需要调整容量。需要调整容量的条件为:使用的是Dummy或者Unused态节点并且装载率>2/3。

调整容量不一定是变大,也有可能变小。调整后的容量只和Active态的数量有关。

if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))
return 0;
return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);

删除时同理,搜索找到需要删除的entry,原数据引用减一,然后转化到Dummy态。更新维护的数据。

5、对象缓冲池


[dictobject.c]

#ifndef PyDict_MAXFREELIST
#define PyDict_MAXFREELIST 80
#endif
static PyDictObject *free_list[PyDict_MAXFREELIST];
static int numfree = 0;

看定义和List的对象池几乎一样,其实就是一样。

初始时,对象池并没有内存。当一个PyDictObject要销毁时,会询问free_list是否需要,numfree没达到阈值就会把这个要销毁的PyDictObject的ma_table申请内存释放掉,初始化一下,然后把这块内存给对象池。