python源码分析:list对象的实现

一、List对象的基石:

下面这个结构体囊括了python实现的list的所有信息:list中的内容信息与处理方法

typedef struct {

PyObject_VAR_HEAD

PyObject **ob_item;

Py_ssize_t allocated;

} PyListObject;

下面来分别解释上面的变量含义:

PyObject_VAR_HEAD

:在第一篇的对象实现中,我们知道只要是变长对象的共有内容

PyObject **ob_item:由于每个对象都是由PyObject指针来索引,而列表是存储若干对象,即存储若干指针

。因此,需要一个指针数组(存储指针的数组),即需要一个指针的指针来索引这个数组。

Py_ssize_t allocated:列表的总容量,由于python中的列表采用预申请的机制(什么叫预申请呢?下面会详细说明),所以才会出现总容量与使用容量的区别。

我们知道在PyObject_VAR_HEAD中有一个ob_size来指示变长对象中其元素的个数,那上面的这个allocated(表示列表总容量)不就多余了吗?

这就要从list的内存管理来理解了,当list添加一个元素时,并不是简单地扩充list一个元素的空间,这样子效率太低。那怎样?与文件系统的中的读磁盘块的预读思想是一样,即预申请内存。这样就好理解有两个变量来维护list的元素个数与空间容量了。

二、list对象的相关操作

list这种线性群式类型的数据的操作无外乎:置换、插入、删除、追加、查找、反转。

下面就让我们先看看,list对象的生成动作,然后依依对上述这些动作的核心部分进行剖析。

list对象都是从PyList_New函数生成的。

PyObject *

PyList_New(Py_ssize_t size)

{

。。。(检查操作:临界数据、数据合法性等操作

//python对池的运用真是到极致了,连list这种对象都有池

if (num_free_lists) //检查池中可用的list

{

 num_free_lists--;

op = free_lists[num_free_lists];

_Py_NewReference((PyObject *)op);//对其引用计数作初始化操作

}

 else

 {

 op = PyObject_GC_New(PyListObject, &PyList_Type);

 if (op == NULL)

 return NULL;

 }

上面这部分是生成list对象本身的操作('本身'意味着还要生成list额外的部分),可以看到python用到池了。但是在初始化时,那个free_list_num=0。也就是说,池中没有现成的list对象,因此需要调用PyObject_GC_New来生成一个list对象。唉?那池子里没有东西,还缓存什么呢?别急,后面就会看到,'用时生成'的另类使用方法。

if (size <= 0)

op->ob_item = NULL;

 else

 {

op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);

if (op->ob_item == NULL) //申请失败

{

Py_DECREF(op);//既然失败了,就不用这个,减少引用计数,以备GC回收

return PyErr_NoMemory();

}

//初始为0

//也就是说,最初生成的list其元素指针空间全都是NULL,有木有!!

memset(op->ob_item, 0, nbytes);

}

上面这部分代码呢,就是我们说的生成list对象额外部分的代码:list里存放的元素对象啊!

由于listob_itme存放的是PyObject指针,所以list并不关心元素的类型。

 下面我就对list的最核心的两个操作进行剖析(因为其它大部分操作都是基于两个操作):插入与删除。而这两个操作都用了一个核心函数:list_resize。这里可以看到始终贯穿python的设计思想:提前预知,提前处理

list_resize的关键代码,

。。。。

if (allocated >= newsize && newsize >= (allocated >> 1))

{

assert(self->ob_item != NULL || newsize == 0);

self->ob_size = newsize;

return 0;

}

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

// 新大小的1/8 + 3(新大小小于9)否则为6

new_allocated += newsize;

。。。。

每当来了一个新要求的大小(比如插入操作中的原大小+1,或删除操作中原大小-1):newsize,这时python并不直接对list的空间进行调整。而是作个比较,若新要求的大小在总容量之下,总容量的一半之上则,不进行调整。

若大于总容量了,那就得扩张(不够使的了);若小于总容量的一半了,就得缩小(优化内存使用率)。接下来就要上演精彩之处了,前面说了不能简单的扩张与缩小一个单位,这样势必会效率低下,从数学的角度就是线性增长与缩小,很显然,我们需要来个非线性的操作。

先从增长来看,当每次newsize大于总容量allocated时,基于newsize新增加的部分就是:

(newsize >> 3) + (newsize < 9 ? 3 : 6)

显然这是关于newsize的一个函数。

list增长到allocated指明的最大容量时,就进行一次'跳跃'式的增长,而这个'跳跃'的高度由newsize(如果放在这个函数中,就是当前的allocated)的大小决定,容量越大,增长的也越大。

再从缩小来看,当newsize小于allocated/2时,意味着需要缩小空间大小了(节约内存)。

该缩小多少呢,同样是基于上面那个函数。由它计算出一个增量来,在什么基础上增呢?

allocated/2,对就是在这个基础上,因为一旦由于删除操作导致newsize恰好小于allocated/2时,就会执行缩小list空间大小的操作。这样,即节省了内存,又不至于减少内存过少,导致效率降低(想像一下,如果每次小于allocated/2时,就缩小为allocated/2,那么如果对于那么删除后立即执行插入操作效率就很不理想了。)

以上这个策略,可以实现不会过去频繁地调用realloc这个低效率的函数。

对于反转这个操作,之前一直以为list是用一种链表与数组的组合结构实现,因此只要调换一下头指针即可。由于list就是用数组实现,因此对于反转这种操作,只能老老实实地进行一一对换实现反转。但是由于list存储的全部是元素的对象指针,因此其对换操作对任何类型的元素都是pyobject指针的对换,因此效率还是可以忍受的,复杂度为O(n/2)

二、list池的实现

好了,现在到了揭密list池实现内幕的时刻了,我们上面看到在生成一个list对象时,先看看池中有没有空闲的list。我们知道在python虚拟机初始化时那个free_lists里全部是空的,而且那个free_list_num=0。就好奇了,池子不放list对象,就是一个好看的空池子,没什么实际价值。下面让我们看看list的销毁函数:list_dealloc就晓得了。

static void

list_dealloc(PyListObject *op)

{

Py_ssize_t i;

PyObject_GC_UnTrack(op);

Py_TRASHCAN_SAFE_BEGIN(op)

if (op->ob_item != NULL) {

i = op->ob_size;

while (--i >= 0) {

Py_XDECREF(op->ob_item[i]);

}

PyMem_FREE(op->ob_item);

 }

list的生成我们知道了,list对象其实是分两部分:list对象自身与存储其中的元素群。上面这段代码,便是销毁元素群的操作。最后一个PyMem_FREE(op->ob_item)list的对象指针空间给释放了。没了,全没了,list的一切与元素相关的信息都没了。

if (num_free_lists < MAXFREELISTS && PyList_CheckExact(op))

free_lists[num_free_lists++] = op;

else

op->ob_type->tp_free((PyObject *)op);

接下来该处理list对象本身了,唉!看见了,free_listslist的池了。哦!原来这些该销毁的list没有真正销毁而是进了池子,等待下次重新利用,妙!

当然,若池子满仓了,还是不得不面临被推出斩首的下场。

Py_TRASHCAN_SAFE_END(op)

}

发表评论