- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
在本篇文章当中主要给大家介绍 cpython 虚拟机当中针对列表的实现,在 Python 中,List 是一种非常常用的数据类型,可以存储任何类型的数据,并且支持各种操作,如添加、删除、查找、切片等,在本篇文章当中将深入去分析这一点是如何实现的.
在 cpython 实现的 python 虚拟机当中,下面就是 cpython 内部列表实现的源代码:
typedef struct {
PyObject_VAR_HEAD
/* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
PyObject **ob_item;
/* ob_item contains space for 'allocated' elements. The number
* currently in use is ob_size.
* Invariants:
* 0 <= ob_size <= allocated
* len(list) == ob_size
* ob_item == NULL implies ob_size == allocated == 0
* list.sort() temporarily sets allocated to -1 to detect mutations.
*
* Items must normally not be NULL, except during construction when
* the list is not yet visible outside the function that builds it.
*/
Py_ssize_t allocated;
} PyListObject;
#define PyObject_VAR_HEAD PyVarObject ob_base;
typedef struct {
PyObject ob_base;
Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;
typedef struct _object {
_PyObject_HEAD_EXTRA // 这个宏定义为空
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
} PyObject;
将上面的结构体展开之后,PyListObject 的结构大致如下所示:
现在来解释一下上面的各个字段的含义:
Py_ssize_t,一个整型数据类型.
ob_refcnt,表示对象的引用记数的个数,这个对于垃圾回收很有用处,后面我们分析虚拟机中垃圾回收部分在深入分析.
ob_type,表示这个对象的数据类型是什么,在 python 当中有时候需要对数据的数据类型进行判断比如 isinstance, type 这两个关键字就会使用到这个字段.
ob_size,这个字段表示这个列表当中有多少个元素.
ob_item,这是一个指针,指向真正保存 python 对象数据的地址,大致的内存他们之间大致的内存布局如下所示:
allocated * sizeof(PyObject *)
。 首先需要了解的是在 python 虚拟机内部为列表创建了一个数组,所有的创建的被释放的内存空间,并不会直接进行释放而是会将这些内存空间的首地址保存到这个数组当中,好让下一次申请创建新的列表的时候不需要再申请内存空间,而是直接将之前需要释放的内存直接进行复用即可.
/* Empty list reuse scheme to save calls to malloc and free */
#ifndef PyList_MAXFREELIST
#define PyList_MAXFREELIST 80
#endif
static PyListObject *free_list[PyList_MAXFREELIST];
static int numfree = 0;
创建链表的代码如下所示(为了精简删除了一些代码只保留核心部分):
PyObject *
PyList_New(Py_ssize_t size)
{
PyListObject *op;
size_t nbytes;
/* 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 *);
// 如果 numfree 不等于 0 那么说明现在 free_list 有之前使用被释放的内存空间直接使用这部分即可
if (numfree) {
numfree--;
op = free_list[numfree]; // 将对应的首地址返回
_Py_NewReference((PyObject *)op); // 这条语句的含义是将 op 这个对象的 reference count 设置成 1
} else {
// 如果没有空闲的内存空间 那么就需要申请内存空间 这个函数也会对对象的 reference count 进行初始化 设置成 1
op = PyObject_GC_New(PyListObject, &PyList_Type);
if (op == NULL)
return NULL;
}
/* 下面是申请列表对象当中的 ob_item 申请内存空间,上面只是给列表本身申请内存空间,但是列表当中有许多元素
保存这些元素也是需要内存空间的 下面便是给这些对象申请内存空间
*/
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();
}
// 对元素进行初始化操作 全部赋值成 0
memset(op->ob_item, 0, nbytes);
}
// Py_SIZE 是一个宏
Py_SIZE(op) = size; // 这条语句会被展开成 (PyVarObject*)(ob))->ob_size = size
// 分配数组的元素个数是 size
op->allocated = size;
// 下面这条语句对于垃圾回收比较重要 主要作用就是将这个列表对象加入到垃圾回收的链表当中
// 后面如果这个对象的 reference count 变成 0 或者其他情况 就可以进行垃圾回收了
_PyObject_GC_TRACK(op);
return (PyObject *) op;
}
在 cpython 当中,创建链表的字节码为 BUILD_LIST,我们可以在文件 ceval.c 当中找到对应的字节码对应的执行步骤:
TARGET(BUILD_LIST) {
PyObject *list = PyList_New(oparg);
if (list == NULL)
goto error;
while (--oparg >= 0) {
PyObject *item = POP();
PyList_SET_ITEM(list, oparg, item);
}
PUSH(list);
DISPATCH();
}
从上面 BUILD_LIST 字节码对应的解释步骤可以知道,在解释执行字节码 BUILD_LIST 的时候确实调用了函数 PyList_New 创建一个新的列表.
static PyObject *
// 这个函数的传入参数是列表本身 self 需要 append 的元素为 v
// 也就是将对象 v 加入到列表 self 当中
listappend(PyListObject *self, PyObject *v)
{
if (app1(self, v) == 0)
Py_RETURN_NONE;
return NULL;
}
static int
app1(PyListObject *self, PyObject *v)
{
// PyList_GET_SIZE(self) 展开之后为 ((PyVarObject*)(self))->ob_size
Py_ssize_t n = PyList_GET_SIZE(self);
assert (v != NULL);
// 如果元素的个数已经等于允许的最大的元素个数 就报错
if (n == PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"cannot add more objects to list");
return -1;
}
// 下面的函数 list_resize 会保存 ob_item 指向的位置能够容纳最少 n+1 个元素(PyObject *)
// 如果容量不够就会进行扩容操作
if (list_resize(self, n+1) == -1)
return -1;
// 将对象 v 的 reference count 加一 因为列表当中使用了一次这个对象 所以对象的引用计数需要进行加一操作
Py_INCREF(v);
PyList_SET_ITEM(self, n, v); // 宏展开之后 ((PyListObject *)(op))->ob_item[i] = v
return 0;
}
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated;
Py_ssize_t allocated = self->allocated;
/* Bypass realloc() when a previous overallocation is large enough
to accommodate the newsize. If the newsize falls lower than half
the allocated size, then proceed with the realloc() to shrink the list.
*/
// 如果列表已经分配的元素个数大于需求个数 newsize 的就直接返回不需要进行扩容
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SIZE(self) = newsize;
return 0;
}
/* This over-allocates proportional to the list size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
// 这是核心的数组大小扩容机制 new_allocated 表示新增的数组大小
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 这是一个宏定义 会申请 new_allocated 个数元素并且将原来数组的元素拷贝到新的数组当中
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;
}
在上面的扩容机制下,数组的大小变化大致如下所示:
在列表当中插入一个数据比较简单,只需要将插入位置和其后面的元素往后移动一个位置即可,整个过程如下所示:
在 cpython 当中列表的插入函数的实现如下所示:
int
PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
{
// 检查是否是列表类型
if (!PyList_Check(op)) {
PyErr_BadInternalCall();
return -1;
}
// 如果是列表类型则进行插入操作
return ins1((PyListObject *)op, where, newitem);
}
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
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;
}
// 确保列表能够容纳 n + 1 个元素
if (list_resize(self, n+1) == -1)
return -1;
// 这里是 python 的一个小 trick 就是下标能够有负数的原理
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];
// 因为链表应用的对象,因此对象的 reference count 需要进行加一操作
Py_INCREF(v);
// 在列表当中保存对象 v
items[where] = v;
return 0;
}
对于数组 ob_item 来说,删除一个元素就需要将这个元素后面的元素往前移动,因此整个过程如下所示:
static PyObject *
listremove(PyListObject *self, PyObject *v)
{
Py_ssize_t i;
// 编译数组 ob_item 查找和对象 v 相等的元素并且将其删除
for (i = 0; i < Py_SIZE(self); i++) {
int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
if (cmp > 0) {
if (list_ass_slice(self, i, i+1,
(PyObject *)NULL) == 0)
Py_RETURN_NONE;
return NULL;
}
else if (cmp < 0)
return NULL;
}
// 如果没有找到这个元素就进行报错处理 在下面有一个例子重新编译 python 解释器 将这个错误内容修改的例子
PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
return NULL;
}
执行的 python 程序内容为:
data = []
data.remove(1)
下面是整个修改内容和报错结果:
从上面的结果我们可以看到的是,我们修改的错误信息正确打印了出来.
这个函数的主要作用就是统计列表 self 当中有多少个元素和 v 相等.
static PyObject *
listcount(PyListObject *self, PyObject *v)
{
Py_ssize_t count = 0;
Py_ssize_t i;
for (i = 0; i < Py_SIZE(self); i++) {
int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
// 如果相等则将 count 进行加一操作
if (cmp > 0)
count++;
// 如果出现错误就返回 NULL
else if (cmp < 0)
return NULL;
}
// 将一个 Py_ssize_t 的变量变成 python 当中的对象
return PyLong_FromSsize_t(count);
}
这是列表的浅拷贝函数,它只拷贝了真实 python 对象的指针,并没有拷贝真实的 python 对象 ,从下面的代码可以知道列表的拷贝是浅拷贝,当 b 对列表当中的元素进行修改时,列表 a 当中的元素也改变了。如果需要进行深拷贝可以使用 copy 模块当中的 deepcopy 函数.
>>> a = [1, 2, [3, 4]]
>>> b = a.copy()
>>> b[2][1] = 5
>>> b
[1, 2, [3, 5]]
copy 函数对应的源代码(listcopy)如下所示:
static PyObject *
listcopy(PyListObject *self)
{
return list_slice(self, 0, Py_SIZE(self));
}
static PyObject *
list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
// Py_SIZE(a) 返回列表 a 当中元素的个数(注意不是数组的长度 allocated)
PyListObject *np;
PyObject **src, **dest;
Py_ssize_t i, len;
if (ilow < 0)
ilow = 0;
else if (ilow > Py_SIZE(a))
ilow = Py_SIZE(a);
if (ihigh < ilow)
ihigh = ilow;
else if (ihigh > Py_SIZE(a))
ihigh = Py_SIZE(a);
len = ihigh - ilow;
np = (PyListObject *) PyList_New(len);
if (np == NULL)
return NULL;
src = a->ob_item + ilow;
dest = np->ob_item;
// 可以看到这里循环拷贝的是指向真实 python 对象的指针 并不是真实的对象
for (i = 0; i < len; i++) {
PyObject *v = src[i];
// 同样的因为并没有创建新的对象,但是这个对象被新的列表使用到啦 因此他的 reference count 需要进行加一操作 Py_INCREF(v) 的作用:将对象 v 的 reference count 加一
Py_INCREF(v);
dest[i] = v;
}
return (PyObject *)np;
}
下图就是使用 a.copy() 浅拷贝的时候,内存的布局的示意图,可以看到列表指向的对象数组发生了变化,但是数组中元素指向的 python 对象并没有发生变化.
下面是对列表对象进行深拷贝的时候内存的大致示意图,可以看到数组指向的 python 对象也是不一样的.
当我们在使用 list.clear() 的时候会调用下面这个函数。清空列表需要注意的就是将表示列表当中元素个数的 ob_size 字段设置成 0 ,同时将列表当中所有的对象的 reference count 设置进行 -1 操作,这个操作是通过宏 Py_XDECREF 实现的,这个宏还会做另外一件事就是如果这个对象的引用计数变成 0 了,那么就会直接释放他的内存.
static PyObject *
listclear(PyListObject *self)
{
list_clear(self);
Py_RETURN_NONE;
}
static int
list_clear(PyListObject *a)
{
Py_ssize_t i;
PyObject **item = a->ob_item;
if (item != NULL) {
/* Because XDECREF can recursively invoke operations on
this list, we make it empty first. */
i = Py_SIZE(a);
Py_SIZE(a) = 0;
a->ob_item = NULL;
a->allocated = 0;
while (--i >= 0) {
Py_XDECREF(item[i]);
}
PyMem_FREE(item);
}
/* Never fails; the return value can be ignored.
Note that there is no guarantee that the list is actually empty
at this point, because XDECREF may have populated it again! */
return 0;
}
在 python 当中如果我们想要反转类表当中的内容的话,就会使用这个函数 reverse .
>>> a = [i for i in range(10)]
>>> a.reverse()
>>> a
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
其对应的源程序如下所示:
static PyObject *
listreverse(PyListObject *self)
{
if (Py_SIZE(self) > 1)
reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
Py_RETURN_NONE;
}
static void
reverse_slice(PyObject **lo, PyObject **hi)
{
assert(lo && hi);
--hi;
while (lo < hi) {
PyObject *t = *lo;
*lo = *hi;
*hi = t;
++lo;
--hi;
}
}
上面的源程序还是比较容易理解的,给 reverse_slice 传递的参数就是保存数据的数组的首尾地址,然后不断的将首尾数据进行交换(其实是交换指针指向的地址).
本文介绍了 Python 中列表对象的实现细节,介绍了一些常用函数的实现,包括列表的扩容机制,插入、删除、统计、拷贝、清空和反转等操作的实现方式.
总之,了解 Python 列表对象的实现细节有助于我们更好地理解 Python 的内部机制,从而编写更高效、更可靠的 Python 代码.
更多精彩内容合集可访问项目: https://github.com/Chang-LeHung/CSCore 。
关注公众号:一无是处的研究僧,了解更多计算机(Java、Python、计算机系统基础、算法与数据结构)知识.
最后此篇关于深入理解Python虚拟机:列表(list)的实现原理及源码剖析的文章就讲到这里了,如果你想了解更多关于深入理解Python虚拟机:列表(list)的实现原理及源码剖析的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
最近做一个项目,由于是在别人框架里开发app,导致了很多限制,其中一个就是不能直接引用webservice 。 我们都知道,调用webserivice 最简单的方法就是在 "引用"
这是SDL2代码的一部分 SDL主函数 int main(int argc,char *argv[]) { ... ... bool quit=false; S
c 中的函数: PHPAPI char *php_pcre_replace(char *regex, int regex_len, ch
我有以下映射: public class SecurityMap : ClassMap { public SecurityMap() {
我在vue-lic3中使用了SCSS,但是有一个奇怪的错误,使用/ deep /会报告错误,我不想看到它。 代码运行环境 vue-cli3 + vant + scss 的CSS /deep/ .van
我在深入阅读 C# 时遇到了这个我能理解的内容: 当它被限制为引用类型时,执行的比较类型完全取决于类型参数被限制为什么。 但是不能理解这个: 如果进一步限制派生自重载 == 和 != 运算符的特定类型
Closed. This question is opinion-based。它当前不接受答案。 想改善这个问题吗?更新问题,以便editing this post用事实和引用来回答。 3年前关闭。
有人可以详细介绍关于自赋值的运算符重载中的 *this 和 const 例如: Class& Class::operator=(const Class& other) { a = other.
在向树中插入新节点时,如何填充闭包表的深度/长度列? ancestor 和 descendant 中的值是来自另一个表的 ID,表示要以树结构排列的页面。 关闭表: ancestor desce
现在我正在阅读“深入了解 C#”。缺少的一件事是完成一章后我可以解决的一系列问题。那会帮助我理解我刚刚学到的概念。 哪里可以找到适合 C#3.0 的问题集? 谢谢 最佳答案 你可以试试LINQ 101
TypeScript 给 JavaScript 扩展了类型的语法,我们可以给变量加上类型,在编译期间会做类型检查,配合编辑器还能做更准确的智能提示。此外,TypeScript 还支持了高级类型用
是否有一个单行代码来获取生成器并生成该生成器中的所有元素?例如: def Yearly(year): yield YEARLY_HEADER for month in range(1, 13)
所以我阅读了一些与“什么是方法组”相关的 StackOverflow 问题以及其他互联网文章,它们在底线都说了同样的话——方法组是“一组重载方法” ". 但是,在阅读 Jon Skeet 的“C# 深
有什么方法可以从子组件中获取子组件吗? 想象一下以下组件树: 应用程序 问题 问题选项(包含复选框) 问题选项(包含复选框) 问题选项(包含复选框) 我想从 App 访问问题选项以选中所有复选框。 参
class_eval 和 instance_eval 在定义方法等情况下是完全可以预测的。我也理解类的实例和类的单例(又名特征类)之间的区别。 但是 我无法弄清楚以下唯一的事情:比方说,出于某些策略目
我想出了如何将符号 rwx 部分读取/转换为 421 个八进制部分,这非常简单。但是当涉及到特殊字符时,我感到非常困惑。我们知道 -r-xr---wx 转换为 0543,但 -r-sr---wt 或
我怀疑我系统的 Java 版本有问题。某些应用程序出现段错误或内存不足或存在链接错误。如果我从源代码安装了 JDK,我会做类似“make test”的事情,看看哪些测试失败了。但是,看起来从源代码构建
如何克隆一个 repo(使用 libgit2 ) 我想做什么git clone确实,但有 libgit2 .我可能要问的是什么 git clone确实很深入。 这是我目前正在做的: 初始化一个repo
00、头痛的JS闭包、词法作用域? 被JavaScript的闭包、上下文、嵌套函数、this搞得很头痛,这语言设计的,感觉比较混乱,先勉强理解总结一下😂😂😂.
我开始玩 lubridate R 中的包。我注意到 now(tzone="EST")计算为: [1] "2015-08-25 13:01:08 EST" 而 now(tzone="PST")导致警告:
我是一名优秀的程序员,十分优秀!