本文同步刊載於 「為你自己學 Python - 不動如山的 Tuple」

不動如山的 Tuple

Python 裡的 Tuple 是一種不可變的（Immutable）資料結構，它可以用來儲存多個元素，並且可以透過索引值來存取這些元素。Tuple 跟串列有點像，但是 Tuple 是不可變的，也就是說，一旦 Tuple 被建立之後，就不能再新增、刪除或修改裡面的元素。這個章節就來看看它是怎麼設計的，還有哪些有趣的特性。

Tuple 的設計

// 檔案：Include/cpython/tupleobject.h

typedef struct {
    PyObject_VAR_HEAD
    PyObject *ob_item[1];
} PyTupleObject;

如果各位是從前面看到這個章節的話，應該對這個結構不陌生了。PyTupleObject 結構的一開頭也有像串列一樣的 PyObject_VAR_HEAD，然後還有一個 ob_item 成員，主要用來存放 Tuple 中的元素。只是，為什麼這裡是寫 ob_item[1] 而不像 PyListObject 用 **ob_items？這個 [1] 又是什麼意思？

這是一個 C 語言的技巧,稱為「彈性陣列成員（Flexible Array Member）」，這樣的寫法可以讓結構的最後一個成員是一個未知大小的陣列，雖然看起來像是一個只有一個元素，但實際上它可以容納任意數量的元素，而且所有元素都是連續儲存的。這樣的設計可以讓 Tuple 在記憶體中佔用連續的空間，這樣一來，Python 就可以更有效率地存取 Tuple 裡的元素。大概看起來像這樣：

+-------------------+
| PyObject_VAR_HEAD |
+-------------------+
| ob_item[0]        |
+-------------------+
| ob_item[1]        |
+-------------------+
| ob_item[2]        |
+-------------------+
| ...               |
+-------------------+
| ob_item[size-1]   |
+-------------------+

而不像串列一樣用 **ob_items 的寫法，最主要是因為 Tuple 的設計不需要支援動態增減元素，所以可以用這種更簡單的方式來實現，執行的效率也會更好。

建立 Tuple

建立 Tuple，應該就是去找 PyTuple_Type 上的 tp_new 成員，它指向 tuple_new() 函數：

// 檔案：Objects/clinic/tupleobject.c.h

static PyObject *
tuple_new(PyTypeObject *type, PyObject *args, PyObject *kwargs)
{
    PyObject *return_value = NULL;
    PyTypeObject *base_tp = &PyTuple_Type;
    PyObject *iterable = NULL;

    // ... 略 ...
    if (PyTuple_GET_SIZE(args) < 1) {
        goto skip_optional;
    }
    iterable = PyTuple_GET_ITEM(args, 0);
skip_optional:
    return_value = tuple_new_impl(type, iterable);

exit:
    return return_value;
}

扣掉一些參數判斷的，首先第一個重點在 PyTuple_GET_ITEM() 巨集，展開後是這樣的：

// 檔案：Include/cpython/tupleobject.h

#define PyTuple_GET_ITEM(op, index) (_PyTuple_CAST(op)->ob_item[(index)])

這個巨集是用來取得 Tuple 裡的元素，它會直接存取 Tuple 的 ob_item 陣列，並且回傳指定索引的元素。這個巨集在滿多地方都會用節，算是 Tuple 的重點操作之一。

下一個重點，就是 tuple_new_impl() 函數，這個函數是真正用來建立 Tuple 的：

// 檔案：Objects/tupleobject.c

static PyObject *
tuple_new_impl(PyTypeObject *type, PyObject *iterable)
{
    if (type != &PyTuple_Type)
        return tuple_subtype_new(type, iterable);

    if (iterable == NULL) {
        return tuple_get_empty();
    }
    else {
        return PySequence_Tuple(iterable);
    }
}

這個函數裡面有兩個分支，第一個是檢查是否是自 Tuple 的子類別，例如在 Python 程式可能會這樣寫：

class HelloTuple(tuple):
    pass

如果是這樣的話，就會進入這個分支呼叫 tuple_subtype_new() 函數，但如果追進去看就會發現這個函數本質上還是呼叫 tuple_new_impl()，只是傳入不一樣的參數，這麼做的原因是為了讓 Tuple 的子類別可以自由地擴充或修改建立 Tuple 的行為。

