python 배열 slicing(item[2:])의 성능은 왜 O(n)일까

파이썬을 쓰신다면 items[2:] 같은 slicing 문법을 보셨을텐데요. 이 기능이 매번 메모리 할당을 한다는 것을 알고 계신가요? 실제로 실행해보는 것만큼 정확한 건 없으니 디버깅을 해보겠습니다.

이런 파이썬 코드를 가지고 확인해보겠습니다.

items[2:] 는 어떻게 동작하는 걸까요? 결론부터 말씀드리면 필요한 length만큼 메모리를 확보하고 for 문을 통해 items 값의 복사가 이루어집니다. 즉, 시간/공간 복잡도가 O(n)이 됩니다.

디버깅을 통해 실제 동작을 확인해보겠습니다. cpython 의 구현체를 기준으로 진행하고 c 언어이기 때문에 vscode와 c/c++ extenstion을 사용하여 디버깅을 진행합니다. 3.14 버전를 기준으로 설명합니다.

slicing에 대한 주요한 로직은 list_slice_lock_held 함수에 있습니다. 다음은 list_slice_lock_held 함수 구현입니다.

list_slice_lock_held 함수에 브레이크 포인트를 걸고 실행하면 다음 사진처럼 ilow = 2, len = 8 로 items의 슬라이싱 정보들이 넘어간 것을 확인할 수 있습니다. items 길이가 10이고 items[2:] 이니 인덱스 2부터 9까지 사용되어 시작 인덱스(ilow)는 2, 길이(len)는 8인 것으로 이해할 수 있겠습니다.

 

그럼 list_new_prealloc 내부로 들어가봅니다. 넘어온 size = 8 에 대한 memory allocation이 될 것을 예상할 수 있습니다. 진입하면 op 가 할당되지 않은 상태로 시작합니다. 리턴이 되는 op에 메모리 할당이 이루어질 것을 예상해볼 수 있습니다.

 

list_new_prealloc 함수 코드에서 step over를 눌러 리턴 문까지 실행해보면 op에 size 8이 할당된 것을 볼 수 있습니다. 그럼 step over를 눌러 list_slice_lock_held로 돌아갑니다.

 

메모리 할당이 정상적으로 되었으니 이 공간에 items의 값을 할당해줍니다. for loop를 이용하여 하나씩 값을 할당하는 방식을 사용하네요.

 

정리)
실제로 파이썬을 디버깅해보면서 어떻게 동작하는지 확인해보았습니다. 메모리를 길이만큼 할당하고 배열의 값을 복사하는 생각보다 무거운 작업임을 알 수 있습니다. slicing의 step이 1인 경우에 대해서 살펴본 것이니 관심 있으신 분은 살펴보시면 좋을 거 같습니다. cpython 3.14 버전 기준으로 작성된 글이니 다른 파이썬 구현체나 버전에서는 동작이 다르니 참고해주세요.

참고)
cpython: https://github.com/python/cpython
c/c++ extenstion: https://marketplace.visualstudio.com/items?itemName=ms-vscode.cpptools