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” 필드가 필요하며, 이는 결합된 딕셔너리의 크기를 한 워드만큼 증가시킵니다. 추가된 간접 참조는 코드에 더 많은 복잡성을 더하며, 잠재적으로 성능을 약간 저하시킬 수 있습니다.

“인덱싱된” 버전은 이번 구현에는 포함되지 않겠지만, 추가 실험을 거친 후 거부되기보다는 보류된 것으로 간주해야 합니다.

참고 자료