[set] set에서 삽입시에 벌어지는 key 테이블 리사이징

파이썬 set object의 C 구현 코드 : https://github.com/python/cpython/blob/main/Objects/setobject.c

일단.. cpython 의 set object의 c코드만해도 2500줄이 넘어간다는 사실에 경악했습니다.. 이렇게 복잡한 자료구조를 나는 여태 이렇게 편하게 쓰고 있었구나...ㄷㄷ

 

아무튼, set에 들어가는 아이템이 너무 많아지면 set_table_resize 를 통해서 key 리스트를 더 많이 할당한 메모리로 싹 옮긴다고 합니다. 이 임계점에서 순간적으로 연산량이 많아지겠네요.

언제 사이즈가 바뀌는지 출력해봤습니다. 또 pop으로 아이템을 제거하면 다시 줄어드는지도 확인해봤습니다.

A = set()
now_size = A.__sizeof__()
print(sys.getsizeof(1))
print((1).__sizeof__())

for i in range(1,10000) :
    A.add(i)
    if now_size < A.__sizeof__() :
        now_size = A.__sizeof__()
        print(f'{i} {now_size}')

for i in range(1,10000) :
    A.remove(i)
    if now_size > A.__sizeof__() :
        now_size = A.__sizeof__()
        print(f'{i} {now_size}')

print(len(A))

결과
5 712
19 2248
77 8392
307 32968
1229 131272
4915 524488 # {리사이징이 벌어진 item 개수} {리사이징된 후 메모리 사용량}
0 # pop 할때는 리사이징 없이 다 팝. 마지막에 남은 아이템 갯수가 0인걸로 다 팝된걸 확인.

 

일단 주석에 적혀있기로는..

/*
Restructure the table by allocating a new table and reinserting all
keys again.  When entries have been deleted, the new table may
actually be smaller than the old one.
*/

라고 되어있긴합니다. 요소가 삭제되고 리사이즈가 발생하면 기존것보다 새 테이블이 더 작아진다고 해요. 근데 일단 리사이징이 일어나는 트리거가 증가, 감소에 따라서 그 기준이 다른 것 같습니다.

리사이징이 일어나는 기준은... 잘 모르겠습니다.ㅠㅠ (알고 계시다면 알려주세용)

 

리스트로도 비슷한걸 해봤는데, 리스트도 append 할때마다 늘리는게 아니라 미리 넉넉하게 메모리를 잡아놓더라구요. 근데 list는 사이즈가 줄면 메모리도 주기적으로 같이 줄어듭니다! 이런 차이가 있네요.

 

2줄 요약

1. set 아이템 수가 늘어나면 어느 순간 key 테이블을 리사이징해서 key들을 싹 이사시키는 작업이 진행됨

2. 늘어나는건 금방 늘어나는데, 한번 늘어난게 잘 줄지는 않음.