python list를 어떻게 효율적으로 쓸까 고민하다가 list에 대해서 공부를 좀 했다.

궁금증은 다음 두 가지였다.

• python list의 구조는 어떻게 생겼는지… item 갯수를 알 때 효율적으로 넣는 방법(preallocation)
• python list의 처음 alloc size와 append의 동작 방식

python list 구조와 preallocation

사실 처음에 preallocation을 하려면 어떻게 할까 찾아봤는데, 답변들이 [None] * size를 쓰면 된다고 했다. 이러면 size가 다른 객체들을 어떻게 넣지? 의문이 생겼고, 그래서 생긴 꼴을 찾아봤다.

참조 1 - PyListObject 구조를 보면 다음처럼 생겼다.

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

대충 봐도 pointer로 item들을 가지고 있겠거니… 생각이 들며 다음 코드를 보면 확실해진다.

참조 2 - python list setitem

PyList_SetItem(PyObject *op, Py_ssize_t i,
               PyObject *newitem)
{
    PyObject **p;
    if (!PyList_Check(op)) {
        Py_XDECREF(newitem);
        PyErr_BadInternalCall();
        return -1;
    }
    if (i < 0 || i >= Py_SIZE(op)) {
        Py_XDECREF(newitem);
        PyErr_SetString(PyExc_IndexError,
                        "list assignment index out of range");
        return -1;
    }
    p = ((PyListObject *)op) -> ob_item + i
    Py_XSETREF(*p, newitem);
    return 0;
}

마지막 세 줄을 보면

1. pointer를 옮기고
2. item을 포인팅하고
3. return

이다.

따라서 [None] * size는 포인터 배열을 한번에 alloc하는 정도로, append 시 포인터 배열 realloc에 대한 overhead만 줄여준다.

python list의 처음 alloc size와 append의 동작 방식

그러고보면 처음에 얼마나 메모리를 잡고있으며, append를 하면 어떻게 메모리를 할당하나 궁금해졌다.

결론은

• 처음에는 한칸도 alloc하지 않는다.
• 하나라도 append를 하면 4개를 alloc한다.
• 그 뒤로 4개 이상 들어오면 8개로 realloc하며, 이를 반복!

요런 식으로 동작한다.

알아본 방법은 코드로 대체한다.

Python 3.5.3 (default, Jan 17 2018, 16:36:00)
[GCC 5.4.0 20160609] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> l = [None] * 10
>>> l
[None, None, None, None, None, None, None, None, None, None]
>>> sys.getsizeof(l)
144
>>> sys.getsizeof(None)
16
>>> a = []
>>> sys.getsizeof(a)
64
>>> b = [None] * 100
>>> sys.getsizeof(b)
864
>>> a = [1]
>>> sys.getsizeof(a)
72
>>> a = []
>>> a.append(1)
>>> sys.getsizeof(a)
96