如果是建立一般的 Tuple，就會進入第二個分支，看是要建立個空的 Tuple，還是建立有料的 Tuple。先看看建立空 Tuple 的 tuple_get_empty() 函數...

空的 Tuple

// 檔案：Objects/tupleobject.c

static inline PyObject *
tuple_get_empty(void)
{
    return Py_NewRef(&_Py_SINGLETON(tuple_empty));
}

這裡的 _Py_SINGLETON() 巨集會定義一個全域的物件，這種全域物件建立之後就不會被 GC 回收的，這樣可以確保每次要建立空 Tuple 的時候直接伸手去空中抓一份回來重複使用，不用每次都重新建立。正因為都是同一份物件，加上 Tuple 是不可變的，所以如果我們在 Python 裡使用 is 關鍵字比較兩個空的 Tuple 的時候會得到 True：

>>> a = ()
>>> b = ()
>>> a is b
True

因為它們根本就是同一顆物件，而且在 Python 直譯器一啟動的時候就會先幫我們建立一份了。

有料的 Tuple

我這裡指的「有料」，是指在 Python 呼叫 tuple() 類別建立 Tuple 的時候額外帶資料給它：

>>> t1 = tuple([1, 2, 3])
>>> t1
(1, 2, 3)
>>> t2 = tuple("hello")
>>> t2
('h', 'e', 'l', 'l', 'o')
>>>

只要傳進來的是個可迭代的物件，Python 就會把它轉換成 Tuple。來看看 PySequence_Tuple() 是怎麼做到這件事，不過這個函數行數比較多，我們分段來看：

// 檔案：Objects/abstract.c

PyObject *
PySequence_Tuple(PyObject *v)
{
    // ... 略 ...
    if (PyTuple_CheckExact(v)) {
        return Py_NewRef(v);
    }
    if (PyList_CheckExact(v))
        return PyList_AsTuple(v);

    // ... 略 ...
}

這裡有兩個檢查，如果傳入的本身就是一個 Tuple 的話，就直接回傳它自己，不用再重新建立，所以：

>>> a = (1, 2, 3)
>>> b = tuple(a)
>>> a is b
True

如果是串列的話，就會呼叫 PyList_AsTuple() 函數，這個函數會把串列轉換成 Tuple，而這個轉換過程也滿單純的，最後實作的是這個 _PyTuple_FromArray() 函數：

// 檔案：Objects/tupleobject.c

PyObject *
_PyTuple_FromArray(PyObject *const *src, Py_ssize_t n)
{
    if (n == 0) {
        return tuple_get_empty();
    }

    PyTupleObject *tuple = tuple_alloc(n);
    if (tuple == NULL) {
        return NULL;
    }
    PyObject **dst = tuple->ob_item;
    for (Py_ssize_t i = 0; i < n; i++) {
        PyObject *item = src[i];
        dst[i] = Py_NewRef(item);
    }
    _PyObject_GC_TRACK(tuple);
    return (PyObject *)tuple;
}

這裡所謂的轉換，其實也就是跑個 for 迴圈，然後把值一個一個放到 ob_item 陣列裡，這樣就完成了 Tuple 的建立。

回收機制？

當建立的 Tuple 不再使用的時候，例如它的 Reference Count 降到 0 的時候，系統應該會來收回佔用的記憶體空間。想要知道是怎麼做到這件事的話，就得翻一下 PyTuple_Type 的 tp_dealloc 成員對應到的函數 tupledealloc()：

// 檔案：Objects/tupleobject.c

static void
tupledealloc(PyTupleObject *op)
{
    if (Py_SIZE(op) == 0) {
        if (op == &_Py_SINGLETON(tuple_empty)) {
            return;
        }
    }

    PyObject_GC_UnTrack(op);
    Py_TRASHCAN_BEGIN(op, tupledealloc)

    Py_ssize_t i = Py_SIZE(op);
    while (--i >= 0) {
        Py_XDECREF(op->ob_item[i]);
    }
    if (!maybe_freelist_push(op)) {
        Py_TYPE(op)->tp_free((PyObject *)op);
    }

    Py_TRASHCAN_END
}

這裡有兩個地方值得看的，第一個是判斷要放掉的這顆物件是不是空的 Tuple，前面有提到空的 Tuple 是一顆全域的物件，它不會參與資源回收的流程，所以就直接跳過。第二個重點是 maybe_freelist_push() 函數，來看看這個函數在做什麼：

