[Python] List Reallocation in CPython

참고: Python C API - List Objects, CPython listobject.c

list 재할당이란?

Python의 list는 내부적으로 연속된 배열처럼 동작한다. 하지만 Python object 자체를 배열에 직접 저장하는 것은 아니고, 각 element를 가리키는 pointer들을 저장한다.

개념적으로는 다음과 비슷하다.

list object
  ├─ size
  ├─ allocated
  └─ ob_item -> [PyObject*, PyObject*, PyObject*, ...]

여기서 중요한 값은 두 가지이다.

예를 들어 Python에서 보는 길이는 len(a)이다. 하지만 CPython 내부에는 len(a)보다 더 큰 공간이 미리 잡혀 있을 수 있다.

a = []
a.append(1)
a.append(2)

이때 len(a)는 2이지만, 내부 배열 capacity는 2보다 클 수 있다. 이 여분의 공간 덕분에 매번 append()할 때마다 메모리를 새로 할당하지 않아도 된다.

Python 변수 재할당과 list 내부 재할당

먼저 용어를 구분해야 한다.

Python에서 다음 코드는 변수 a가 다른 list object를 가리키게 만드는 재할당이다.

a = [1, 2, 3]
a = [4, 5, 6]

이 경우 기존 list를 수정하는 것이 아니라, a라는 이름이 새 list object를 참조하게 된다.

반면 다음 코드는 같은 list object를 유지하면서 내부 element를 바꾼다.

a = [1, 2, 3]
a[0] = 10

또 다음 코드는 같은 list object의 길이를 늘리면서 내부 배열이 재할당될 수 있다.

a = []
a.append(1)
a.append(2)

이 글에서 말하는 list 재할당은 주로 세 번째 경우이다. 즉 list object 자체가 아니라, list가 들고 있는 내부 element pointer 배열이 커지거나 줄어드는 현상을 말한다.

id로 확인하기

변수 재할당과 list 내부 변경은 id()로 구분할 수 있다.

a = [1, 2, 3]
print(id(a))

a.append(4)
print(id(a))

append()는 같은 list object를 수정하므로 보통 id(a)는 그대로 유지된다.

반면 새 list를 대입하면 id가 바뀐다.

a = [1, 2, 3]
print(id(a))

a = a + [4]
print(id(a))

a + [4]는 새 list를 만든 뒤 a가 그 새 list를 가리키게 한다.

정리하면 다음과 같다.

CPython의 list 구조

Python C API 문서에서 list object는 PyListObject로 표현된다. 또 PyList_Size()는 Python의 len(list)와 같은 길이를 반환한다고 설명한다.

CPython 내부 구현에서는 list가 대략 다음 정보를 가진다.

PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;

정확한 struct 정의는 CPython 내부 header에 있지만, 핵심은 ob_item과 allocated이다.

Python list는 element object를 직접 연속 저장하지 않는다. 각 element는 별도 Python object이고, list는 그 object를 가리키는 pointer 배열을 관리한다.

a = [10, "hello", object()]

위 list는 서로 다른 type의 object를 담을 수 있다. 그 이유는 list 내부 배열이 int, str 값을 직접 담는 것이 아니라 PyObject* pointer를 담기 때문이다.

append와 resize

append()를 호출하면 CPython은 list 끝에 item을 추가한다. 그런데 현재 size가 allocated보다 작으면 이미 여유 공간이 있으므로 pointer 하나만 넣으면 된다.

size < allocated

이 경우에는 큰 메모리 재할당이 필요 없다.

반대로 여유 공간이 없으면 내부 배열을 더 큰 공간으로 재할당해야 한다.

size == allocated

CPython의 listobject.c에는 list 크기를 조정하는 내부 함수 list_resize()가 있다. 이 함수는 새 크기가 기존 allocated 범위 안에 충분히 들어가면 실제 realloc()을 피하고 size만 바꾼다.

즉 append()는 매번 메모리를 새로 할당하는 것이 아니다. 여유 공간이 있을 때는 O(1)에 가깝게 끝나고, 여유 공간이 없을 때만 더 큰 배열을 확보한다.

C 코드로 보는 append 흐름

Python에서 다음 코드를 실행한다고 하자.

a = []
a.append(obj)

CPython 내부에서는 대략 다음 흐름으로 처리된다. 아래 코드는 실제 listobject.c를 설명용으로 단순화한 것이다.

