파이썬 리스트 내부구조 (Python List Internals)
파이썬 리스트는 mutable 시퀀스(sequence)로, 주로 유사한(homogeneous) 아이템들의 콜렉션(collections)을 저장하기 위해서 사용합니다. 그렇기에 시퀀스가 기본적으로 가지는 연산자(collections.abc.Sequence ABC)들은 리스트에도 구현되어 있습니다.
이번 글에서는 CPython에서의 리스트 내부구조를 아래와 같은 사항을 중점으로 살펴보겠습니다:
- 리스트 내부구조와 기본 연산
- 메모리 할당
관련글:
리스트 내부구조와 기본 연산
cpython 코드 상에서 파이썬 리스트는 다음과 같은 형태를 가지고 있습니다:
흔히 인지하는 리스트의 길이, len(list_a)는 PyVarObject의 ob_size에 기록됩니다. PyListObject의 allocated에는 리스트에 할당된 크기를 기록합니다. 리스트에는 항상 리스트 크기(길이)에 비례해 over-allocate되기 때문에 0 <= ob_size <= allocated 가 언제나 성립합니다.
PyList_Type은 아래와 같은 메소드를 가집니다 (Objects/listobject.c#L2766):
static PyMethodDef list_methods[] = {
{"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, "x.__getitem__(y) <==> x[y]"},
LIST___REVERSED___METHODDEF
LIST___SIZEOF___METHODDEF
LIST_CLEAR_METHODDEF
LIST_COPY_METHODDEF
LIST_APPEND_METHODDEF
LIST_INSERT_METHODDEF
LIST_EXTEND_METHODDEF
LIST_POP_METHODDEF
LIST_REMOVE_METHODDEF
LIST_INDEX_METHODDEF
LIST_COUNT_METHODDEF
LIST_REVERSE_METHODDEF
LIST_SORT_METHODDEF
{"__class_getitem__", (PyCFunction)Py_GenericAlias, METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
{NULL, NULL} /* sentinel */
};
Append
list_a = []
list_a.append(1)위와 같은 리스트 append는 PyList_Append라는 cpython 함수를 통해 실행됩니다. PyList_Append는 내부에서 app1을 실행하고, app1 내에서는 리스트 최대 사이즈(PY_SSIZE_T_MAX)를 넘는지 확인, resize(크기 재조정 필요 시 재조정) 후 Reference count를 올리고 아이템을 해당 index에 설정합니다 (resize 관련해서는 아래 메모리 부분에서 자세히 알아봅니다):
static int
app1(PyListObject *self, PyObject *v)
{
Py_ssize_t n = PyList_GET_SIZE(self);
assert (v != NULL);
if (n == PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"cannot add more objects to list");
return -1;
}
if (list_resize(self, n+1) < 0)
return -1;
Py_INCREF(v);
PyList_SET_ITEM(self, n, v);
return 0;
}
static PyObject *
list_append(PyListObject *self, PyObject *object)
{
if (app1(self, object) == 0)
Py_RETURN_NONE;
return NULL;
}
Insert
append와 유사하게 PyList_Insert 함수 내부에서 다른 함수 ins1를 호출하는 것을 확인할 수 있습니다.
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
Py_ssize_t i, n = Py_SIZE(self);
PyObject **items;
if (v == NULL) {
PyErr_BadInternalCall();
return -1;
}
if (n == PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"cannot add more objects to list");
return -1;
}
if (list_resize(self, n+1) < 0)
return -1;
if (where < 0) {
where += n;
if (where < 0)
where = 0;
}
if (where > n)
where = n;
items = self->ob_item;
for (i = n; --i >= where; )
items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;
return 0;
}
static PyObject *
list_insert_impl(PyListObject *self, Py_ssize_t index, PyObject *object)
{
if (ins1(self, index, object) == 0)
Py_RETURN_NONE;
return NULL;
}
Remove
리스트에서 특정 값을 가진 원소를 제거하는 것은 list.remove 메소드를 통해 가능합니다. 아래에서 리스트 안의 값들을 iteration하며 그 값을 PyObject_RichCompareBool을 통해 비교하고 같다면 list_ass_slice 메소드를 통해 제거하는 것을 볼 수 있습니다:
static PyObject *
list_remove(PyListObject *self, PyObject *value)
{
Py_ssize_t i;
for (i = 0; i < Py_SIZE(self); i++) {
PyObject *obj = self->ob_item[i];
Py_INCREF(obj);
int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
Py_DECREF(obj);
if (cmp > 0) {
if (list_ass_slice(self, i, i+1,
(PyObject *)NULL) == 0)
Py_RETURN_NONE;
return NULL;
}
else if (cmp < 0)
return NULL;
}
PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
return NULL;
}
메모리 할당
파이썬 리스트에 대한 cpython에서의 메모리 할당은 아래 list_resize 메소드를 중심으로 진행됩니다:
/* Ensure ob_item has room for at least newsize elements, and set
* ob_size to newsize. If newsize > ob_size on entry, the content
* of the new slots at exit is undefined heap trash; it's the caller's
* responsibility to overwrite them with sane values.
* The number of allocated elements may grow, shrink, or stay the same.
* Failure is impossible if newsize <= self.allocated on entry, although
* that partly relies on an assumption that the system realloc() never
* fails when passed a number of bytes <= the number of bytes last
* allocated (the C standard doesn't guarantee this, but it's hard to
* imagine a realloc implementation where it wouldn't be true).
* Note that self->ob_item may change, and even if newsize is less
* than ob_size on entry.
*/
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated, num_allocated_bytes;
Py_ssize_t allocated = self->allocated;
/* Bypass realloc() when a previous overallocation is large enough
to accommodate the newsize. If the newsize falls lower than half
the allocated size, then proceed with the realloc() to shrink the list.
*/
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SET_SIZE(self, newsize);
return 0;
}
/* This over-allocates proportional to the list size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* Add padding to make the allocated size multiple of 4.
* The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
* Note: new_allocated won't overflow because the largest possible value
* is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
*/
new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
/* Do not overallocate if the new size is closer to overalocated size
* than to the old size.
*/
if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
new_allocated = ((size_t)newsize + 3) & ~(size_t)3;
if (newsize == 0)
new_allocated = 0;
num_allocated_bytes = new_allocated * sizeof(PyObject *);
items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
if (items == NULL) {
PyErr_NoMemory();
return -1;
}
self->ob_item = items;
Py_SET_SIZE(self, newsize);
self->allocated = new_allocated;
return 0;
}
리스트 사이즈가 증가함에 따라서 어느 정도가 allocated되는지 나타내는 위 코드의 알고리즘은, 아래와 같은 파이썬 코드로 간략화하여 알아 볼 수 있습니다:
def new_allocated(newsize):
return (newsize + (newsize >> 3) + 6) & (~3)
allocated = 0
for i in range(100):
if allocated >= i & i >= (allocated / 2):
continue
new = new_allocated(i)
if new != allocated:
print(f"Size changed: i - {i}, new - {new}")
allocated = new
# 출력
Size changed: i - 1, new - 4
Size changed: i - 5, new - 8
Size changed: i - 9, new - 16
Size changed: i - 17, new - 24
Size changed: i - 25, new - 32
Size changed: i - 33, new - 40
Size changed: i - 41, new - 52
Size changed: i - 53, new - 64
Size changed: i - 65, new - 76
Size changed: i - 77, new - 92
Size changed: i - 93, new - 108
코드 코멘트 상에 언급된 것과 같이 0, 4, 8, 16, 24, 32 ... 패턴으로 할당되는 사이즈가 증가하는 것을 볼 수 있습니다. 또한, pop과 같이 리스트의 원소를 제거하여 할당된 크기에서 사용하지 않는 부분이 많아지면 할당을 shrink하게 됩니다.
Reference
[2] CPython Internals - List