Python列表对象实现原理

新媒体管家

关键时刻，第一时间送达！

Python中的列表基于PyList 实现，列表支持元素的插入、删除、更新操作，因此PyList 是一个变长对象（列表的长度随着元素的增加和删除而变长和变短），同时它还是一个可变对象（列表中的元素根据列表的操作而发生变化，内存大小动态的变化）。

PyList 的定义：

咋一看PyList 对象的定义非常简单，除了通用对象都有的引用计数（ob_refcnt）、类型信息（ob_type），以及变长对象的长度（ob_size）之外，剩下的只有ob_item，和allocated，ob_item是真正存放列表元素容器的指针，专门有一块内存用来存储列表元素，这块内存的大小就是allocated所能容纳的空间。

alloocated是列表所能容纳的元素大小，而且满足条件：

0

len(list) == ob_size

ob_item == NULL 时 ob_size == allocated == 0

列表对象的创建

Pylist 对象的是通过函数PyList_New创建而成，接收参数size，该参数用于指定列表对象所能容纳的最大元素个数。

创建过程大致是：

检查size参数是否有效，如果小于0，直接返回NULL，创建失败

检查size参数是否超出Python所能接受的大小，如果大于PY_SIZE_MAX（64位机器为8字节，在32位机器为4字节），内存溢出。

检查缓冲池free_list是否有可用的对象，有则直接从缓冲池中使用，没有则创建新的PyList ，分配内存。

初始化ob_item中的元素的值为Null

设置PyList 的allocated和ob_size。

PyList 对象的缓冲池

free_list是PyList 对象的缓冲池，其大小为80，那么PyList 对象是什么时候加入到缓冲池free_list的呢？答案在list_dealloc方法中：

当PyList 对象被销毁的时候，首先将列表中所有元素的引用计数减一，然后释放ob_item占用的内存，只要缓冲池空间还没满，那么就把该PyList 加入到缓冲池中（此时PyList 占用的内存并不会正真正回收给系统，下次创建PyList 优先从缓冲池中获取PyList ），否则释放PyList 对象的内存空间。

列表元素插入

设置列表某个位置的值时，如“list[1]=0”，列表的内存结构并不会发生变化，而往列表中插入元素时会改变列表的内存结构：

相比设置某个列表位置的值来说，插入操作要多一次PyList 容量大小的调整，逻辑是list_resize，其次是挪动where之后的元素位置。

满足allocated >= newsize && newsize >= (allocated /2)时，简单改变list的元素长度，PyList 对象不会重新分配内存空间，否则重新分配内存空间，如果newsizeallocated，就会扩大内存空间。当newsize==0时内存空间将缩减为0。

总结

PyList 缓冲池的创建发生在列表销毁的时候。

PyList 对象的创建分两步：先创建PyList 对象，然后初始化元素列表为NULL。

PyList 对象的销毁分两步：先销毁PyList 对象中的元素列表，然后销毁PyList 本身。

PyList 对象内存的占用空间会根据列表长度的变化而调整。

参考：

list .h

list .c

来自：LiuZhiJun

https://foofish.net/python-list-implements.html

程序员共读整理发布，转载请联系作者获得授权