파이썬 튜플 내부구조 (Python Tuple Internals)

파이썬의 튜플은 파이썬 시퀀스(sequence)의 하나로, 주로 Immutable이라는 부분만을 중심으로 기술되곤 합니다. 하지만, 이는 튜플의 또 하나의 큰 장점인 필드명 없이이 다양한 데이터타입(heterogeneous/homogeneous)을 기록한다는 부분을 간과하게 하는데요 [2]. 

 

이번 글에서는 파이썬 튜플의 내부구조와 관련해 아래와 같은 사항을 다뤄보려 합니다:

 

• 튜플구조와 2가지 특성 (Immutability, Records with no field names)
• 최적화

 

관련글:

• 파이썬 딕셔너리 내부구조
• 파이썬 클래스 내부구조

튜플구조와 2가지 특성

튜플은 파이썬의 다른 데이터타입과 비교할 때, 비교적 간단한 구조를 가집니다 [1]:

Image from Author

위와 같이 PyObject, PyVarObject, PyObject_VAR_HEAD, 그리고 튜플의 구조체인 PyTupleObject들이 내부구조를 이루고 있습니다. 위 PyTupleObject 코드에서 보실 수 있듯이, ob_item이라는 (사용 시에는 NULL이 아닌) 포인터가 ob_size의 객체를 가르키고 ob_item이 가르키는 곳에 record가 저장됩니다.

 

 

Immutability

튜플은 고정된 길이와 고정된 값을 가집니다. 

 

고정된 길이

튜플 생성 시(PyTuple_New), tuple_alloc 함수를 통해 요청 된 사이즈의 튜플을 할당합니다. tuple_alloc 함수는 요청된 사이즈의 튜플이 기존에 생성되어있던 것이 있으면 그것을 꺼내서 사용하고, 아니면 PyObject_GC_NewVar를 통해 새로 생성합니다 (이 부분은 아래 최적화에서 자세히 기술합니다).

 

# 생성
PyObject *
PyTuple_New(Py_ssize_t size)
{
    ...
    
    op = tuple_alloc(size);
    
    ...
}

# tuple_alloc 함수
static PyTupleObject *
tuple_alloc(Py_ssize_t size)
{
# 만약 PyTuple_MAXSAVESIZE > 0 이고 해당 size와 같은 크기의 미리 할당된 튜플이 있으면 재사용
    if (size < PyTuple_MAXSAVESIZE && (op = free_list[size]) != NULL) {
        assert(size != 0);
        free_list[size] = (PyTupleObject *) op->ob_item[0];
        numfree[size]--;

        ...
    
    else
    {
        ...
# 아니면 새로 할당
        op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
        
        ...
    }
    return op;
}

 

그렇기에 기존 사이즈를 벗어난 곳 위치에 값을 할당하려고 하면 아래와 같이 에러가 발생하게 구현되어 있습니다:

if (i < 0 || i >= Py_SIZE(op)) {
    Py_XDECREF(newitem);
    PyErr_SetString(PyExc_IndexError,
                    "tuple assignment index out of range");
    return -1;
}

 

고정된 값

튜플에 'a[1] = 2'와 같은 update가 발생하면, STORE_SUBSCR이라는 op_code가 발생하고 PyObject_SetItem을 호출합니다:

from dis import dis
dis("a[0] = 3")
# op_code 
1           0 LOAD_CONST               0 (3)
            2 LOAD_NAME                0 (a)
            4 LOAD_CONST               1 (0)
            6 STORE_SUBSCR
            8 LOAD_CONST               2 (None)
           10 RETURN_VALUE
           
           
# cpython/Python/ceval.c
case TARGET(STORE_SUBSCR): {
    ...
    err = PyObject_SetItem(container, sub, v);
    ...
}

튜플은 위의 PyObject_SetItem 내의 type_error를 발생시키게 됩니다:

type_error("'%.200s' object does not support item assignment", o);

 

최적화

잦은 메모리 할당은 성능에 악영향을 미칩니다. 특히, 작은 튜플이 코드 상에서 빈번히 생성되는데 이러한 경우에 메모리 할당을 피하는 것을 통해 파이썬에서는 최적화를 이루고 있습니다.

 

그러한 부분에서 아래의 4가지 변수가 관련되어 사용됩니다:

#define PyTuple_MAXSAVESIZE     20
#define PyTuple_MAXFREELIST  2000
static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];
static int numfree[PyTuple_MAXSAVESIZE];

