// Include/cpython/tupleobject.h
typedef struct {
    PyObject_VAR_HEAD
    PyObject *ob_item[1];
} PyTupleObject;

// Objects/tupleobject.c
PyObject *
PyTuple_New(Py_ssize_t size)
{
    // 參數(shù) size 表示元組的長(zhǎng)度
    PyTupleObject *op;
    // 如果 size 為 0，返回空數(shù)組
    if (size == 0) {
        return tuple_get_empty();
    }
    // 調(diào)用 tuple_alloc 為元組申請(qǐng)內(nèi)存
    op = tuple_alloc(size);
    // 如果返回的指針為 NULL，表示申請(qǐng)失敗
    if (op == NULL) {
        return NULL;
    }
    // 將指針數(shù)組中所有元素設(shè)置為 NULL
    for (Py_ssize_t i = 0; i < size; i++) {
        op->ob_item[i] = NULL;
    }
    // 讓 GC 進(jìn)行跟蹤
    _PyObject_GC_TRACK(op);
    // 轉(zhuǎn)成泛型指針之后返回
    return (PyObject *) op;
}

// Objects/tupleobject.c
static PyTupleObject *
tuple_alloc(Py_ssize_t size)
{
    // size 必須大于等于 0
    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
    // 優(yōu)先從緩存池中獲取，所以元組也有緩存池
    // 關(guān)于元組的緩存池稍后再聊
    PyTupleObject *op = maybe_freelist_pop(size);
    // 如果 op 為 NULL，說(shuō)明緩存池?zé)o可用元素
    if (op == NULL) {
        // size * sizeof(PyObject *) + sizeof(PyTupleObject) 便是元組大小
        // 該值不能超過(guò) PY_SSIZE_T_MAX，否則報(bào)錯(cuò)
        if ((size_t)size > ((size_t)PY_SSIZE_T_MAX - (sizeof(PyTupleObject) -
                    sizeof(PyObject *))) / sizeof(PyObject *)) {
            return (PyTupleObject *)PyErr_NoMemory();
        }
        // 為 PyTupleObject 和長(zhǎng)度為 size 的指針數(shù)組申請(qǐng)內(nèi)存
        // 然后將它的類(lèi)型設(shè)置為 &PyTuple_Type，將 ob_size 設(shè)置為 size
        op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
        if (op == NULL)
            return NULL;
    }
    // 返回 op
    return op;
}

// Include/internal/pycore_tuple.h
#define PyTuple_MAXSAVESIZE 20
#define PyTuple_NFREELISTS PyTuple_MAXSAVESIZE
#define PyTuple_MAXFREELIST 2000

struct _Py_tuple_state {
    PyTupleObject *free_list[PyTuple_NFREELISTS];
    int numfree[PyTuple_NFREELISTS];
};