int PyList_Append(PyObject *op, PyObject *newitem) {
    if (PyList_Check(op) && newitem != NULL) {
        return _PyList_AppendTakeRef(
            (PyListObject *)op,
            Py_NewRef(newitem)
        );
    }

    PyErr_BadInternalCall();
    return -1;
}

핵심은 PyListObject *로 list를 다루고, 추가할 object의 reference를 넘긴다는 점이다. 실제로 끝에 item을 넣으려면 현재 길이보다 1 큰 크기가 필요하다.

int _PyList_AppendTakeRefListResize(PyListObject *self, PyObject *newitem) {
    Py_ssize_t len = Py_SIZE(self);

    if (list_resize(self, len + 1) < 0) {
        Py_DECREF(newitem);
        return -1;
    }

    self->ob_item[len] = newitem;
    return 0;
}

여기서 중요한 줄은 다음이다.

list_resize(self, len + 1)

append()는 단순히 마지막 slot에 값을 넣는 것처럼 보이지만, 그 전에 list가 len + 1개의 element를 담을 수 있는지 확인한다. 여유 공간이 있으면 size만 바꾸고, 여유 공간이 없으면 내부 배열을 재할당한다.

C 코드로 보는 list_resize

list_resize()의 핵심은 두 단계로 볼 수 있다.

1. 기존 capacity로 충분하면 실제 memory realloc을 피한다.
2. 부족하면 over-allocation으로 더 큰 배열을 잡는다.

설명용으로 줄이면 다음과 같다.

static int list_resize(PyListObject *self, Py_ssize_t newsize) {
    Py_ssize_t allocated = self->allocated;

    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        Py_SET_SIZE(self, newsize);
        return 0;
    }

    size_t new_allocated =
        ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

    if (newsize == 0) {
        new_allocated = 0;
    }

    PyObject **items = PyMem_Realloc(
        self->ob_item,
        new_allocated * sizeof(PyObject *)
    );

    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }

    self->ob_item = items;
    Py_SET_SIZE(self, newsize);
    self->allocated = new_allocated;
    return 0;
}

이 코드를 기준으로 보면 size와 allocated가 분리되어 있다는 점이 명확하다.

Py_SET_SIZE(self, newsize);
self->allocated = new_allocated;

Py_SET_SIZE는 Python에서 보이는 list 길이를 바꾼다. allocated는 내부 배열 capacity를 나타낸다.

다음 조건은 resize를 피하는 빠른 경로이다.

if (allocated >= newsize && newsize >= (allocated >> 1)) {
    Py_SET_SIZE(self, newsize);
    return 0;
}

의미는 다음과 같다.

newsize가 기존 allocated 안에 들어간다.
그리고 너무 많이 줄어든 것도 아니다.
그러면 memory 재할당 없이 size만 바꾼다.

반대로 capacity가 부족하면 PyMem_Realloc()으로 내부 pointer 배열을 다시 잡는다.

PyMem_Realloc(self->ob_item, new_allocated * sizeof(PyObject *))

이때 self->ob_item 주소는 바뀔 수 있다. 하지만 Python level의 list object 주소, 즉 id(a)는 그대로 유지될 수 있다.

list object는 유지
ob_item pointer 배열은 교체 가능

C 코드로 보는 capacity 증가식

CPython의 over-allocation 계산은 설명용으로 보면 다음과 같다.

new_allocated = newsize + (newsize >> 3) + 6;
new_allocated = new_allocated & ~3;

newsize >> 3은 대략 newsize / 8이다. 즉 새 크기보다 약 12.5% 정도 여유를 더한다. 그리고 마지막에 & ~3을 적용해 4의 배수에 맞춘다.

예를 들어 newsize가 17이라면 대략 다음처럼 계산된다.

newsize          = 17
newsize >> 3     = 2
+ 6              = 25
4의 배수로 정리  = 24

그래서 실제 필요한 길이는 17이지만, 내부 capacity는 24가 될 수 있다.

이 방식 덕분에 다음 append 몇 번은 메모리 재할당 없이 진행된다.

len: 17, allocated: 24
len: 18, allocated: 24
len: 19, allocated: 24
...
len: 24, allocated: 24

그 다음 len이 25가 되려는 순간 다시 resize가 필요해진다.

C 코드로 보는 인덱스 재할당

