요약
- array doubling은 동적 배열이 내부적으로 크기를 늘릴때 쓰는 전략을 말한다.
- 파이썬에서는 완만한 오버할당을 사용한다.
본문
- array doubling은 동적 배열이 내부적으로 크기를 늘릴때 쓰는 전략을 말한다.
- append/extend/insert등으로 길이가 현재 수용량을 초과하면 리사이즈가 트리거됨
- realloc 같은 방식으로 메모리 블록을 키우려고 하고 안되면 새 블록 할당 후 포인터 배열만 복사(값 복사는 아님)
- Cpython은 2배가 아닌 약 12.5%씩 더 크게 잡는 완만한 오버할당을 사용
- 고전 버전
- new_allocated = newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6)
- newsize >> 3 은 1/8로 나누는 거임
- (newsize < 9 ? 3 : 6) 추가 패딩으로, 리스트가 아주 작을 때 12.5%를 주면 절대적인 양으로 너무 적게 추가되서 +3을 붙여줌
- 최신 버전
- new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3
(size_t)newsize: newsize의 size, size_t는 크기를 표현하기 위한 타입-
- & ~(size_t)3 => 하위 2비트를 0으로 만듦
- 4의 배수로 만들어서 capacity를 항상 4의 배수로 유지
- 17이면 16으로 변환, 26이면 24로 변경
- 메모리 관리를 위함
- 확인 가능한 코드
import sys
arr = list()
prev_size = sys.getsizeof(arr)
for i in range(1, 10000):
arr.append(i)
if sys.getsizeof(arr) / prev_size != 1:
doubling_rate = round((sys.getsizeof(arr)- prev_size)/ prev_size * 100, 2)
print(len(arr), sys.getsizeof(arr), doubling_rate)
prev_size = sys.getsizeof(arr)
