#python dictionary insertion ordered

* 이 글은 스택 오버플로우에 올라온 질문을 재구성한 것 입니다. * 읽기 어려우신 문장은 원문을 확인해보시는 걸 권장해드립니다. * 이 글은 PC에서 보기 편합니다.

Python 3.6 이상에선 Dictionary가 순서 보장이 되나요?

네. CPython에선 삽입 순서가 유지됩니다. 하지만 CPython 외 다른 구현체에서는 보장되지 않습니다. 즉, 이 기능은 CPython 3.6의 Implementation detail 입니다. (Python 3.7부터, 위 내용이 Implementation detail이 아닌 언어 기본 feature가 되었습니다. Python 3.7부터는 구현체에 무관하게 삽입 순서가 보장됩니다.)

순서가 보장되는데 어떻게 메모리 사용을 줄였나요?

두 가지 배열을 사용합니다. PyDictKeyEntry 형식의 entry들을 담는 dk_entries 배열과 그 인덱스들을 담는 dk_indicies 배열을 씁니다.

첫번째 배열 dk_entries는 삽입 순서에 따라 entry(PyDictKeyEntry type)들을 저장합니다. 즉, 삽입 순서 보존이 이 배열에 의해 이뤄집니다.

두번째 배열 dk_indicies는 dk_entries의 각 요소에 대한 index들을 저장합니다. 즉, 각각의 index 값이 dk_entries의 요소를 가리킵니다. 이 배열은 해시 테이블 역할을 합니다. 키가 해시되면 그 키가 dk_indices 안에 저장된 index를 가리키고, 그 index는 그에 맞는 entry를 dk_entries에서 가져옵니다. 인덱스들만 저장되기 때문에, dk_indices의 형식은 Dictionary의 크기에 따라 결정됩니다.(int8_t부터 int32_6, int64_t까지)

이전 구현체에선, PyDictKeyEntry 형식의 희소 배열을 사용하고 dk_size에 크기를 저장했습니다. 하지만 성능을 이유로 배열이 dk_size의 2/3 이상을 사용할 수 없었고, 이에 따라 빈공간이 많이 생겼습니다. 게다가 빈공간이어도 PyDictKeyEntry 크기만큼 차지하고 있었기 때문에 문제가 더 컸습니다.

이젠 괜찮습니다. entry 배열에는 필수 entry들만 저장하고 dk_size의 2/3을 채우는 intX_t(X는 Dict에 따라 결정) 형식의 희소 배열이 유지됩니다. 빈공간 형식이 PyDictKeyEntry에서 intX_t로 바뀌었기 때문에 훨씬 메모리를 아낄 수 있습니다.

이 아이디어를 제안한 Raymond Hettinger씨의 원본 문서를 보면, 내용을 시각화 한 자료가 있습니다.

For example, the dictionary:

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

is currently stored as:

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

Instead, the data should be organized as follows:

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

위 자료에서 보듯, 이전에는 빠른 검색과 충돌 방지를 위해 많은 공간이 필수였습니다. 새로운 접근 방식에선, entry들이 아닌 index에 희소 배열을 사용함으로써 메모리를 많이 아낄 수 있습니다.

Python-Dev에서 이 feature를 다룬 대화를 확인할 수 있습니다. 관심 있으시면 읽어보셔도 즣을 것 같습니다.

--