// 檔案：Objects/tupleobject.c

static inline int
maybe_freelist_push(PyTupleObject *op)
{
    PyInterpreterState *interp = _PyInterpreterState_GET();
    if (Py_SIZE(op) == 0) {
        return 0;
    }
    Py_ssize_t index = Py_SIZE(op) - 1;
    if (index < PyTuple_NFREELISTS
        && STATE.numfree[index] < PyTuple_MAXFREELIST
        && Py_IS_TYPE(op, &PyTuple_Type))
    {
        op->ob_item[0] = (PyObject *) STATE.free_list[index];
        STATE.free_list[index] = op;
        STATE.numfree[index]++;
        OBJECT_STAT_INC(to_freelist);
        return 1;
    }

    return 0;
}

這裡我把一些條件編譯拿掉了，可以看的出來
還記得我們在浮點數章節也介紹過一個叫做「空閒列表（Free List）」的機制，這個 maybe_freelist_push() 函數就是在處理類似的事情。

如果是空的 Tuple 的話不處理，因為空的 Tuple 是不需要參與這個機制。再來，如果：

1. Tuple 裡的元素數量沒有超過 PyTuple_NFREELISTS（通常設定 20）的話。
2. 傳進來的這傢伙是個 Tuple 的話
3. 空閒列表的空間還沒超過 PyTuple_MAXFREELIST（通常設定 2,000）的話。

上面三個條件都滿足的時候，就會準備把這個 Tuple 加到空閒列表裡。也就是說，如果 Tuple 裡的元素數量小於 20 的話，當這顆物件被放掉的時候，Python 不會馬上釋放記憶體，而是會先把它加到加到空閒列表裡。

我們來寫一段程式碼證明一下：

>>> t1 = tuple(range(20))
>>> id(t1)
4339988768

>>> del t1
>>> t2 = tuple(range(20))
>>> id(t2)
4339988768

>>> t3 = tuple(range(21))
>>> id(t3)
4306827552

>>> del t3
>>> t4 = tuple(range(21))
>>> id(t4)
4306827552

可以看到在 Tuple 元素沒有大於 20 個的時候，使用 del 關鍵字斷開變數跟 Tuple 之間的連結後再建立一個一樣的 Tuple 的時候，它們的 id 還是一樣的，表示這兩個 Tuple 是同一個物件，Python 從 Free List 裡幫我們把 Tuple 撿回來了。但是當 Tuple 元素數量大於 20 的時候，再建立一個一樣的 Tuple 的時候，它們的 id 就不一樣了，這表示這兩個 Tuple 是不同的物件。

常見 Tuple 操作

Tuple 修改

Tuple 是不可變的（Immutable），這個特性跟串列不一樣，所以我們不能直接修改 Tuple 裡的元素。但這個其實也沒什麼神秘的，就跟之前介紹到同樣也是不可修改的字串一樣，說穿了，就是 PyTuple_Type 的 tuple_as_mapping 成員中關於修改的成員函數是空的：

// 檔案：Objects/tupleobject.c

static PyMappingMethods tuple_as_mapping = {
    (lenfunc)tuplelength,
    (binaryfunc)tuplesubscript,
    0
};

讀取有 tuplesubscript() 函數沒問題，但修改的成員函數是空的，所以想要對 Tuple 進行修改就會出現錯誤：

>>> t = (9, 5, 2, 7)
>>> t[0] = "x"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

Tuple 開箱

在 Python 裡，我們可以用 Tuple「開箱（Unpacking）」的方式來把 Tuple 裡的元素一次取出來並指定給多個變數：

t = (9, 5, 2, 7)
a, b, c, d = t

這是怎麼做到的？翻一下這一段程式碼的 Bytecode，會發現開箱對應到的指令碼是 UNPACK_SEQUENCE，追看看這個指令做什麼事：

// 檔案：Python/bytecodes.c

inst(UNPACK_SEQUENCE, (unused/1, seq -- unused[oparg])) {
    #if ENABLE_SPECIALIZATION
    _PyUnpackSequenceCache *cache = (_PyUnpackSequenceCache *)next_instr;
    if (ADAPTIVE_COUNTER_IS_ZERO(cache->counter)) {
        next_instr--;
        _Py_Specialize_UnpackSequence(seq, next_instr, oparg);
        DISPATCH_SAME_OPARG();
    }
    STAT_INC(UNPACK_SEQUENCE, deferred);
    DECREMENT_ADAPTIVE_COUNTER(cache->counter);
    #endif  /* ENABLE_SPECIALIZATION */
    PyObject **top = stack_pointer + oparg - 1;
    int res = unpack_iterable(tstate, seq, oparg, -1, top);
    DECREF_INPUTS();
    ERROR_IF(res == 0, error);
}

