快捷導(dǎo)航

深入理解Python虛擬機中元組(tuple)的實現(xiàn)原理及源碼

更新時間：2023年03月11日 08:24:59 作者：一無是處的研究僧

在本篇文章當(dāng)中主要給大家介紹?cpython?虛擬機當(dāng)中針對列表的實現(xiàn)，在?Python?中，tuple?是一種非常常用的數(shù)據(jù)類型，在本篇文章當(dāng)中將深入去分析這一點是如何實現(xiàn)的

元組的結(jié)構(gòu)

在這一小節(jié)當(dāng)中主要介紹在 python 當(dāng)中元組的數(shù)據(jù)結(jié)構(gòu)：

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;

從上面的數(shù)據(jù)結(jié)構(gòu)來看和 list 的數(shù)據(jù)結(jié)構(gòu)基本上差不多，最終的使用方法也差不多。將上面的結(jié)構(gòu)體展開之后，PyTupleObject 的結(jié)構(gòu)大致如下所示：

現(xiàn)在來解釋一下上面的各個字段的含義：

Py_ssize_t，一個整型數(shù)據(jù)類型。
ob_refcnt，表示對象的引用記數(shù)的個數(shù)，這個對于垃圾回收很有用處，后面我們分析虛擬機中垃圾回收部分在深入分析。
ob_type，表示這個對象的數(shù)據(jù)類型是什么，在 python 當(dāng)中有時候需要對數(shù)據(jù)的數(shù)據(jù)類型進行判斷比如 isinstance, type 這兩個關(guān)鍵字就會使用到這個字段。
ob_size，這個字段表示這個元組當(dāng)中有多少個元素。
ob_item，這是一個指針，指向真正保存 python 對象數(shù)據(jù)的地址，大致的內(nèi)存他們之間大致的內(nèi)存布局如下所示：

需要注意的是元組的數(shù)組大小是不能夠進行更改的，這一點和 list 不一樣，我們可以注意到在 list 的數(shù)據(jù)結(jié)構(gòu)當(dāng)中還有一個 allocated 字段，但是在元組當(dāng)中是沒有的，這主要是因為元組的數(shù)組大小是固定的，而列表的數(shù)組大小是可以更改的。

元組操作函數(shù)源碼剖析

創(chuàng)建元組

首先我們需要了解一下在 cpython 內(nèi)部關(guān)于元組內(nèi)存分配的問題，首先和 list 一樣，在 cpython 當(dāng)中對于分配的好的元組進行釋放的時候，并不會直接進行釋放，而是會先保存下來，當(dāng)下次又有元組申請內(nèi)存的時候，直接將這塊內(nèi)存進行返回即可。

在 cpython 內(nèi)部會進行緩存的元組大小為 20，如果元組的長度為 0 - 19 那么在申請分配內(nèi)存之后釋放并不會直接釋放，而是將其先保存下來，下次有需求的時候直接分配，而不需要申請。在 cpython 內(nèi)部，相關(guān)的定義如下所示：

static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];
static int numfree[PyTuple_MAXSAVESIZE];

free_list，保存指針——指向被釋放的元組。
numfree，對應(yīng)的下標(biāo)表示元組當(dāng)中元素的個數(shù)，numfree[i] 表示有 i 個元素的元組的個數(shù)。

下面是新建 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
    // 如果申請一個空的元組對象 當(dāng)前的 free_list 當(dāng)中是否存在空元組對象 如果存在則直接返回
    if (size == 0 && free_list[0]) k
        op = free_list[0];
        Py_INCREF(op);
        return (PyObject *) op;
    }
    // 如果元組的對象元素個數(shù)小于 20 而且對應(yīng)的 free_list 當(dāng)中還有余下的元組對象 則不需要進行內(nèi)存申請直接返回
    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 的引用計數(shù)設(shè)置成 1
    }
    else
#endif
    {
        /* Check for overflow */
        // 如果元組的元素個數(shù)大或者等于 20 或者 當(dāng)前 free_list 當(dāng)中沒有沒有剩余的對象則需要進行內(nèi)存申請
        if ((size_t)size > ((size_t)PY_SSIZE_T_MAX - sizeof(PyTupleObject) -
                    sizeof(PyObject *)) / sizeof(PyObject *)) {
          	// 如果元組長度大于某個值直接報內(nèi)存錯誤
            return PyErr_NoMemory();
        }
        // 申請元組大小的內(nèi)存空間
        op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
        if (op == NULL)
            return NULL;
    }
		// 初始化內(nèi)存空間
    for (i=0; i < size; i++)
        op->ob_item[i] = NULL;
