[CPython]CPython의 List 구현 살펴보기

이번 포스팅에서는 CPython의 소스코드를 통해서 Python List가 어떻게 동작하는지 알아봅니다.

 

Python List를 C언어의 Array와 사뭇 다릅니다

Python List	C Array
Type 무관	Type 고정
Element크기 고정	Type에 따라 변함
malloc 불필요	malloc 필요

 

이때, Python List의 특징을 보면 C의 Pointer Array와 상당히 비슷한 것을 볼 수 있습니다.

(Pointer 특성상 고정된 크기(주소값)를 차지하고, Type은 void Pointer를 이용할경우)

 

그러면, 이제 Cpython 내의 PyListObject의 정의를 살펴보겠습니다.

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;
    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

source code : cpython/Include/cpython/listobject.h

#define PyObject_VAR_HEAD      PyVarObject ob_base;

typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;

source code : cpython/Include/object.h

PyObject는 ListObject를 설명하는 context의 일종 입니다.

 

allocated의 경우 ListObject에 할당 + 잔여배열의 총 크기를 의미합니다

(Python List의 경우 실제 선언한 Array보다 예비로 더 많은 Array를 할당합니다.이는 cpython/Objects/listobject.c 내 list_resize로 확인이 가능합니다)

 

여기서 PyObject **ob_item이 실제 Python List의 Element를 가지고 있는 이중 포인터가 됩니다

 

즉, Python List의 경우 C언어의 여유 공간이 확보된 Type이 PyObject인 2중 Pointer Array가 됩니다.

 

아래 CPython으로 정의된 List.append() Method에서 확인이 가능합니다.

/* in cpython/include/cpython/listobject.h
 * #define PyList_SET_ITEM(op, i, v) _Py_RVALUE(_PyList_CAST(op)->ob_item[i] = (v))
 * self를 한번더 PY_list를 Casting하고 ob_item이 2중 pointer이므로 v를 할당
 */

static int
app1(PyListObject *self, PyObject *v)
{
    Py_ssize_t n = PyList_GET_SIZE(self);

    assert (v != NULL);
    assert((size_t)n + 1 < PY_SSIZE_T_MAX);
    if (list_resize(self, n+1) < 0)
        return -1;

    Py_INCREF(v);
    PyList_SET_ITEM(self, n, v);
    return 0;
}



/* self를 받아서 PyList Pointer로 Casting
 * newitem은 PyObject Pointer로, 추가될 때 기존 self의 listsize를 1 늘린다음에 newitem의 reference count를 증가시키고
 * self의 ob_item의 배열에 newitem을 추가시킵니다.
 */

int
PyList_Append(PyObject *op, PyObject *newitem)
{
    if (PyList_Check(op) && (newitem != NULL))
        return app1((PyListObject *)op, newitem);
    PyErr_BadInternalCall();
    return -1;
}

source code : cpython/Objects/listobject.c

Python List에 append로 Value 이외에 List를 Append할 수 있습니다.

 

PyList_Check(op)로 self는 항상 PyListObject이지만 Append되는 값은 PyObject이기만 하면 됩니다.

(PyObject는 PyListObject를 Casting이 가능한것을 확인할 수 있습니다.)

 

즉, PyListObject의 Element에 PyListObject가 올 수도, 아닐 수도 있게 되는 것이죠

 

위에 설면된 소스코드를 그림으로 정리하면, 아래와 비슷한 이미지가 나올겁니다.

이상 Python List의 정체에 대해서 확인 했습니다.