Following system colour scheme Selected dark colour scheme Selected light colour scheme

Python 개선 제안 한국어 번역

PEP 412 – 키 공유 딕셔너리

Author:
Mark Shannon <mark at hotpy.org>
Status:
Final
Type:
Standards Track
Created:
08-Feb-2012
Python-Version:
3.3
Post-History:
08-Feb-2012
Table of Contents

번역·라이선스 안내

이 비공식 한국어 번역은 원문 Copyright 절의 Public Domain 조건에 따라 제공합니다. 원저자와 공식 원문은 그대로 표시합니다. 수정되지 않은 기준 원문 · 공식 최신판

초록

이 PEP는 내장 딕셔너리 타입 dict의 구현 변경을 제안합니다. 새 구현에서는 속성 딕셔너리(객체의 __dict__ 속성)로 사용되는 딕셔너리가 같은 클래스 인스턴스의 다른 속성 딕셔너리와 키를 공유할 수 있습니다.

동기

현재 딕셔너리 구현을 객체 속성의 컨테이너로 사용하면 필요 이상으로 많은 메모리를 사용합니다. 같은 클래스의 여러 인스턴스가 키를 공유하지 않고 인스턴스마다 키를 복제하기 때문입니다. 그럼에도 현재 딕셔너리 구현은 세밀하게 조정되어 있으며, 범용 매핑 객체로서 매우 뛰어난 성능을 보입니다.

키(와 해시)를 값에서 분리하면 여러 딕셔너리가 키를 공유할 수 있으므로 메모리 사용을 개선할 수 있습니다. 이득이 있을 때에만 키를 값에서 분리하도록 하면, 범용 매핑 객체로 사용할 때 현재 딕셔너리 구현의 높은 성능을 유지할 수 있습니다.

동작

새 딕셔너리는 이전 구현과 똑같이 동작합니다. Python API, C API, ABI를 모두 완전히 준수합니다.

성능

메모리 사용량

메모리 사용량 감소는 특정 시점에 존재하는 키 공유 딕셔너리의 수와 직접적인 관련이 있습니다. 이러한 딕셔너리의 크기는 일반적으로 현재 딕셔너리 구현의 절반입니다.

벤치마크 결과, 객체 지향 프로그램에서는 메모리 사용량이 10%에서 20%까지 줄었으며, 그 밖의 프로그램에서는 메모리 사용량에 유의미한 변화가 없었습니다.

속도

새 구현의 성능은 주로 메모리 지역성 효과에 따라 좌우됩니다. 키를 공유하지 않는 경우(예를 들어 모듈 딕셔너리나 dict() 또는 {}로 명시적으로 생성한 딕셔너리)에는 현재 구현과 비교해 성능에 변화가 없습니다(차이는 1~2퍼센트 이내입니다).

키를 공유하는 경우 새 구현에서는 키와 값이 떨어져 저장되는 경향이 있지만, 전체 메모리 사용량은 줄어듭니다. 많은 경우 메모리 사용량 감소 효과가 지역성 손실보다 크므로 성능이 향상되지만, 일부 프로그램은 약간 느려질 수 있습니다.

벤치마크 결과, 대부분의 벤치마크에서 속도에 유의미한 변화가 없었습니다. 객체 지향 벤치마크에서는 같은 클래스의 객체를 대량으로 생성할 때 속도가 약간 향상되었습니다(gcbench 벤치마크에서는 10% 향상되었으며, 이는 상한에 가까운 수치일 것입니다).

구현

이전 딕셔너리와 새 딕셔너리는 모두 고정 크기의 dict 구조체와 크기를 조정할 수 있는 테이블로 구성됩니다. 새 딕셔너리에서는 이 테이블을 다시 키 테이블과 값 배열로 분할할 수 있습니다. 키 테이블은 키와 해시를 저장하며, (분할되지 않은 테이블의 경우) 값도 함께 저장합니다. 원래 구현과 다른 점은 이전에 dict 구조체에 있던 여러 필드를 키 테이블이 포함한다는 것뿐입니다. 테이블이 분할되면 키 테이블의 값은 무시되며, 대신 값은 별도의 배열에 저장됩니다.

분할 테이블 딕셔너리