// Objects/tupleobject.c
static void
tupledealloc(PyTupleObject *op)
{   
    // 緩存池存放的是長(zhǎng)度為 1 ~ 20 的元組
    // 如果是空元組，那么它是單例的永恒對(duì)象，會(huì)永遠(yuǎn)存在
    // 因此這里會(huì)直接返回，不做任何額外操作
    if (Py_SIZE(op) == 0) {
        if (op == &_Py_SINGLETON(tuple_empty)) {
            return;
    }
    // 讓 GC 不再跟蹤
    PyObject_GC_UnTrack(op);
    // 延遲釋放，和列表是類(lèi)似的
    Py_TRASHCAN_BEGIN(op, tupledealloc)
    // 獲取銷(xiāo)毀的元組的長(zhǎng)度
    Py_ssize_t i = Py_SIZE(op);
    // 減少內(nèi)部元素指向?qū)ο蟮囊糜?jì)數(shù)，因?yàn)樵M不再持有對(duì)它們的引用
    while (--i >= 0) {
        Py_XDECREF(op->ob_item[i]);
    }
    // 嘗試放入緩存池
    if (!maybe_freelist_push(op)) {
        // 如果元組長(zhǎng)度大于 20，或者緩存池已滿(mǎn)
        // 那么釋放內(nèi)存
        Py_TYPE(op)->tp_free((PyObject *)op);
    }

    Py_TRASHCAN_END
}

/* 在前面的章節(jié)中我們說(shuō)了，在 3.12 之前
   對(duì)象的緩存池是以靜態(tài)全局變量的形式定義在文件中，以 3.8 的元組緩存池為例
   static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];
   static int numfree[PyTuple_MAXSAVESIZE];
   但在 3.12 的時(shí)候則被封裝在了一個(gè)結(jié)構(gòu)體（_Py_tuple_state）中
   在解釋器啟動(dòng)之后會(huì)靜態(tài)初始化好，并綁定在進(jìn)程狀態(tài)對(duì)象上面 */
// 所以這里的 STATE 便負(fù)責(zé)獲取元組的緩存池，即 _Py_tuple_state 結(jié)構(gòu)體實(shí)例
// 它里面包含了 numfree 和 free_list
#define STATE (interp->tuple)

// 將元組放入緩存池
static inline int
maybe_freelist_push(PyTupleObject *op)
{
#if PyTuple_NFREELISTS > 0
    // 獲取進(jìn)程狀態(tài)對(duì)象，interp->tuple 便是元組的緩存池
    PyInterpreterState *interp = _PyInterpreterState_GET();
    // 如果元組長(zhǎng)度為 0，不做處理
    if (Py_SIZE(op) == 0) {
        return0;
    }
    // free_list 里面的每個(gè)元素都指向了一個(gè)鏈表的頭結(jié)點(diǎn)
    // 每條鏈表存放的元組都具有相同的長(zhǎng)度，如果元組長(zhǎng)度為 n
    // 那么它會(huì)放在 free_list[n - 1] 對(duì)應(yīng)的鏈表中
    Py_ssize_t index = Py_SIZE(op) - 1;
    // index 必須小于 20，即元組長(zhǎng)度不超過(guò) 20
    // STATE.numfree[index] 必須小于 2000，即每條鏈表最多緩存 2000 個(gè)元組
    if (index < PyTuple_NFREELISTS
        && STATE.numfree[index] < PyTuple_MAXFREELIST
        && Py_IS_TYPE(op, &PyTuple_Type))
    {
        // ob_item[0] 充當(dāng)了鏈表的 next 指針
        // 這里讓 op->ob_item[0] 等于 free_list[index]
        // 然后讓 free_list[index] 等于 op
        // 這樣元組就緩存起來(lái)了，并成為鏈表新的頭結(jié)點(diǎn)，即 free_list[index]
        op->ob_item[0] = (PyObject *) STATE.free_list[index];
        STATE.free_list[index] = op;
        // 然后維護(hù)一下鏈表的節(jié)點(diǎn)個(gè)數(shù)
        STATE.numfree[index]++;
        OBJECT_STAT_INC(to_freelist);
        return1;
    }
#endif
    return0;
}

// Objects/tupleobject.c
static inline PyTupleObject *
maybe_freelist_pop(Py_ssize_t size)
{
#if PyTuple_NFREELISTS > 0
    // 獲取進(jìn)程狀態(tài)對(duì)象
    PyInterpreterState *interp = _PyInterpreterState_GET();
    // size 不可能為 0
    // 如果 size 為 0，那么在 PyTuple_New 中會(huì)直接返回空元組
    if (size == 0) {
        return NULL;
    }
    assert(size > 0);
    // 緩存池中每個(gè)元素都指向一個(gè)鏈表的頭結(jié)點(diǎn)
    // PyTuple_NFREELISTS 表示鏈表的個(gè)數(shù)，PyTuple_MAXSAVESIZE 表示緩存池的大小
    // 所以這兩個(gè)宏是等價(jià)的，默認(rèn)都是 20
    // 只有元組的長(zhǎng)度不超過(guò) 20 的時(shí)候，才會(huì)被緩存
    if (size <= PyTuple_MAXSAVESIZE) {
        Py_ssize_t index = size - 1;
        // 獲取鏈表的頭節(jié)點(diǎn)
        PyTupleObject *op = STATE.free_list[index];
        if (op != NULL) {
            // 獲取之后，它的下一個(gè)節(jié)點(diǎn)要成為新的頭結(jié)點(diǎn)
            STATE.free_list[index] = (PyTupleObject *) op->ob_item[0];
            // 鏈表節(jié)點(diǎn)個(gè)數(shù)減 1
            STATE.numfree[index]--;
            // 增加引用計(jì)數(shù)之后返回
            _Py_NewReference((PyObject *)op);
            OBJECT_STAT_INC(from_freelist);
            return op;
        }
    }
#endif
    return NULL;
}

a, b, c, d = 1, 2, 3, 4

from timeit import timeit

t1 = timeit(stmt="x1 = [1, 2, 3, 4, 5]", number=1000000)
t2 = timeit(stmt="x2 = (1, 2, 3, 4, 5)", number=1000000)

print(round(t1, 2))  # 0.05
print(round(t2, 2))  # 0.01

// Objects/tupleobject.c
static inline PyObject *
tuple_get_empty(void)
{
    return Py_NewRef(&_Py_SINGLETON(tuple_empty));
}

// Include/internal/pycore_global_objects.h
struct _Py_static_objects {
    struct {
        // ...
        PyTupleObject tuple_empty;
        // ...
    } singletons;
};

// Include/internal/pycore_runtime_init.h
#define _PyRuntimeState_INIT(runtime) \
    { \
        .static_objects = { \
            .singletons = { \
             /* ... */ \
                .tuple_empty = { \
                    .ob_base = _PyVarObject_HEAD_INIT(&PyTuple_Type, 0) \
                }, \
                /* ... */ \
            }, \
        }, \
    }