python3.7에서 Dict가 정렬이 되는 이유

python3.7 부터 dict에 데이터를 입력한 뒤 출력 해보면 항상 정렬을 유지한다. (cpython의 경우에는 3.6에서도 지원이 되었지만, 3.7부터는 정식으로 모두 지원이 되기에 3.7이라고 지칭한다.) 다만 여기서 말하는 정렬은 입력 순 정렬을 말하는 것으로, 실제 데이터의 정렬과는 다르다. 데이터 값의 정확한 정렬을 원한다면, collection 모듈의 OrderDict 를 사용해야 한다. (여기에 대해서도 StackOverflow에 동일한 답변이 있다.[Link])

Python3.5와 Python3.7의 비교

3.6이 아닌 3.5와 비교하는 이유는 우리가 일반적으로 사용하는 python이 cpyton이다 보니 3.7과의 비교에서 차이가 없다.

# version 3.5
_dict = {}
_dict['b'] = None
_dict['c'] = None
_dict['f'] = None
_dict['a'] = None

print("Dict result >> {}".format(_dict))
# Dict result >> {'c': None, 'f': None, 'b': None, 'a': None} 
/* 해당 결과값은 정렬이 되어있지도 않지만, 호출시마다 달라질 수 있다.*/

# version 3.7
_dict = {}
_dict['b'] = None
_dict['c'] = None
_dict['f'] = None
_dict['a'] = None

print("Dict result >> {}".format(_dict))
# Dict result >> {'b': None, 'c': None, 'f': None, 'a': None} 
/* 결과를 보면 입력순으로 정렬이 되어서 나온다. */

Python 3.7에서 dict가 정렬이 되는 이유

그럼 갑자기 3.7 부터 왜 이러한 정렬을 지원하는지 찾아보니, python 웹페이지에 Compact and ordered dict(issue27350) [링크] 라는 제목으로 등록된 글을 확인할 수 있다. 해당 issue는 처음 2016.06.19에 처음 등록 되었고 현재는 종료된 issue다.

여기서 처음 issue를 등록한 사람의 글을 보면 pypy 블로그에 등록된 faster-more-memory-efficient-and-more[링크]라는 글을 언급하고 있는데 여기서 힌트를 얻어서 해당 아이디어를 낸 듯 하다. pypy에 언급된 내용에서는 pypy가 dict 정렬 등에 빠르고, 더 많은 메모리 효율의 성과를 낼 수 있었는지를 설명하는 내용이 있는데 이러한 작업이 시작하게 된 계기 또한 Raymond Hettinger가 제시한 아이디어[링크]에서 시작되었다.

Raymond Hettinger가 제시한 아이디어는 아래와 같이 기존에 배열 공간 하나로만 관리했던 dict 형태에 인덱스를 관리하는 공간을 하나 더 추가하는 형태로 제시한다.

/** Raymond Hettinger 가 제시한 생각 */

# 입력된 Dict 값 
d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

# 기존의 보관 방식 
entries = [['--', '--', '--'],
            [-8522787127447073495, 'barry', 'green'],
            ['--', '--', '--'],
            ['--', '--', '--'],
            ['--', '--', '--'],
            [-9092791511155847987, 'timmy', 'red'],
            ['--', '--', '--'],
            [-6480567542315338377, 'guido', 'blue']]

# 새로운 보관 방식
indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, 'timmy', 'red'],
            [-8522787127447073495, 'barry', 'green'],
            [-6480567542315338377, 'guido', 'blue']]

위와 같은 형태로 변경된 블로그에서 설명하는 이전 dict의 구조와 새로운 dict의 구조

# Original Dict struct
struct dict {
    long num_items;
    dict_entry* items;   /* pointer to array */
}

struct dict_entry {
    long hash;
    PyObject* key;
    PyObject* value;
}

# New Dict struct
struct dict {
    long num_items;
    # 기존에 하나로 존재하던것을 두개의 공간으로 나누었다.
    variable_int *sparse_array;
    dict_entry* compact_array;
}

struct dict_entry {
    long hash;
    PyObject *key;
    PyObject *value;
}

애초에 dict와 같은 Hash테이블은 속도 적인 부분에서 많은 장점이 있지만, 빠른 속도와 충돌을 방지하기 위해서 희소 배열 형태로 데이터를 보관하여야 했기에 많은 메모리 공간을 차지하고 있어야 했다.

기존 3.5이전에는 dict 정보가 보관되는 dictentry를 PyDictKeyEntry 형태(메모리 주소, 키, 값)의 희소 배열로 저장을 하면서 사용하지 않는 공간에 대해서도 PyDictKeyEntry 형태로 저장되어 불필요한 자원이 소모 되었다면, 3.7부터는 dictentry에는 순수한 dict 정보만 보관하고, variable_int에 희소 배열 형태로 dict의 index를 저장하도록 변경 되면서 불필요하게 사용되던 메모리 공간을 효율적으로 관리할 수 있도록 수정된 것이다. 그와 함께 dict가 입력 순 정렬로 출력되는데에는 dict의 저장 공간이 list 형태로 변경 되면서 부수적인 효과가 나오게 된 것이다.