객체의 __dict__ 슬롯을 채우기 위해 딕셔너리를 생성할 때는 분할 형태로 생성합니다. 키 테이블은 타입에 캐시됩니다. 따라서 한 클래스의 모든 인스턴스가 가진 속성 딕셔너리가 키를 공유할 수 있습니다. 이러한 딕셔너리들의 키가 서로 달라지기 시작하면 개별 딕셔너리는 지연 방식으로 결합 테이블 형태로 변환됩니다. 이를 통해 일반적인 경우에는 메모리를 효율적으로 사용하고, 모든 경우에 정확성을 보장합니다.

분할 딕셔너리의 크기를 조정할 때는 결합 테이블로 변환합니다. 인스턴스 속성을 저장한 결과로 크기 조정이 일어났고 클래스의 인스턴스가 하나뿐이라면 딕셔너리를 즉시 다시 분할합니다. 대부분의 객체 지향 코드는 __init__ 메서드에서 속성을 설정합니다. 따라서 두 번째 인스턴스가 생성되기 전에 모든 속성이 설정됩니다. 이후의 인스턴스 딕셔너리는 모두 올바른 크기를 가지므로 더 이상 크기 조정이 필요하지 않습니다. 더 복잡한 사용 패턴에서는 어떤 방식이 최선인지 알 수 없습니다. 그래서 구현은 크기 조정으로 결합 테이블(공유되지 않는 키)로 되돌아가는 시점까지 추가 삽입을 허용합니다.

분할 딕셔너리에서 항목을 삭제해도 키 테이블은 바뀌지 않으며, 값 배열에서 값만 제거됩니다.

결합 테이블 딕셔너리

명시적 딕셔너리(dict() 또는 {}), 모듈 딕셔너리 및 그 밖의 대부분의 딕셔너리는 결합 테이블 딕셔너리로 생성됩니다. 결합 테이블 딕셔너리는 절대 분할 테이블 딕셔너리가 되지 않습니다. 결합 테이블은 기존 딕셔너리의 테이블과 거의 같은 방식으로 배치되므로 성능도 매우 비슷합니다.

구현

새 딕셔너리 구현은 [1]에서 볼 수 있습니다.

장단점

장점

객체 지향 애플리케이션에서 메모리를 크게 절약합니다. 비슷한 객체를 많이 생성하는 프로그램의 속도가 약간 향상됩니다.

단점

자료 구조 변경: 딕셔너리 구현의 내부를 건드리는 서드파티 모듈은 동작하지 않게 됩니다.

repr() 출력과 순회 순서 변경: 대부분의 경우에는 달라지지 않습니다. 하지만 일부 분할 테이블 딕셔너리에서는 순회 순서가 달라집니다.

두 단점 모두 문제가 되지 않을 것입니다. 딕셔너리 구현의 내부를 건드리는 모듈은 이미 잘못된 것이므로 API를 사용하도록 고쳐야 합니다. 딕셔너리의 순회 순서는 한 번도 정의된 적이 없고 언제나 임의적이었습니다. Jython과 PyPy에서도 순서가 다릅니다.

대안 구현

분할 테이블에는 메모리를 더욱 절약할 수 있는 대안 구현도 있습니다. 키 테이블의 값 필드를 무시하는 대신 그 필드에 인덱스를 저장하는 방식입니다. 이 인덱스는 값 배열의 어느 위치를 찾아봐야 하는지 명시적으로 나타냅니다. 그러면 값 배열에는 키 테이블의 모든 슬롯이 아니라 사용 가능한 슬롯마다 필드 1개만 있으면 됩니다.

이 “인덱스” 방식을 사용하면 값 배열의 크기가 약 3분의 1 줄어듭니다. 키 테이블에 “values_size” 필드를 하나 더 두어야 하므로, 결합 딕셔너리의 크기가 한 워드만큼 커집니다. 간접 참조가 한 단계 늘어나 코드가 더 복잡해지고, 성능이 약간 떨어질 수도 있습니다.

“인덱스” 방식은 이번 구현에 포함하지 않지만, 기각된 것이 아니라 추가 실험 결과가 나올 때까지 보류된 것으로 보아야 합니다.

참고 문헌