深刻了解 Python 虚拟机：元组（tuple）的实现原理及源码分析

在本篇文章当中次要给大家介绍 cpython 虚拟机当中针对列表的实现，在 Python 中，tuple 是一种十分罕用的数据类型，在本篇文章当中将深刻去剖析这一点是如何实现的。

元组的构造

在这一大节当中次要介绍在 python 当中元组的数据结构：

typedef struct {    PyObject_VAR_HEAD    PyObject *ob_item[1];    /* ob_item contains space for 'ob_size' elements.     * Items must normally not be NULL, except during construction when     * the tuple is not yet visible outside the function that builds it.     */} PyTupleObject;#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;

从下面的数据结构来看和 list 的数据结构基本上差不多，最终的应用办法也差不多。将下面的构造体开展之后，PyTupleObject 的构造大抵如下所示：

当初来解释一下下面的各个字段的含意：

  • Py_ssize_t，一个整型数据类型。
  • ob_refcnt，示意对象的援用记数的个数，这个对于垃圾回收很有用途，前面咱们剖析虚拟机中垃圾回收局部在深入分析。
  • ob_type，示意这个对象的数据类型是什么，在 python 当中有时候须要对数据的数据类型进行判断比方 isinstance, type 这两个关键字就会应用到这个字段。
  • ob_size，这个字段示意这个元组当中有多少个元素。
  • ob_item，这是一个指针，指向真正保留 python 对象数据的地址，大抵的内存他们之间大抵的内存布局如下所示：

须要留神的是元组的数组大小是不可能进行更改的，这一点和 list 不一样，咱们能够留神到在 list 的数据结构当中还有一个 allocated 字段，然而在元组当中是没有的，这次要是因为元组的数组大小是固定的，而列表的数组大小是能够更改的。

元组操作函数源码分析

创立元组

首先咱们须要理解一下在 cpython 外部对于元组内存调配的问题，首先和 list 一样，在 cpython 当中对于调配的好的元组进行开释的时候，并不会间接进行开释，而是会先保留下来，当下次又有元组申请内存的时候，间接将这块内存进行返回即可。

在 cpython 外部会进行缓存的元组大小为 20，如果元组的长度为 0 - 19 那么在申请分配内存之后开释并不会间接开释，而是将其先保留下来，下次有需要的时候间接调配，而不须要申请。在 cpython 外部，相干的定义如下所示：

static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];static int numfree[PyTuple_MAXSAVESIZE];
  • free_list，保留指针——指向被开释的元组。
  • numfree，对应的下标示意元组当中元素的个数，numfree[i] 示意有 i 个元素的元组的个数。

上面是新建 tuple 对象的源程序：

PyObject *PyTuple_New(Py_ssize_t size){    PyTupleObject *op;    Py_ssize_t i;    if (size < 0) {        PyErr_BadInternalCall();        return NULL;    }#if PyTuple_MAXSAVESIZE > 0    // 如果申请一个空的元组对象 以后的 free_list 当中是否存在空元组对象 如果存在则间接返回    if (size == 0 && free_list[0]) k        op = free_list[0];        Py_INCREF(op);        return (PyObject *) op;    }    // 如果元组的对象元素个数小于 20 而且对应的 free_list 当中还有余下的元组对象 则不须要进行内存申请间接返回    if (size < PyTuple_MAXSAVESIZE && (op = free_list[size]) != NULL) {        free_list[size] = (PyTupleObject *) op->ob_item[0];        numfree[size]--;        /* Inline PyObject_InitVar */        _Py_NewReference((PyObject *)op); // _Py_NewReference 这个宏是将对象 op 的援用计数设置成 1    }    else#endif    {        /* Check for overflow */        // 如果元组的元素个数大或者等于 20 或者 以后 free_list 当中没有没有残余的对象则须要进行内存申请        if ((size_t)size > ((size_t)PY_SSIZE_T_MAX - sizeof(PyTupleObject) -                    sizeof(PyObject *)) / sizeof(PyObject *)) {              // 如果元组长度大于某个值间接报内存谬误            return PyErr_NoMemory();        }        // 申请元组大小的内存空间        op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);        if (op == NULL)            return NULL;    }        // 初始化内存空间    for (i=0; i < size; i++)        op->ob_item[i] = NULL;#if PyTuple_MAXSAVESIZE > 0    // 因为 size == 0 的元组不会进行批改操作 因而能够间接将这个申请到的对象放到 free_list 当中以备后续应用    if (size == 0) {        free_list[0] = op;        ++numfree[0];        Py_INCREF(op);          /* extra INCREF so that this is never freed */    }#endif    _PyObject_GC_TRACK(op); // _PyObject_GC_TRACK 这个宏是将对象 op 将入到垃圾回收队列当中    return (PyObject *) op;}

新建元组对象的流程如下所示：

  • 查看 free_list 当中是否曾经存在闲暇的元组，如果有则间接进行返回。
  • 如果没有，则进行内存调配，而后将申请的内存空间进行初始化操作。
  • 如果 size == 0，则能够将新调配的元组对象放到 free_list 当中。

查看元组的长度

这个性能比较简单，间接只用 cpython 当中的宏 Py_SIZE 即可。他的宏定义为 \#define Py_SIZE(ob) (((PyVarObject*)(ob))->ob_size)。

static Py_ssize_ttuplelength(PyTupleObject *a){    return Py_SIZE(a);}

元组当中是否蕴含数据

这个其实和 list 一样，就是遍历元组当中的数据，而后进行比拟即可。

static inttuplecontains(PyTupleObject *a, PyObject *el){    Py_ssize_t i;    int cmp;    for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)        cmp = PyObject_RichCompareBool(el, PyTuple_GET_ITEM(a, i),                                           Py_EQ);    return cmp;}