因為 Tuple 跟串列都可以用同樣的手法進行開箱，而且指令都是 UNPACK_SEQUENCE，所以要分辨是 Tuple 還是串列的開箱應該就是在 _Py_Specialize_UnpackSequence() 函數裡了：

// 檔案：Python/specialize.c

void
_Py_Specialize_UnpackSequence(PyObject *seq, _Py_CODEUNIT *instr, int oparg)
{
    // ... 略 ...
    _PyUnpackSequenceCache *cache = (_PyUnpackSequenceCache *)(instr + 1);
    if (PyTuple_CheckExact(seq)) {
        // ... 略 ...
        if (PyTuple_GET_SIZE(seq) == 2) {
            instr->op.code = UNPACK_SEQUENCE_TWO_TUPLE;
            goto success;
        }
        instr->op.code = UNPACK_SEQUENCE_TUPLE;
        goto success;
    }
    if (PyList_CheckExact(seq)) {
        // ... 略 ...
        instr->op.code = UNPACK_SEQUENCE_LIST;
        goto success;
    }
    // ... 略 ...
}

看的出來這些指令會有不同的 opcode。只是，當 Tuple 的元素只有 2 個的時候，會用 UNPACK_SEQUENCE_TWO_TUPLE 指令，其他的情況都是用 UNPACK_SEQUENCE_TUPLE 指令。這有什麼差別？難道 Python 有專門對 2 個元素的 Tuple 做了什麼最佳化的設計？來看看這兩個指令在做什麼事：

// 檔案：Python/bytecodes.c

inst(UNPACK_SEQUENCE_TUPLE, (unused/1, seq -- values[oparg])) {
    // ... 略 ...
    PyObject **items = _PyTuple_ITEMS(seq);
    for (int i = oparg; --i >= 0; ) {
        *values++ = Py_NewRef(items[i]);
    }
    DECREF_INPUTS();
}

看起來一般的 UNPACK_SEQUENCE_TUPLE 指令做的事就是把 Tuple 物件的 ob_item 拿出來，跑個 for 迴圈然後把 Tuple 裡的元素一個一個取出來放到指定的變數裡。不過你會看到這個 for 迴圈是反著跑的，還記得最一開始在看 Tuple 結構的時候，裡面有個 ob_item[1] 的設計嗎？這個彈性陣列成員的設計就是讓元素就剛好貼在這個物件後面，不過因為這裡是「先進後出（Last In First Out）」的堆疊，舉個例子，t = (9, 5, 2, 7) 在記憶體裡的樣子：

+-----+-----+-----+-----+-----+
|  t  |  9  |  5  |  2  |  7  |
+-----+-----+-----+-----+-----+
^
|
PyTupleObject 本身

所以 for 迴圈反著跑就能一個一個拿出來了。再來看看 UNPACK_SEQUENCE_TWO_TUPLE 指令：

// 檔案：Python/bytecodes.c

inst(UNPACK_SEQUENCE_TWO_TUPLE, (unused/1, seq -- values[oparg])) {
    // ... 略 ...
    values[0] = Py_NewRef(PyTuple_GET_ITEM(seq, 1));
    values[1] = Py_NewRef(PyTuple_GET_ITEM(seq, 0));
    DECREF_INPUTS();
}

因為只有 2 顆元素，所以直接把 Tuple 裡的第 2 個元素放到第 1 個變數裡，第 1 個元素放到第 2 個變數裡，連迴圈都省下來了，真聰明。

最後順便看看串列的開箱：

// 檔案：Python/bytecodes.c

inst(UNPACK_SEQUENCE_LIST, (unused/1, seq -- values[oparg])) {
    // ... 略 ...
    PyObject **items = _PyList_ITEMS(seq);
    for (int i = oparg; --i >= 0; ) {
        *values++ = Py_NewRef(items[i]);
    }
    DECREF_INPUTS();
}

其實做的事差不多，只是拿的是串列的 ob_item 出來而已。

本文同步刊載於 「為你自己學 Python - 不動如山的 Tuple」