위의 변수들이 새로운 튜플을 요청하에 tuple_alloc이 실행되는 경우, 그리고 튜플을 삭제하거나 scope을 벗어나 reference가 없어져 tuple_dealloc이 실행되는 경웨 사용됩니다:

 

• tuple_alloc이 실행되는 경우: (위의 '고정된 길이' 부분에서 설명한 것과 같이) 요청한 사이즈의 튜플이 이전에 메모리 할당되어 생성된 것이 있다면 꺼내서 사용하고, 아니면 새롭게 메모리를 할당합니다:

# tuple_alloc 함수
static PyTupleObject *
tuple_alloc(Py_ssize_t size)
{
    PyTupleObject *op;
    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
#if PyTuple_MAXSAVESIZE > 0
    if (size < PyTuple_MAXSAVESIZE && (op = free_list[size]) != NULL) {
        assert(size != 0);
        free_list[size] = (PyTupleObject *) op->ob_item[0];
        numfree[size]--;
        /* Inline PyObject_InitVar */
#ifdef Py_TRACE_REFS
        Py_SIZE(op) = size;
        Py_TYPE(op) = &PyTuple_Type;
#endif
        _Py_NewReference((PyObject *)op);
    }
    else
#endif
    {
        /* Check for overflow */
        if ((size_t)size > ((size_t)PY_SSIZE_T_MAX - (sizeof(PyTupleObject) -
                    sizeof(PyObject *))) / sizeof(PyObject *)) {
            return (PyTupleObject *)PyErr_NoMemory();
        }
        op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
        if (op == NULL)
            return NULL;
    }
    return op;
}

 

• tuple_delloc이 실행되는 경우: 튜플의 ob_item에 있는 포인터들의 레퍼런스를 없애고, 튜플의 사이즈가 PyTuple_MAXSAVESIZE보다 작고, numfree[튜플 사이즈]가 PyTuple_MAXFREELIST보다 작고, 타입이 튜플인 경우 free_list[튜플 사이즈]에 free_list에 넣어둡니다. 

# tuple_dealloc
static void
tupledealloc(PyTupleObject *op)
{
    Py_ssize_t i;
    Py_ssize_t len =  Py_SIZE(op);
    PyObject_GC_UnTrack(op);
    Py_TRASHCAN_BEGIN(op, tupledealloc)
    if (len > 0) {
        i = len;
        while (--i >= 0)
            Py_XDECREF(op->ob_item[i]);
#if PyTuple_MAXSAVESIZE > 0
        if (len < PyTuple_MAXSAVESIZE &&
            numfree[len] < PyTuple_MAXFREELIST &&
            Py_IS_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);
#if PyTuple_MAXSAVESIZE > 0
done:
#endif
    Py_TRASHCAN_END
}

그림으로 살펴보면 처음의 free_list와 numfree는 아래와 같은 상황입니다 (3.9.1 버젼에서 PyTuple_MAXSAVESIZE는 20): 

Image from Author

빈 튜플을 생성하고 reference를 제거하는 경우에는 Singleton과 같이 같은 것을 계속 사용합니다 (id가 모두 동일):

a = tuple()
print(id(a))
# 139811101286472
del a
b = tuple()
print(id(b))
# 139811101286472
c = tuple()
print(id(c))
# 139811101286472

Image from Author

튜플 사이즈가 1 <= 이고 <= PyTuple_MAXSAVESIZE인 경우에는 다음과 같이 튜플 생성 후 레퍼런스 삭제 시 free_list에 저장됩니다:

a = ("a", "b")
b = ("c", "d")
print(id(a))
print(id(b))
# 139810418320968
# 139810418390664
del a
del b

이미지로 그리면 아래와 같이 numfree[2]의 값이 2로 올라가고, free_list[2]에 2개의 PyTupleObject가 연결된 상태로 존재합니다:

Image from Author

아래와 같이 새로운 2 사이즈의 튜플을 생성하면 free_list[2]가 바라보고 있던 튜플의 id를 가진 튜플이 새로 생성되는 부분을 확인하실 수 있습니다:

c = ("e", "f")
print(id(c))
# 139810418390664 - 삭제한 b 튜플과 같은 id를 가짐

또한, free_list와 numfree는 아래와 같이 변경됩니다:

Image from Author

 

 

 

Referece

[1] CPython Internals - Tuple

[2] Fluent Python