#if PyTuple_MAXSAVESIZE > 0
    // 因為 size == 0 的元組不會進行修改操作 因此可以直接將這個申請到的對象放到 free_list 當(dāng)中以備后續(xù)使用
    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 將入到垃圾回收隊列當(dāng)中
    return (PyObject *) op;
}

新建元組對象的流程如下所示：

查看 free_list 當(dāng)中是否已經(jīng)存在空閑的元組，如果有則直接進行返回。
如果沒有，則進行內(nèi)存分配，然后將申請的內(nèi)存空間進行初始化操作。
如果 size == 0，則可以將新分配的元組對象放到 free_list 當(dāng)中。

查看元組的長度

這個功能比較簡單，直接只用 cpython 當(dāng)中的宏 Py_SIZE 即可。他的宏定義為 #define Py_SIZE(ob) (((PyVarObject*)(ob))->ob_size)。

static Py_ssize_t
tuplelength(PyTupleObject *a)
{
    return Py_SIZE(a);
}

元組當(dāng)中是否包含數(shù)據(jù)

這個其實和 list 一樣，就是遍歷元組當(dāng)中的數(shù)據(jù)，然后進行比較即可。

static int
tuplecontains(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;
}

獲取和設(shè)置元組中的數(shù)據(jù)

這兩個方法也比較簡單，首先檢查數(shù)據(jù)類型是不是元組類型，然后判斷是否越界，之后就返回數(shù)據(jù)，或者設(shè)置對應(yīng)的數(shù)據(jù)。

這里在設(shè)置數(shù)據(jù)數(shù)據(jù)的時候需要注意一點的是，當(dāng)設(shè)置新的數(shù)據(jù)的時候，原來的 python 對象引用計數(shù)需要減去一，同理如果設(shè)置沒有成功的話傳入的新的數(shù)據(jù)的引用計數(shù)也需要減去一。

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];
}
 
int
PyTuple_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;
}

釋放元組內(nèi)存空間

當(dāng)我們在進行垃圾回收的時候，判定一個對象的引用計數(shù)等于 0 的時候就需要釋放這塊內(nèi)存空間（相當(dāng)于析構(gòu)函數(shù)），下面就是釋放 tuple 內(nèi)存空間的函數(shù)。

static void
tupledealloc(PyTupleObject *op)
{
    Py_ssize_t i;
    Py_ssize_t len =  Py_SIZE(op);
    PyObject_GC_UnTrack(op); // PyObject_GC_UnTrack 將對象從垃圾回收隊列當(dāng)中移除
    Py_TRASHCAN_SAFE_BEGIN(op) 
    if (len > 0) {
        i = len;
        while (--i >= 0)
            // 將這個元組指向的對象的引用計數(shù)減去一
            Py_XDECREF(op->ob_item[i]);
#if PyTuple_MAXSAVESIZE > 0
        // 如果這個元組對象滿足加入 free_list  的條件，則將這個元組對象加入到 free_list 當(dāng)中
        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)
}

將元組的內(nèi)存空間回收的時候，主要有以下幾個步驟：

將元組對象從垃圾回收鏈表當(dāng)中移除。
將元組指向的所有對象的引用計數(shù)減一。
判斷元組是否滿足保存到 free_list 當(dāng)中的條件，如果滿足就將他加入到 free_list 當(dāng)中去，否則回收這塊內(nèi)存。加入到 free_list 當(dāng)中整個元組當(dāng)中 ob_item 指向變化如下所示：

如果不能夠?qū)⑨尫诺脑M對象加入到 free_list 當(dāng)中，否則將內(nèi)存釋放回收。

總結(jié)

在本篇文章當(dāng)中主要介紹了在 cpython 當(dāng)中是如何實現(xiàn) tuple 的，以及相關(guān)的數(shù)據(jù)結(jié)構(gòu)和一些基本的使用函數(shù)，最后簡單談了關(guān)于元組內(nèi)存釋放的問題，這里面還是涉及一些其他的知識點，不能夠在這篇文章進行分析，在本文內(nèi)存分配主要是聚焦在元組身上，主要是分析內(nèi)存分配和 tuple 的 free_list 是如何交互的。

到此這篇關(guān)于深入理解Python虛擬機中元組(tuple)的實現(xiàn)原理及源碼的文章就介紹到這了,更多相關(guān)Python虛擬機元組內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: