Python列表对象实现原理详解

作者:FOOFISH-PYTHON之禅 时间:2022-09-07 10:24:58 

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


typedef struct {
# 列表对象引用计数
int ob_refcnt;
# 列表类型对象
struct _typeobject *ob_type;
# 列表元素的长度
int ob_size; /* Number of items in variable part */
# 真正存放列表元素容器的指针,list[0] 就是 ob_item[0]
PyObject **ob_item;
# 当前列表可容纳的元素大小
Py_ssize_t allocated;
} PyListObject;

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

  • 0 <= ob_size <= allocated

  • len(list) == ob_size

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

Python列表对象实现原理详解

列表对象的创建

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


// 列表缓冲池, PyList_MAXFREELIST为80
static PyListObject *free_list[PyList_MAXFREELIST];
//缓冲池当前大小
static int numfree = 0;
PyObject *PyList_New(Py_ssize_t size)
{
PyListObject *op; //列表对象
size_t nbytes; //创建列表对象需要分配的内存大小
if (size < 0) {
PyErr_BadInternalCall();
return NULL;
}
/* Check for overflow without an actual overflow,
* which can cause compiler to optimise out */
if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
return PyErr_NoMemory();
nbytes = size * sizeof(PyObject *);
if (numfree) {
numfree--;
op = free_list[numfree];
_Py_NewReference((PyObject *)op);
} else {
op = PyObject_GC_New(PyListObject, &PyList_Type);
if (op == NULL)
return NULL;
}
if (size <= 0)
op->ob_item = NULL;
else {
op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
if (op->ob_item == NULL) {
Py_DECREF(op);
return PyErr_NoMemory();
}
memset(op->ob_item, 0, nbytes);
}
# 设置ob_size
Py_SIZE(op) = size;
op->allocated = size;
_PyObject_GC_TRACK(op);
return (PyObject *) op;
}

创建过程大致是:

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

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

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

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

  5. 设置PyListObject的allocated和ob_size。

PYLISTOBJECT对象的缓冲池

free_list是PyListObject对象的缓冲池,其大小为80,那么PyListObject对象是什么时候加入到缓冲池free_list的呢?答案在list_dealloc方法中:


static void
list_dealloc(PyListObject *op)
{
Py_ssize_t i;
PyObject_GC_UnTrack(op);
Py_TRASHCAN_SAFE_BEGIN(op)
if (
i = Py_SIZE(op);
while (--i >= 0) {
Py_XDECREF(op->ob_item[i]);
}
PyMem_FREE(op->ob_item);
}
if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
free_list[numfree++] = op;
else
Py_TYPE(op)->tp_free((PyObject *)op);
Py_TRASHCAN_SAFE_END(op)
}

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

列表元素插入

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


static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
// n是列表元素长度
Py_ssize_t i, n = Py_SIZE(self);
PyObject **items;
if (v == NULL) {
PyErr_BadInternalCall();
return -1;
}
if (n == PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"cannot add more objects to list");
return -1;
}
if (list_resize(self, n+1) == -1)
return -1;
if (where < 0) {
where += n;
if (where < 0)
where = 0;
}
if (where > n)
where = n;
items = self->ob_item;
for (i = n; --i >= where; )
items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;
return 0;
}

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


// newsize: 列表新的长度
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated;
Py_ssize_t allocated = self->allocated;
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SIZE(self) = newsize;
return 0;
}
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
PyErr_NoMemory();
return -1;
} else {
new_allocated += newsize;
}
if (newsize == 0)
new_allocated = 0;
items = self->ob_item;
if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
PyMem_RESIZE(items, PyObject *, new_allocated);
else
items = NULL;
if (items == NULL) {
PyErr_NoMemory();
return -1;
}
self->ob_item = items;
Py_SIZE(self) = newsize;
self->allocated = new_allocated;
return 0;
}

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

Python列表对象实现原理详解

总结

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

  • PyListObject对象的创建分两步:先创建PyListObject对象,然后初始化元素列表为NULL。

  • PyListObject对象的销毁分两步:先销毁PyListObject对象中的元素列表,然后销毁PyListObject本身。

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

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

标签:python,列表,对象,原理
0
投稿

猜你喜欢

  • pytorch finetuning 自己的图片进行训练操作

    2023-03-17 00:46:53
  • python学生管理系统学习笔记

    2022-06-25 13:55:05
  • 深入SQL Server中char、varchar、text和nchar、nvarchar、ntext的区别详解

    2024-01-26 11:26:57
  • Python pygame 动画游戏循环游戏时钟实现原理

    2022-07-02 06:27:27
  • Django REST Swagger实现指定api参数

    2023-03-10 05:48:58
  • mysql如何通过当前排序字段获取相邻数据项

    2024-01-13 02:24:25
  • mysql设置远程访问数据库的多种方法

    2024-01-23 05:26:45
  • Python中处理Session和Cookie的方法

    2023-09-09 00:51:18
  • Python实现自动发消息自定义内容的操作代码

    2023-10-17 18:01:53
  • 详解Windows下源码编译PaddlePaddle

    2022-07-06 00:22:09
  • rs.getrows的使用方法

    2008-04-05 14:01:00
  • 关于Pytorch的MLP模块实现方式

    2021-12-19 03:28:22
  • Flask和Django框架中自定义模型类的表名、父类相关问题分析

    2022-04-04 00:23:17
  • mysql 获取时间方式

    2024-01-20 03:26:14
  • mysql5.5与mysq 5.6中禁用innodb引擎的方法

    2024-01-21 13:55:42
  • PHP 检查扩展库或函数是否可用的代码

    2023-07-22 23:34:34
  • Python搭建代理IP池实现获取IP的方法

    2023-01-05 05:16:35
  • Python机器学习之实现模型持久化与加载

    2022-06-06 14:24:13
  • python requests 库请求带有文件参数的接口实例

    2022-04-23 09:12:10
  • JavaScript实现点击改变图片形状(transform应用)

    2024-05-13 09:18:32
  • asp之家 网络编程 m.aspxhome.com