paca94

고민이 생기고 해당 고민에 대해 어떤 결과를 도출해내는지 써내려가는 블로그입니다.
여러가지 의견은 언제나 환영입니다!

dict는 언제 리사이즈될까

3 분 소요 

Python 잘써보기 위해 dict를 분석해봤다.

찾아보거나 알게된 배경

  • 잘 써보기 위한 노력
  • 예전에 팀원분이 블로그에 쓴 dict가 순서를 기억한다는 글이 떠올라서 다시 읽어보고 좀 더 디테일하게 관련 정보를 찾아보게 되었다.

요약

  • 읽기 전에
    • 파이썬의 해시테이블 위한 공간은 2의 지수배로 늘어난다
    • 최소 크기는 2^3 이다.
    • 파이썬 해시테이블에서 데이터가 실제로 저장되는 공간의 최소 크기는 일반적으로 테이블 크기 * 2 / 3 의 크기를 가진다.
    • 리사이징 할 때, 현재 사용하고 있는 아이템 개수 * 3 보다 큰 가장 가까운 지수배수로 늘어난다.
  1. 새로운 dict 생성(PyDict_New ) 후, 데이터 추가
    1. 최초로 아무 key나 value가 없는 dict를 만들면, 해당 dict는 파이썬 내부에서 미리 만들어놓은 Py_EMPTY_KEYS 를 가져다가 PyDictObject의 ma_keys(자료형 : PyDictKeysObject)에 할당해놓는다.
    2. 이후, 데이터를 설정해주기 위해, SetItem을 호출한다면, Py_EMPTY_KEYS 를 사용하고 있기 때문에 그때서야 새로운 공간을 할당해준다.
      1. 해시테이블을 위해 할당된 공간(dk_indices)의 크기는 8이다
      2. 실제 데이터가 저장될 수 있는 공간(entires)의 크기는 5이다 ( 2 ^ 3 * 2 / 3 )
  2. 해당 dict에 더이상 쓸 수 있는 횟수가 남아있지 않음
    1. 이미 데이터가 추가가 되어있을 때, PyDictObject→ma_keys→dk_usable 값이 0 이하라면, 리사이징 한다.
      1. Dict에서 실제 데이터가 저장되는 공간인 entires에 데이터는 현재 dk_usable의 값에 해당되는 위치에 저장된다. ( 값을 넣을 때마다 1씩 추가 )
  3. 해당 dict의 타입이 유니코드고, 이번에 들어온 키값이 유니코드가 아니라면, 리사이징한다 ( 이부분은 테스트 못해봤음 + 3.11 알파버전 기준으로 해당방식으로 구현되어있고 3.10 이전은 다를 수 있음! )
    1. 유니코드만 있을때랑, 아닐때 entries에 저장시 사용하는 데이터의 형태가 다름.

내용

# 최초로 만들어졌을때. 실제 해당 dict만을 위한 테이블 공간은 없음
>>> t3 = {}
>>> sys.getsizeof(t3)
64

# 처음으로 데이터를 넣자, 리사이즈 되어 공간이 커졌음
>>> t3[1] = 'a'
>>> sys.getsizeof(t3)
232

# 하나 더 넣어도 사이즈가 늘어나지 않음
>>> t3[2] = 'b'
>>> sys.getsizeof(t3)
232

# 아이템을 5개까지 넣음
>>> t3
{1: 'a', 2: 'b', 0: 'c', 3: 'd', 4: 'f'}
>>> sys.getsizeof(t3)
232

# 코드상으로 usable값이 5개를 넘어가면 리사이즈가 일어나고,
# 아이템을 삭제한 뒤에 추가해도 해당값이 줄어들지 않아 리사이즈가 일어날 것임.
>>> del t3[4]
>>> t3
{1: 'a', 2: 'b', 0: 'c', 3: 'd'}
>>> sys.getsizeof(t3)
232
>>> t3
{1: 'a', 2: 'b', 0: 'c', 3: 'd', 4: 'g'}
>>> t3[4] = 'g'
>>> sys.getsizeof(t3)
360

>>> t3.clear()
>>> sys.getsizeof(t3)
64