获取和设置元组中的数据

这两个办法也比较简单，首先查看数据类型是不是元组类型，而后判断是否越界，之后就返回数据，或者设置对应的数据。

这里在设置数据数据的时候须要留神一点的是，当设置新的数据的时候，原来的 python 对象援用计数须要减去一，同理如果设置没有胜利的话传入的新的数据的援用计数也须要减去一。

PyObject *PyTuple_GetItem(PyObject *op, Py_ssize_t i){    if (!PyTuple_Check(op)) {        PyErr_BadInternalCall();        return NULL;    }    if (i < 0 || i >= Py_SIZE(op)) {        PyErr_SetString(PyExc_IndexError, "tuple index out of range");        return NULL;    }    return ((PyTupleObject *)op) -> ob_item[i];}intPyTuple_SetItem(PyObject *op, Py_ssize_t i, PyObject *newitem){    PyObject *olditem;    PyObject **p;    if (!PyTuple_Check(op) || op->ob_refcnt != 1) {        Py_XDECREF(newitem);        PyErr_BadInternalCall();        return -1;    }    if (i < 0 || i >= Py_SIZE(op)) {        Py_XDECREF(newitem);        PyErr_SetString(PyExc_IndexError,                        "tuple assignment index out of range");        return -1;    }    p = ((PyTupleObject *)op) -> ob_item + i;    olditem = *p;    *p = newitem;    Py_XDECREF(olditem);    return 0;}

开释元组内存空间

当咱们在进行垃圾回收的时候，断定一个对象的援用计数等于 0 的时候就须要开释这块内存空间（相当于析构函数），上面就是开释 tuple 内存空间的函数。

static voidtupledealloc(PyTupleObject *op){    Py_ssize_t i;    Py_ssize_t len =  Py_SIZE(op);    PyObject_GC_UnTrack(op); // PyObject_GC_UnTrack 将对象从垃圾回收队列当中移除    Py_TRASHCAN_SAFE_BEGIN(op)     if (len > 0) {        i = len;        while (--i >= 0)            // 将这个元组指向的对象的援用计数减去一            Py_XDECREF(op->ob_item[i]);#if PyTuple_MAXSAVESIZE > 0        // 如果这个元组对象满足退出 free_list  的条件，则将这个元组对象退出到 free_list 当中        if (len < PyTuple_MAXSAVESIZE &&            numfree[len] < PyTuple_MAXFREELIST &&            Py_TYPE(op) == &PyTuple_Type)        {            op->ob_item[0] = (PyObject *) free_list[len];            numfree[len]++;            free_list[len] = op;            goto done; /* return */        }#endif    }    Py_TYPE(op)->tp_free((PyObject *)op);done:    Py_TRASHCAN_SAFE_END(op)}

将元组的内存空间回收的时候，次要有以下几个步骤：

  • 将元组对象从垃圾回收链表当中移除。
  • 将元组指向的所有对象的援用计数减一。
  • 判断元组是否满足保留到 free_list 当中的条件，如果满足就将他退出到 free_list 当中去，否则回收这块内存。退出到 free_list 当中整个元组当中 ob_item 指向变动如下所示：

  • 如果不可能将开释的元组对象退出到 free_list 当中，否则将内存开释回收。

总结

在本篇文章当中次要介绍了在 cpython 当中是如何实现 tuple 的，以及相干的数据结构和一些根本的应用函数，最初简略谈了对于元组内存开释的问题，这外面还是波及一些其余的知识点，不可能在这篇文章进行剖析，在本文内存调配次要是聚焦在元组身上，次要是剖析内存调配和 tuple 的 free_list 是如何交互的。

本篇文章是深刻了解 python 虚拟机系列文章之一，文章地址：https://github.com/Chang-LeHung/dive-into-cpython

更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHung/CSCore

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。