다음 Python 코드는 list 길이를 바꾸지 않는다.

a = [1, 2, 3]
a[1] = 20

CPython C API 관점에서는 PyList_SetItem() 동작과 연결해서 이해할 수 있다. 설명용으로 단순화하면 다음과 같다.

int PyList_SetItem(PyObject *op, Py_ssize_t i, PyObject *newitem) {
    PyListObject *self = (PyListObject *)op;

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

    PyObject *olditem = self->ob_item[i];
    self->ob_item[i] = newitem;
    Py_XDECREF(olditem);

    return 0;
}

여기서는 list_resize()가 호출되지 않는다. 이미 존재하는 slot 하나를 새 object pointer로 교체할 뿐이다.

ob_item[1]이 가리키던 PyObject*를 새 PyObject*로 바꾼다.

따라서 index assignment는 길이와 capacity를 바꾸지 않는다.

a[1] = 20

이 코드는 list 내부 배열을 키우는 작업이 아니라, 특정 위치의 pointer를 교체하는 작업이다.

over-allocation

CPython list는 크기를 딱 맞게만 늘리지 않는다. 조금 더 크게 잡는다. 이 전략을 over-allocation이라고 한다.

예를 들어 element 1개를 추가할 때 내부 slot을 정확히 1개만 늘리면, 다음 append에서 또 재할당이 필요하다. 이렇게 되면 반복적인 append가 비싸진다.

그래서 CPython은 list를 늘릴 때 약간의 여유 공간을 함께 확보한다. listobject.c의 resize 로직은 새 크기에 비례한 여분을 더하고, 특정 배수에 맞춰 capacity를 정리한다.

CPython source comment에는 성장 패턴이 다음과 같이 제시되어 있다.

0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...

핵심은 다음과 같다.

list가 커질 때 매번 1칸씩만 늘리지 않는다.
조금 더 크게 잡아서 다음 append 비용을 줄인다.

이 덕분에 append()를 많이 반복해도 평균적으로 효율적이다. 엄밀히 말하면 list append는 amortized O(1)로 설명된다.

append가 가끔 느릴 수 있는 이유

대부분의 append()는 빠르다. 하지만 capacity가 꽉 찬 순간에는 다음 작업이 필요하다.

1. 더 큰 pointer 배열을 할당한다.
2. 기존 pointer들을 새 배열로 옮긴다.
3. list의 ob_item이 새 배열을 가리키게 한다.
4. allocated 값을 갱신한다.
5. 새 item pointer를 끝에 넣는다.

이 순간의 append는 일반 append보다 비싸다. 하지만 over-allocation 덕분에 이런 비싼 append가 매번 발생하지 않는다.

예를 들어 다음 코드는 대부분 빠르게 동작하지만, 중간중간 resize가 발생한다.

a = []

for i in range(1_000_000):
    a.append(i)

전체적으로는 효율적이지만, 내부적으로는 몇 번의 큰 재할당이 섞여 있다.

sys.getsizeof로 관찰하기

내부 capacity를 Python에서 직접 공식 API로 보는 방법은 없다. 하지만 sys.getsizeof()로 list object의 메모리 크기가 계단식으로 늘어나는 것을 관찰할 수 있다.

import sys


a = []
last_size = sys.getsizeof(a)

for i in range(100):
    a.append(i)
    current_size = sys.getsizeof(a)

    if current_size != last_size:
        print(len(a), current_size)
        last_size = current_size

출력은 환경과 Python build에 따라 달라질 수 있다. 하지만 보통 매 append마다 크기가 변하지 않고, 특정 길이에서만 커지는 것을 볼 수 있다.

이것이 over-allocation의 흔적이다.

인덱스 재할당

다음 코드는 list 길이를 바꾸지 않는다.

a = [1, 2, 3]
a[1] = 20

CPython C API로 보면 이는 PyList_SetItem()과 대응되는 동작으로 이해할 수 있다. 문서에서는 이 함수가 특정 index의 item을 설정하고, 범위를 벗어나면 IndexError를 설정한다고 설명한다.

인덱스 재할당은 내부 배열 capacity를 바꾸지 않는다. 이미 존재하는 slot의 pointer를 새 object pointer로 교체하는 작업이다.

기존 ob_item[1] -> 새 PyObject*

따라서 a[1] = 20은 list resize와는 다른 문제이다. 길이가 그대로라면 내부 배열을 키울 필요가 없다.

