python list implementation

 

 

해당 글은 http://www.laurentluce.com/posts/python-list-implementation/ 를 번역한 글입니다. 해당 글의 로직은 python버전에 따라 다를 수 있습니다. 

 

List object C structure

 

listobject.h의 소스 파일

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

list 오브젝트는 cpython의 위와 같은 c structure로 선언되어 있습니다.  ob_item는 list의 데이터에 대한 포인터입니다. allocated는 메모리에 할당된 슬롯의 개수입니다. list의 전체 사이즈는 ob_size로 표현되며, 크기는 아래와 같습니다.

 

- 0 <= ob_size <= allocated

- len(list) == ob_size

- ob_item == NULL일때 ob_size == allocated == 0

 

List.sort() 시엔 변화를 감지하기 위헤 -1을 일시적으로 할당합니다. 

 

 

리스트 초기화

빈 llist를 초기화하는 경우 어떤 일이 발생하는지 알아봅시다. 예를 들어 l = []입니다.

arguments: size of the list = 0
returns: list object = []
PyListNew:
    nbytes = size * size of global Python object = 0
    allocate new list object
    allocate list of pointers (ob_item) of size nbytes = 0
    clear ob_item
    set list's allocated var to 0 = 0 slots
    return list object

 

먼저 초기화를 실행하면 Objects/listobject.c의 PyList_New()를 실행합니다. 

PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op;

…...

    if (size <= 0)
        op->ob_item = NULL;
    else {
        op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
    }

    Py_SIZE(op) = size;
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

리스트의 사이즈와 할당된 슬롯의 차이가 중요합니다. 리스트의 사이즈는 len(l)와 같습니다. 

할당된 슬롯의 개수는 메모리에 할당된 것입니다. 종종 할당된 크기가 크기보다 클 수 있음을 알 수 있습니다. 새 요소가 목록에 추가될 때마다 realloc을 호출할 필요가 없습니다.

 

 

리스트 추가

L.append(1) , 리스트에 정수를 추가합니다. 

arguments: list object, new element
returns: 0 if OK, -1 if not
app1:
    n = size of list
    call list_resize() to resize the list to size n+1 = 0 + 1 = 1
    list[n] = list[0] = new element
    return 0

현재 l= []로 원소가 하나도 들어 있지 않습니다. 여기에서 리스트에 List의 사이즈를 가져온 후 list_resize()를 통해 슬롯 사이즈를 늘린 후 set_item()을 통해 새로운 엘리멘트를 할당합니다. 여기서 눈여겨볼 것은 list_resize()입니다. 

 

Objects/listobject.c 의 list_resize()

arguments: list object, new size
returns: 0 if OK, -1 if not
list_resize:
    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) = 3
    new_allocated += newsize = 3 + 1 = 4
    resize ob_item (list of pointers) to size new_allocated
    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().
* The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/

 

list_resize()를 보자. list_resize()의 로직은 list_resize를 너무 많이 호출하지 않도록 메모리를 과도하게 할당합니다. list의 할당 패턴은 다음과 같습니다. 0, 4, 8, 16, 25, 35, 46, 58, 72, 88,…

4개의 슬롯을 새롭게 할당한 후 첫 번째 슬롯엔 1이 들어갑니다. 

---

만약 n = 1000 인 경우 list의 크기는 27번 조정됩니다. 성장 패턴은 다음과 같습니다 : 4, 8, 16, 25, 35, 46, 58, 72, 88, 106, 126, 148, 173, 201, 233, 269, 309, 354, 405, 462, 526, 598 , 679, 771, 874, 990, 1120입니다. 이는 realloc에 대한 27번의 호출을 의미합니다. 

---

 

다음 다이어그램은 l[0]은 1이 할당되어 있습니다. 점선의 사각형은 아직 사용하지 않은 슬롯입니다. 

Append의 실행 시간은 O(1)입니다.

 

l.append (2) 요소를 하나 더 추가합니다. list_resize는 n + 1 = 2로 호출되지만 할당된 크기가 4이므로 더 많은 메모리를 할당할 필요가 없습니다. l.append (3), l.append (4)의 정수를 2 개 더 추가해도 마찬가지입니다. 다음 다이어그램은 우리가 지금까지 추가된 것을 보여줍니다.

 

 

 

Insert

위치 1에 새로운 정수 5를 삽입할 때 l.insert(1, 5),  내부적으로 어떤 일이 발생하는지 살펴보겠습니다. 

Ins1()을 호출합니다. 

arguments: list object, where, new element
returns: 0 if OK, -1 if not
ins1:
    resize list to size n+1 = 5 -> 4 more slots will be allocated
    starting at the last element up to the offset where, right shift each element
    set new element at offset where
    return 0

static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
    Py_ssize_t i, n = Py_SIZE(self);
    PyObject **items;

 …………….. . . . . . . . . . .

   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;
}

 

insert 되는 해당 요소의 자리 이후의 요소들을 전부 옮긴 후 마지막에 insert()의 요소를 해당 슬롯에 넣어줍니다. 

 

 

 

점선의 사각형은 새롭게 할당된 슬롯으로 아직 사용하지 않는 부분입니다. 8개의 슬롯이 할당되었지만, 리스트의 사이즈는 5입니다. 

Insert시 실행 시간은 O(n)입니다. 

 

 

 

 

POP

마지막 요소를 pop 할 경우 l.pop() , listpop()을 호출합니다. listpop()에서 list_resize()를 호출하며, 크기가 할당된 절반보다 작으면 list_ass_slice()를 호출하여 슬롯을 축소합니다.

 

arguments: list object
returns: element popped
listpop:
    if list empty:
        return null
    resize list with size 5 - 1 = 4. 4 is not less than 8/2 so no shrinkage
    set list object size to 4
    return last element

Pop 연산의 실행 시간은 O(1)입니다. 

 

 

 

l.pop()을 통해 슬롯 4번째가 여전히 정수 4를 가리키는 걸 볼 수 있지만 중요한 것은 현재 크기가 4입니다. 

하나 더 요소를 pop()합니다. List_resize()에서 size - 1 = 4 - 1 = 3은 할당된 슬롯의 절반보다 작으므로 슬롯은 6개로 줄어들로 목록의 크기는 3이 됩니다. 

 

 

 

 

Remove

특정 요소를 제거하기 위해 l.remove(5)를 호출하면 listremove()를 호출합니다.

arguments: list object, element to remove
returns none if OK, null if not
listremove:
    loop through each list element:
        if correct element:
            slice list between element's slot and element's slot + 1
            return none
    return null

 

요소를 지우고 리스트를 자르기 위해 list_ass_slice()가 호출되며, 이 작업이 어떻게 동작하는지  흥미롭습니다. 

이 작업은 오프셋 1의 위치에 오프셋 2가 들어가며 (5의 위치에 2가 들어감) 1에 위해 했던 5의 요소는 삭제됩니다.

arguments: list object, low offset, high offset
returns: 0 if OK
list_ass_slice:
    copy integer 5 to recycle list to dereference it
    shift elements from slot 2 to slot 1
    resize list to 5 slots
    return 0

 

삭제 연산의 실행 시간은 o(n)입니다.