파이썬 리스트 내부 구조
C언어의 배열과 파이썬의 리스트는 같은 자료형이지만 파이썬의 리스트가 훨씬 사용하기 편리하다. 그 이유는 아래와 같다.
- 리스트는 초기 선언시 크기를 지정하지 않아도 된다.
- 리스트는 초기 선언시 저장할 변수의 자료형을 지정하지 않아도 된다.
- 하나의 리스트 안에 서로 다른 자료형 데이터를 저장할 수 있다.
파이썬 리스트는 어떻게 구현되어 있길래 이렇게 편리할까? 궁금한 마음에 cpython 코드 상에서 리스트가 어떻게 구현되어있는지 살펴보았다 :)
리스트 내부 구조
cpython 코드 상에서 파이썬 리스트는 PyListObject라는 객체로 구현되어있고, 아래와 같은 구조를 가진다. PyListObject를 이루고 있는 각각의 객체에 대해서 하나씩 살펴보자.
PyObject
모든 파이썬 객체들은 PyObject라는 구조체의 확장판이다. 즉, 모든 객체는 PyObject를 가지고 있다. PyObject 구조체에는 객체의 reference count값과 대응되는 타입의 객체를 가리키는 포인터가 있다.
PyVarObject
PyVarObject는 PyObject의 확장판으로, 길이를 가진 객체에서 사용된다. 그렇기 때문에 길이를 나타내는 ob_size 필드가 추가되었다.
PyObject_VAR_HEAD
PyObject_VAR_HEAD는 인스턴스마다 길이가 변하는 객체를 선언할때 사용되며 PyVarObject ob_base으로 확장된다.
PyListObject
파이썬의 리스트는 아래와 같이 PyListObject라는 구조체로 구현되어있다.
- PyObject_VAR_HEAD
- **ob_item : 이중 포인터 (리스트 원소들의 포인터 배열에 대한 포인터)
- allocated : 리스트의 할당된 크기를 저장한다. 리스트에 담긴 원소의 수, 즉 리스트의 길이는 ob_size에 저장되므로 ob_size는 allocated보다 항상 작거나 같다.
PyListObject 코드를 통해 파이썬 리스트는 리스트 원소들의 포인터를 저장하고, ob_item이라는 이중 포인터를 사용해서 해당 배열의 주소값을 저장하고있다는 것을 알 수 있다. 바로 이 구조때문에 C언어의 배열보다 파이썬 리스트를 더욱 편리하게 사용할 수 있다.
쉽고 빠른 이해를 위해 예시를 살펴보자.
C언어의 배열
int arr[4] = {1, 2, 3, 4} 와 같은 배열이 있을때, 해당 배열은 4바이트 * 4만큼 메인 메모리를 할당받아 연속적으로 저장된다. 변수 arr은 배열의 시작 주소를 가지고 있기 때문에 index를 통해 배열의 원소에 접근할 수 있다.
파이썬의 리스트
동일한 배열에 대해 파이썬 리스트의 저장 구조는 위와 다르다. ob_item 라는 이중 포인터가 있고, ob_item은 리스트 원소들의 주소 값을 저장한 C언어의 배열을 가리킨다. 그리고 이 배열에 저장된 주소값을 통해 실제 원소 값에 접근할 수 있다.
이와 같이 파이썬의 리스트는 원소의 주소값을 저장하기 때문에 각 원소의 자료형이 무엇이든 상관없다. 따라서 초기 선언시 자료형을 지정하지 않아도 되고, 하나의 리스트 안에 서로 다른 자료형을 저장할 수 있는 것이다.
하지만 이중 포인터를 사용하기 때문에 특정 값을 찾기 위해 두 번의 탐색 과정을 거치게 되므로 C언어의 배열보다 속도가 느리다.
메모리 할당
C언어의 배열과 달리 파이썬의 리스트는 동적 배열이기 때문에 초기 선언시 리스트의 크기를 지정하지 않아도 된다. 동적 배열은 초깃값을 작게 잡아 배열을 생성하고, 리스트가 꽉 채워지면 크기를 늘려주는 방식(더블링) 으로 동작한다. 파이썬 리스트의 메모리 할당은 list_resize 메소드를 통해 이뤄진다.
allocated는 리스트의 현재 할당된 크기를, newsize는 리스트의 길이를 나타낸다. 만약 리스트의 길이가 할당된 크기보다 충분히 크다면 메모리 할당을 하지 않는다. 리스트의 할당된 크기를 늘려주는 경우에는 현재 리스트의 길이에 비례하여 0, 4, 8, 16, … 순으로 메모리를 추가적으로 할당한다.
append
파이썬 리스트는 동적 배열 자료형이므로, 아이템을 삽입할때 사용하는 append 메소드에서 배열의 용량이 꽉 차면 알아서 리스트의 크기를 증가시킨다. 더 자세하게 말하면 append는 cpython에서 PyList_Append 함수를 통해 구현되어있고, PyList_Append 함수는 내부에서 app1 함수를 통해 list_resize를 호출하여 리스트의 크기를 증가시키는 방식으로 동작된다.
파이썬 내부가 어떻게 C언어로 짜여졌는지 늘 궁금했는데 이번 기회에 많은 공부를 할 수 있었다. 그리고 cpython을 처음 봤을때는 외계어 같았는데 지금은 리스트 말고 다른 객체의 내부 구조도 뜯어볼 수 있을 것 같은 자신감이 생겼다. 뿌듯하다!
참고 자료 : https://github.com/zpoint/CPython-Internals/blob/master/BasicObject/list/list.md