slice 재할당

slice assignment는 list 길이를 바꿀 수 있다.

a = [1, 2, 3, 4]
a[1:3] = [10, 20, 30, 40]

이 경우 [2, 3] 두 개가 [10, 20, 30, 40] 네 개로 바뀐다. 결과적으로 list 길이는 늘어난다.

[1, 10, 20, 30, 40, 4]

Python C API 문서에서 PyList_SetSlice()는 list의 특정 구간을 다른 list 내용으로 설정하는 동작과 대응된다고 설명한다. slice assignment는 길이가 변할 수 있으므로 내부적으로 resize가 필요할 수 있다.

반대로 길이가 같은 slice replacement라면 capacity 변화가 필요 없을 수도 있다.

a = [1, 2, 3]
a[1:2] = [20]

이 경우 길이는 그대로 3이다.

a = a + b 와 a += b

list를 합칠 때도 재할당 관점이 중요하다.

a = [1, 2]
b = [3, 4]

a = a + b

a + b는 새 list를 만든다. 따라서 a는 새 list object를 가리키게 된다.

a = [1, 2]
old_id = id(a)

a = a + [3, 4]

print(old_id == id(a))  # False

반면 +=는 list의 in-place extend처럼 동작한다.

a = [1, 2]
old_id = id(a)

a += [3, 4]

print(old_id == id(a))  # True

다만 id(a)가 유지된다는 것은 list object가 유지된다는 뜻이다. 내부 ob_item 배열은 capacity가 부족하면 재할당될 수 있다.

즉 다음 두 층을 나누어 봐야 한다.

Python object identity: id(a)
CPython internal array identity: ob_item

+=는 보통 첫 번째는 유지하지만, 두 번째는 바뀔 수 있다.

list comprehension과 append

다음 두 코드는 결과가 같다.

a = []

for i in range(10):
    a.append(i)

a = [i for i in range(10)]

둘 다 list를 만든다. 다만 list comprehension은 Python interpreter가 최적화된 방식으로 list를 구성할 수 있어 보통 더 간결하고 빠르다.

하지만 원리는 여전히 list object와 내부 pointer 배열을 만든다는 점에서 같다. 결과 list는 element object들을 가리키는 pointer 배열을 가진다.

미리 크기를 잡는 방식

반복 append 대신 크기를 미리 아는 경우에는 다음처럼 list를 만들 수 있다.

n = 1000
a = [None] * n

for i in range(n):
    a[i] = i

이 방식은 처음부터 길이 n인 list를 만든다. 그 뒤 index assignment를 하므로 append에 따른 resize가 발생하지 않는다.

다만 무조건 이 방식이 좋은 것은 아니다. 코드가 더 장황해지고, 초기값이 의미 없는 None으로 채워진다.

대부분의 일반적인 Python code에서는 다음 방식이 충분히 좋다.

a = []
for item in items:
    a.append(transform(item))

또는 더 Pythonic하게는 list comprehension을 사용한다.

a = [transform(item) for item in items]

줄어들 때도 재할당될까?

list는 커질 때만 재할당되는 것이 아니다. 크기가 많이 줄면 내부 배열도 줄어들 수 있다.

CPython list_resize()는 새 size가 기존 allocated의 절반 이상이면 실제 재할당을 피하고 size만 줄인다. 반대로 많이 줄어들면 메모리를 줄이기 위해 재할당이 발생할 수 있다.

예를 들어 다음 코드는 list 길이를 줄인다.

a = list(range(1000))
del a[:900]

이때 내부 capacity가 줄어들 수 있다. 하지만 조금 줄어드는 정도라면 남은 여유 공간을 유지할 수 있다.

이 전략은 grow/shrink가 반복될 때 매번 메모리를 재할당하는 비용을 줄이기 위한 것이다.

C++ std::vector와 비교

Python list는 C++의 std::vector와 자주 비교된다. 둘 다 동적 배열처럼 동작하고, 뒤에 원소를 추가할 때 capacity가 부족하면 더 큰 배열을 확보한다.

하지만 내부에 저장하는 대상이 다르다.

Python list는 object를 직접 저장하지 않는다. 각 element는 Python object이고, list 내부 배열은 그 object를 가리키는 pointer를 저장한다.

Python list
ob_item -> [PyObject*, PyObject*, PyObject*]
              |          |          |
             int        str       object

