Python3.6에서는 dict가 입력순으로 정렬된다.

(스택오버플로 질문 Are dictionaries ordered in Python 3.6+?의 답변을 참고했다.)

'''

# 읽지 않아도 되는 서론

회사에서 random 함수가 사용된 함수를 테스트하다가 신기한 점을 발견했다. 내 컴퓨터(Python3.6)에서는 마냥 잘 되던 테스트가 다른 컴퓨터(Python3.5)에서는 계속 실패했던 것이다. 하지만 가끔 통과되는 경우도 있어서 영문을 몰랐는데 알고보니 딕셔너리의 정렬 여부 때문이었다.

import random
random.seed(1)

dict_a = {'a': 1, 'b': 2, 'c':3, 'd':4, 'e':5}
key = random.choice(list(dict_a.keys())) # 딕셔너리 키 값중 하나를 랜덤으로 선택 할당
assert key == 'b'

Python3.5에서는 random.seed(1)로 시드를 고정시켜줬음에도, dict_a.keys()의 값이 계속 바뀌어 변수 key의 값이 계속 달라졌다. 하지만 Python3.6에서는 딕셔너리가 입력순대로 정렬되어 항상 같은 key 값을 보여주었다.

이걸 발견했을 때 정말 신기했는데 알고보니 이러한 업데이트가 단순히 정렬을 위한 게 아니라 성능때문이라 하여 궁금해서 찾아보았다.

'''

# 본론; Python 3.6부터 딕셔너리가 정렬되는 이유

Python 3.5 이하 버전에서는 딕셔너리에 순서란 게 없었다. 딕셔너리는 애초에 정렬된 콜렉션으로서 만들어진 타입이 아니었고, 값을 키로 찾기 때문에 순서를 신경쓸 필요가 없었다. 한편 Python 3.6 버전부터는 딕셔너리에도 순서가 생겨 다음과 같이 모든 키값이 '입력순으로' 저장된다.(그냥 '정렬'이 아니고 '입력순 정렬'이다.)

>>> dict_a = {'b': 1, 'a': 2, 'c': 3, 'd': 4, 'e': 5}
>>> dict_a
{'b': 1, 'a': 2, 'c': 3, 'd': 4, 'e': 5}
>>> dict_a
{'b': 1, 'a': 2, 'c': 3, 'd': 4, 'e': 5}

이러한 업데이트는 성능 때문이라 한다.

3.6 버전의 Python에서는 딕셔너리를 위해 두 개의 배열을 사용한다.

첫 번째는 dk_entries로, 삽입된 딕셔너리에 대한 엔트리(PyDictKeyEntry 타입)를 지니고 있다. 여기서 입력되는 딕셔너리 아이템 순으로 배열을 추가함으로써 정렬이 이루어진다. (이 때문에 '입력순' 정렬이 된다.)

두 번째는 dk_indices로, 이는 dk_entries 배열의 색인을 지닌다(dk_entries의 엔트리에 해당하는 위치 정보를 담음). 이는 해쉬 테이블처럼 작동한다. 키가 해쉬되면 이는 dk_indices에 저장된 색인 중 하나를 가리키고 dk_entries로부터 그에 상응하는 엔트리를 불러온다. 색인만이 저장되어 있기 때문에 dk_indices의 크기은 딕셔너리 전체 사이즈를 따른다.(1byte부터 4/8byte까지)

좀 어렵지만 예시를 보면 이해하기가 수월할 것이다. 기존 Python 3.5 이하 버전이 다음과 같았다면,

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}
entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]

Python 3.6 버전은 이러하다.

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}
indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, 'timmy', 'red'],
            [-8522787127447073495, 'barry', 'green'],
            [-6480567542315338377, 'guido', 'blue']]

Python 3.5 이하 버전에서는 PyDictKeyEntry 타입의 희소배열을 사용하고 dk_size에 배열 크기를 저장하여 빈 공간을 많이 차지했었다. 성능 문제로 배열의 크기가 2/3 * dk_size를 넘지 못했기 때문이다.(그리고 그 빈 공간은 여전히 PyDictKeyEntry의 크기를 지니고 있는 채였다.)

(* 희소배열은 배열의 값이 대부분 0인 경우를 말한다.)

하지만 이제는 필요한 엔트리(딕셔너리 아이템)만 저장하고, 2/3 * dk_size는 intX_t(X는 딕셔너리의 사이즈에 따라 다름) 타입의 희소배열로 채워진다. 배열의 빈 공간을 PyDictKeyEntry 대신 intX_t로 바꾼 것이다.

결론적으로, PyDictKeyEntry 타입의 희소배열 대신 int로 채워진 희소배열을 사용함으로써 메모리 사용을 줄일 수 있게 되었다.