# dict 자료형 생성
>>> t = {}
# 데이터를 모두 채워줌. ma_used=> 5, dk_usable=> 0, dk_nentries=> 5임
>>> for n in range(5):
...     t[n] = n
...
>>> t
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4}
>>> sys.getsizeof(t)
232
# 아이템 3개 삭제. ma_used=> 2, dk_usable=> 0, dk_nentries=> 5임
>>> del t[2]
>>> del t[3]
>>> del t[4]
>>> t
{0: 0, 1: 1}
>>> sys.getsizeof(t)
232
# 데이터를 추가했고, 추가하고있는 당시에는 위와 상황이 동일하며, dk_usable값이 0이므로 리사이징을 시작
# dict는 리사이징시 ma_used*3보다 큰 가장 가까운 2의 거듭제곱에 대해 테이블 크기를 증가시킴
# 따라서, 2 * 3 의 가장 가까운 거듭제곱 값은 2^3 이므로 테이블 크기가 다시 8로 리사이징됨.
# 리사이징 이후, 데이터를 넣음. ma_used=> 3, dk_usable=> 2, dk_nentries=> 3임
>>> t[5] = 5
>>> sys.getsizeof(t)
232
>>> t
{0: 0, 1: 1, 5: 5}
# ma_used=> 4, dk_usable=> 1, dk_nentries=> 4임
>>> t[6] = 1
>>> sys.getsizeof(t)
232
# ma_used=> 5, dk_usable=> 0, dk_nentries=> 5임
>>> t[7] = 1
>>> sys.getsizeof(t)
232
# 여기서 dk_usable값이 0이므로 리사이징 시작
# 이번에는 used 값이 5이므로, 5*3의 가장 가까운 2의 거듭제곱은 4임
# 따라서, 다음 테이블 크기는 2^4 임. ( 실제 값이 저장될 수 있는 entires는 10(2^4*2/3) 임)
# ma_used=> 6, dk_usable=> 4, dk_nentries=> 6임
>>> t[8] = 1
>>> sys.getsizeof(t)
360

>>> t = {}
>>> for n in range(5):
...     t[n] = n
...
>>> sys.getsizeof(t)
232
>>> t
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4}
# 동일한 키값에 데이터를 넣을 경우, ma_used, dk_usable, dk_nentries 값이 변하지 않음.
# 그리고 코드 구현상, 대상 키값에 저장되어있는 데이터가 동일하다면, 아무것도 안함.
>>> t[4] = 10
>>> t
{0: 0, 1: 1, 2: 2, 3: 3, 4: 10}
>>> sys.getsizeof(t)
232
  • del로 해당 키값에 데이터를 지워도 dk_usable값이 늘어나지 않음
  • popitem으로 데이터를 꺼내도 entires의 위치만 변할 뿐, dk_usable은 변하지 않음
    • 즉, 현재 entires가 인덱스 4까지 차 있을 때, popitem을 호출할 경우, 인덱스 4에 해당하는 위치가 비게 되고, 새로 아이템을 추가한다면, 인덱스 4의 위치에 데이터를 쓴다.

  • 기존에 존재하는 키값에 데이터를 다시 셋하는경우, 데이터만 교체한다.

  • python new dict시 할당되는 기본 형태 
    static PyDictKeysObject empty_keys_struct = {
      1, /* dk_refcnt */
      0, /* dk_log2_size */
      DICT_KEYS_SPLIT, /* dk_kind */
      1, /* dk_version */
      0, /* dk_usable (immutable) */
      0, /* dk_nentries */
      {DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY,
       DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY}, /* dk_indices */
};
  • 추가정보
    • 우리가 흔히 {} 이렇게 만들어 쓰는데, 이렇게 사용하면, combined테이블이라고 해서, PyDictObject에서 ma_values를 사용하지 않는다. ( 처음에 이거때문에 엄청 헤맴 )
    • 파이썬 Dict의 기본 종류는 유니코드(DICT_KEYS_UNICODE) 타입이다.
      • 데이터 저장시, 유니코드 테이블은 hash를 미리 계산해놓지 않는다. resize-01
    • 데이터를 넣을 때, 유니코드가 아닌 키값을 사용하면, 제너럴로 리사이즈된다. ( DICT_KEYS_GENERAL )
      • 데이터 저장시, 제너럴 테이블은 hash값을 미리 계산해서 들고있는다.놓지 않는다. resize-02

참고자료

CPython 코드 직접 읽어가며 확인함

참고