반면 std::vector<int>는 int 값을 연속된 메모리에 직접 저장한다.

std::vector<int>
data -> [int, int, int, int]

std::vector<std::string>이라면 std::string object들이 연속된 메모리에 놓인다.

std::vector<std::string>
data -> [std::string, std::string, std::string]

이 차이 때문에 재할당 비용도 달라진다.

append와 push_back

Python의 append()는 C++ vector의 push_back()과 비슷하다.

Python:

a = []
a.append(10)

C++:

#include <vector>

std::vector<int> v;
v.push_back(10);

둘 다 capacity가 남아 있으면 끝에 원소를 추가한다. capacity가 부족하면 더 큰 배열을 할당한다.

하지만 재할당 시 실제로 옮기는 것은 다르다.

Python list는 PyObject* pointer들을 옮긴다.

PyObject **items = PyMem_Realloc(
    self->ob_item,
    new_allocated * sizeof(PyObject *)
);

C++ vector는 T object들을 새 storage로 move 또는 copy한다. 개념적으로는 다음과 같다.

T* new_data = allocate(new_capacity);

for (size_t i = 0; i < size; i++) {
    construct(new_data + i, std::move(old_data[i]));
}

destroy_old_objects();
deallocate(old_data);

따라서 std::vector<T>에서 T가 크거나 move/copy 비용이 크면 재할당 비용도 커질 수 있다. Python list는 pointer를 옮기므로 배열 재할당 자체는 pointer 이동에 가깝지만, 각 element는 별도 Python object로 존재하기 때문에 object overhead가 있다.

capacity 확인 차이

C++ vector는 capacity를 직접 확인할 수 있다.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;

    for (int i = 0; i < 20; i++) {
        v.push_back(i);
        std::cout << "size=" << v.size()
                  << ", capacity=" << v.capacity()
                  << '\n';
    }
}

Python list는 공식적으로 capacity를 보여주는 API가 없다. 대신 sys.getsizeof()로 메모리 크기 변화를 간접 관찰할 수 있다.

import sys


a = []

for i in range(20):
    a.append(i)
    print(len(a), sys.getsizeof(a))

std::vector는 size()와 capacity()가 public API이다. Python list의 allocated는 CPython 내부 구현 detail이다.

reserve와 Python list

C++ vector는 미리 capacity를 확보할 수 있다.

std::vector<int> v;
v.reserve(1000);

for (int i = 0; i < 1000; i++) {
    v.push_back(i);
}

reserve(1000)은 size를 바꾸지 않고 capacity만 확보한다. 따라서 이후 push_back() 중 재할당을 줄일 수 있다.

Python list에는 reserve()에 해당하는 public method가 없다.

a = []
# a.reserve(1000) 같은 API는 없다.

대신 크기를 알고 있다면 다음처럼 미리 길이를 만든 뒤 index assignment를 사용할 수 있다.

n = 1000
a = [None] * n

for i in range(n):
    a[i] = i

하지만 이 방식은 reserve()와 정확히 같지 않다. [None] * n은 capacity만 확보하는 것이 아니라 실제 길이가 n인 list를 만든다.

즉 C++ vector 기준으로 비교하면 다음과 더 가깝다.

std::vector<int> v(1000);

Python에는 다음과 같은 차이가 있다.

C++ vector reserve: capacity만 증가, size는 그대로
Python [None] * n: size도 n으로 증가

pointer invalidation 비교

C++ vector는 재할당이 발생하면 기존 element를 가리키던 pointer, reference, iterator가 invalidation된다.

std::vector<int> v;
v.push_back(1);

int* p = &v[0];

v.push_back(2);
v.push_back(3);
v.push_back(4);

// 재할당이 발생했다면 p는 더 이상 안전하지 않을 수 있다.

vector 내부 storage가 새 위치로 옮겨지면 &v[0] 주소도 바뀔 수 있다.

Python에서는 일반 Python code에서 list 내부의 ob_item pointer를 직접 잡지 않는다. 따라서 이런 식의 pointer invalidation을 직접 경험하는 경우는 드물다.

a = [object()]
x = a[0]

a.append(object())
a.append(object())

# x는 여전히 같은 Python object를 가리킨다.

a 내부 배열이 재할당되어도 x가 가리키는 Python object 자체가 이동하는 것은 아니다. list가 저장하는 것은 object pointer이고, element object는 별도로 존재하기 때문이다.

다만 C extension에서 ob_item 내부 pointer를 직접 들고 있다면 이야기가 달라진다. list resize 이후 내부 배열 주소가 바뀔 수 있으므로, CPython 내부 구조에 의존하는 코드는 매우 조심해야 한다.

메모리 배치 차이

Python list는 다양한 type을 담을 수 있다.

a = [1, "hello", 3.14]

이것이 가능한 이유는 list가 실제 값을 직접 저장하지 않고 PyObject* pointer를 저장하기 때문이다. 각 object는 heap에 따로 존재한다.

반면 C++ vector는 element type이 고정된다.

std::vector<int> values = {1, 2, 3};

std::vector<int>에는 std::string을 넣을 수 없다. 대신 int 값들이 연속된 메모리에 직접 저장되므로 cache locality가 좋다.

Python list[int]:
list array는 연속이지만 int object들은 별도 object

std::vector<int>:
int 값 자체가 연속

따라서 숫자 배열을 많이 다루는 계산에서는 Python list보다 C++ vector나 NumPy array가 훨씬 유리할 수 있다.

증가 전략 차이

둘 다 capacity를 여유 있게 늘리지만, 증가 비율은 구현에 따라 다르다.

CPython list는 list_resize()에서 대략 newsize + newsize / 8 + constant 형태로 over-allocation한다.

new_allocated = newsize + (newsize >> 3) + 6;

C++ 표준은 std::vector의 정확한 capacity 증가 비율을 지정하지 않는다. 구현체마다 1.5배, 2배 등 다른 전략을 사용할 수 있다.

따라서 다음처럼 이해하는 것이 안전하다.

Python list: CPython 구현에서는 비교적 완만하게 over-allocation
C++ vector: 표준은 증가 비율을 강제하지 않음

둘 다 중요한 목적은 같다.

매 push/append마다 재할당하지 않게 해서 평균 O(1) 추가를 달성한다.

비교 정리

Python list와 C++ vector를 비교하면 다음과 같다.

둘 다 동적 배열이라는 점에서는 비슷하다. 하지만 Python list는 범용 object container이고, C++ vector는 type이 고정된 연속 storage container이다.

이 차이가 성능과 메모리 모델의 핵심이다.

성능 관점 정리

list 재할당을 성능 관점에서 정리하면 다음과 같다.

중요한 기준은 길이가 변하는가이다.

길이가 변하지 않으면 보통 pointer 교체만 한다.
길이가 변하면 resize 가능성이 생긴다.
capacity가 충분하면 resize를 피할 수 있다.
capacity가 부족하거나 너무 많이 남으면 재할당될 수 있다.

주의할 점

CPython의 list over-allocation 정책은 구현 세부사항이다. Python 언어 명세가 모든 구현에 같은 capacity 증가 패턴을 강제하는 것은 아니다.

따라서 다음처럼 이해하는 것이 안전하다.

Python list는 append에 효율적이다.
CPython은 over-allocation으로 append를 amortized O(1)에 가깝게 만든다.
정확한 capacity 증가 수치는 CPython version에 따라 바뀔 수 있다.

PyPy, MicroPython 같은 다른 Python 구현에서는 내부 방식이 다를 수 있다. 이 글의 내부 구조 설명은 CPython 기준이다.

정리

Python list 재할당을 이해하려면 object와 내부 배열을 구분해야 한다.

1. a = [...]는 변수 a가 새 list object를 가리키게 한다.
2. append, extend, +=는 보통 같은 list object를 유지한다.
3. 같은 list object를 유지해도 내부 pointer 배열은 재할당될 수 있다.
4. CPython list는 size와 allocated를 구분한다.
5. allocated가 남아 있으면 append 시 실제 재할당을 피한다.
6. capacity가 부족하면 더 큰 배열을 확보한다.
7. CPython은 over-allocation으로 반복 append를 효율적으로 만든다.
8. 인덱스 재할당은 길이를 바꾸지 않으므로 resize와 다르다.
9. slice assignment는 길이가 바뀔 수 있으므로 resize가 발생할 수 있다.

결론적으로 Python list는 단순한 동적 배열처럼 생각하면 된다. 겉으로는 append() 한 줄이지만, CPython 내부에서는 size, allocated, pointer 배열, reference count가 함께 관리된다.