PEP 509 – dict에 비공개 버전 추가

Author:

Victor Stinner <vstinner at python.org>

Status:

Superseded

Type:

Standards Track

Created:

04-Jan-2016

Python-Version:

3.6

Post-History:

08-Jan-2016, 11-Jan-2016, 14-Apr-2016, 19-Apr-2016

Superseded-By:

699

Resolution:

Python-Dev message

---

Table of Contents

• 초록
• 근거
• 가드 예
• dict 버전 사용
  • 메서드 호출 속도 향상
  • 가드를 사용하는 특수화된 함수
  • Pyjion
  • Cython
  • Unladen Swallow
• 변경 사항
• 하위 호환성
• 구현 및 성능
• 정수 오버플로
• 대안
  • Python 수준에서 버전을 읽기 전용 __version__ 속성으로 노출합니다.
  • 각 딕셔너리 항목에 버전 추가
  • 새로운 dict 서브타입 추가
• 기존 사례
  • 메서드 캐시 및 타입 버전 태그
  • 전역 변수 / 내장 함수 캐시
  • 캐시된 전역 변수+내장 함수 조회
  • 반복 중 딕셔너리 변경 방지
  • PySizer
• 토론
• 승인
• Copyright

번역·라이선스 안내

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

초록

네임스페이스에 대한 빠른 가드를 구현하기 위해 각 딕셔너리 생성 시와 각 딕셔너리 변경 시마다 증가하는 새로운 비공개 버전을 내장 dict 타입에 추가합니다.

근거

Python에서는 많은 명령어가 내장 dict 타입을 사용합니다. 예를 들어 LOAD_GLOBAL 명령어는 전역 네임스페이스 또는 내장 네임스페이스에서 변수를 조회합니다(딕셔너리 조회 2회). Python은 내장 네임스페이스, 전역 네임스페이스, 타입 네임스페이스, 인스턴스 네임스페이스 등에 dict를 사용합니다. 로컬 네임스페이스(함수 네임스페이스)는 일반적으로 배열로 최적화되지만, 딕셔너리일 수도 있습니다.

Python은 거의 모든 것이 변경 가능하기 때문에 최적화하기 어렵습니다. 내장 함수, 함수 코드, 전역 변수, 로컬 변수 …를 런타임에 수정할 수 있습니다. Python 의미론을 준수하는 최적화를 구현하려면 “무언가 변경될 때”를 감지해야 합니다. 이러한 검사를 “가드”라고 부르겠습니다.

최적화의 속도 향상은 가드 검사의 속도에 따라 달라집니다. 이 PEP에서는 네임스페이스에 대한 빠른 가드를 구현하기 위해 딕셔너리에 비공개 버전을 추가할 것을 제안합니다.

대부분의 네임스페이스에서 일반적인 경우인 버전이 변경되지 않는 경우에는 딕셔너리 조회를 건너뛸 수 있습니다. 버전은 전역적으로 고유하므로, 버전을 확인하는 것만으로도 네임스페이스 딕셔너리가 새 딕셔너리로 교체되지 않았음을 검증하기에 충분합니다.

딕셔너리 버전이 변경되지 않는 경우 가드의 성능은 감시하는 딕셔너리 항목 수에 영향을 받지 않습니다. 복잡도는 O(1)입니다.

최적화 예: 전역 변수의 값을 함수 상수로 복사합니다. 이 최적화에는 전역 변수가 복사된 후 수정되었는지 확인하기 위한 전역 변수 가드가 필요합니다. 전역 변수가 수정되지 않으면 함수는 캐시된 복사본을 사용합니다. 전역 변수가 수정되면 함수는 일반 조회를 사용하며, 다음 함수 호출에서 가드 검사에 따른 오버헤드를 제거하기 위해 함수를 역최적화할 수도 있습니다.

가드를 사용하여 함수를 특수화하는 구체적인 방법과 Python 정적 최적화 도구에 대한 보다 일반적인 근거는 510 – Specialized functions with guards을 참조하십시오.

가드 예

가상의 dict_get_version(dict) 함수를 사용하여 딕셔너리 항목이 수정되었는지(생성, 갱신 또는 삭제되었는지) 확인하는 빠른 가드의 의사 코드입니다.:

UNSET = object()

class GuardDictKey:
    def __init__(self, dict, key):
        self.dict = dict
        self.key = key
        self.value = dict.get(key, UNSET)
        self.version = dict_get_version(dict)

    def check(self):
        """Return True if the dictionary entry did not change
        and the dictionary was not replaced."""

        # read the version of the dictionary
        version = dict_get_version(self.dict)
        if version == self.version:
            # Fast-path: dictionary lookup avoided
            return True

        # lookup in the dictionary
        value = self.dict.get(self.key, UNSET)
        if value is self.value:
            # another key was modified:
            # cache the new dictionary version
            self.version = version
            return True

        # the key was modified
        return False

dict 버전 사용

메서드 호출 속도 향상

Yury Selivanov는 메서드 호출을 최적화하는 patch to optimize method calls를 작성했습니다. 이 패치는 전역 딕셔너리 또는 내장 딕셔너리가 수정된 경우 캐시를 무효화하기 위해 딕셔너리 버전이 필요한 “implement per-opcode cache in ceval” 패치에 의존합니다.

또한 캐시는 딕셔너리 버전이 전역적으로 고유할 것을 요구합니다. 예를 들어 globals 매개변수를 사용하여 exec()로 한 네임스페이스에서 함수를 정의하고 다른 네임스페이스에서 호출할 수 있습니다. 이 경우 전역 딕셔너리가 교체되었으므로 캐시도 무효화해야 합니다.

가드를 사용하는 특수화된 함수

PEP 510은 가드를 사용하는 특수화된 함수를 지원하는 API를 제안합니다. 이를 통해 Python 의미론을 깨뜨리지 않고 Python용 정적 최적화 도구를 구현할 수 있습니다.

FAT Python 프로젝트의 fatoptimizer는 정적 Python 최적화기의 한 예입니다. 네임스페이스에 대한 가드가 필요한 많은 최적화를 구현합니다:

• 순수 내장 함수 호출: len("abc")를 3으로 대체하려면 builtins.__dict__['len'] 및 globals()['len'] 에 대한 가드가 필요합니다.
• 루프 언롤링: for i in range(...): ...루프를 언롤링하려면 builtins.__dict__['range'] 및 globals()['range'] 에 대한 가드가 필요합니다.
• 기타.

Pyjion

Pyjion의 주요 개발자 두 명 중 한 명인 Brett Cannon에 따르면, Pyjion은 딕셔너리 버전을 활용하여 최적화를 구현할 수 있습니다.

Pyjion은 CoreCLR(Microsoft .NET Core 런타임)을 기반으로 하는 Python용 JIT 컴파일러입니다.

Cython

Cython은 딕셔너리 버전을 활용하여 최적화를 구현할 수 있습니다.

Cython은 Python 프로그래밍 언어와 확장된 Cython 프로그래밍 언어 모두를 위한 최적화 정적 컴파일러입니다.

Unladen Swallow

딕셔너리 버전이 명시적으로 언급되지는 않았더라도, 전역 변수와 내장 함수 조회를 최적화하는 것은 Unladen Swallow 계획의 일부였습니다: “전역 변수와 내장 함수의 조회 속도를 높이기 위해 제안된 여러 방식 중 하나를 구현합니다.” (출처: Unladen Swallow ProjectPlan).

Unladen Swallow는 LLVM으로 구현된 JIT 컴파일러를 추가한 CPython 2.6.1의 포크입니다. 이 프로젝트는 2011년에 중단되었습니다: Unladen Swallow Retrospective.

변경 사항

C 타입 PY_UINT64_T(64비트 부호 없는 정수)를 사용하는 ma_version_tag 필드를 PyDictObject 구조체에 추가하십시오. 전역 딕셔너리 버전도 추가하십시오.

딕셔너리가 생성될 때마다 전역 버전을 증가시키고 딕셔너리 버전을 전역 버전으로 초기화합니다.

딕셔너리 내용이 수정될 때마다 전역 버전을 증가시키고 그 값을 딕셔너리 버전에 복사해야 합니다. 내용을 변경할 수 있는 딕셔너리 메서드는 다음과 같습니다:

• clear()
• pop(key)
• popitem()
• setdefault(key, value)
• __delitem__(key)
• __setitem__(key, value)
• update(...)

딕셔너리 메서드가 내용을 변경하지 않을 때 버전을 증가시킬지 여부는 Python 구현에 맡깁니다. Python 구현은 가드에서 딕셔너리 조회를 피하기 위해 버전을 증가시키지 않도록 결정할 수 있습니다. 딕셔너리 메서드가 내용을 변경하지 않는 경우의 예는 다음과 같습니다:

• 딕셔너리가 이미 비어 있는 경우의 clear()
• 키가 존재하지 않는 경우 pop(key)
• 딕셔너리가 비어 있는 경우 popitem()
• 키가 이미 존재하는 경우 setdefault(key, value)
• 키가 존재하지 않는 경우 __delitem__(key)
• 새 값이 현재 값과 동일한 경우 __setitem__(key, value)
• 인자 없이 호출되거나 새 값이 현재 값과 동일한 경우 update()

키를 기존 값과 동일한 새 값으로 설정하는 것도 딕셔너리 콘텐츠를 수정하는 작업으로 간주합니다.

버전만으로 딕셔너리를 식별할 수 있으려면 서로 다른 두 빈 딕셔너리가 서로 다른 버전을 가져야 합니다. 이를 통해 딕셔너리에 대한 강한 참조를 저장하지 않고 네임스페이스가 교체되지 않았는지 가드에서 확인할 수 있습니다. 빌린 참조를 사용하는 것은 작동하지 않습니다. 이전 딕셔너리가 소멸되면 새 딕셔너리가 동일한 메모리 주소에 할당될 수 있기 때문입니다. 또한 딕셔너리는 약한 참조를 지원하지 않습니다.

버전 증가는 원자적이어야 합니다. CPython에서는 전역 인터프리터 잠금(GIL)이 이미 dict 메서드를 보호하여 변경을 원자적으로 수행합니다.

가상의 dict_get_version(dict) 함수를 사용하는 예입니다.:

>>> d = {}
>>> dict_get_version(d)
100
>>> d['key'] = 'value'
>>> dict_get_version(d)
101
>>> d['key'] = 'new value'
>>> dict_get_version(d)
102
>>> del d['key']
>>> dict_get_version(d)
103

이 필드를 ma_version이 아니라 ma_version_tag라고 부르는 것은 정수 오버플로 후에는 잘못되게 되는 version <= old_version 대신 version_tag == old_version_tag를 사용하여 비교하도록 제안하기 위한 것입니다.

하위 호환성

PyDictObject 구조체는 안정 ABI의 일부가 아니며 새 딕셔너리 버전은 Python 범위에 노출되지 않으므로 변경 사항은 하위 호환성을 가집니다.

구현 및 성능

issue #26058: PEP 509: Add ma_version_tag to PyDictObject에는 이 PEP를 구현하는 패치가 포함되어 있습니다.

pybench 및 timeit 마이크로벤치마크에서 이 패치는 딕셔너리 연산에 어떠한 오버헤드도 추가하지 않는 것으로 보입니다. 예를 들어 다음 timeit 마이크로벤치마크는 변경 전후 모두 318나노초가 걸립니다.:

python3.6 -m timeit 'd={1: 0}; d[2]=0; d[3]=0; d[4]=0; del d[1]; del d[2]; d.clear()'

버전이 변경되지 않을 때 PyDict_GetItem()은 딕셔너리 조회에 14.8ns가 걸리는 반면, 가드 검사는 3.8ns만 걸립니다. 또한 가드는 여러 키를 감시할 수 있습니다. 예를 들어 함수에서 전역 변수 10개를 사용하는 최적화의 경우 딕셔너리 조회 10회에는 148ns가 걸리지만, 버전이 변경되지 않을 때 가드에는 여전히 3.8ns만 걸리므로 39배 빠릅니다.

fat module은 이러한 가드를 구현합니다. fat.GuardDict은 딕셔너리 버전을 기반으로 합니다.

정수 오버플로

이 구현은 버전을 저장하는 데 C 형식 PY_UINT64_T를 사용하며, 이는 64비트 부호 없는 정수입니다. C 코드는 version++를 사용합니다. 정수 오버플로가 발생하면 C 표준에 따라 버전은 0으로 되돌아간 후 계속 증가합니다.

정수 오버플로 후에는 감시 중인 딕셔너리 키가 수정되었는데도 가드가 성공할 수 있습니다. 이전 가드 검사 이후 정확히 2 ** 64회의 딕셔너리 생성 또는 수정이 있었을 때에만 가드 검사에서 버그가 발생합니다.

딕셔너리가 나노초마다 수정된다면, 2 ** 64번 수정하는 데 584년보다 오래 걸립니다. 32비트 버전을 사용하면 4초밖에 걸리지 않습니다. 이것이 32비트 시스템에서도 64비트 부호 없는 타입을 사용하는 이유입니다. C 수준에서 딕셔너리 조회에는 14.8ns가 걸립니다.

584년에 한 번 버그가 발생할 위험은 허용할 수 있습니다.

대안

Python 수준에서 버전을 읽기 전용 __version__ 속성으로 노출합니다.

PEP의 첫 번째 버전에서는 Python 수준에서 딕셔너리 버전을 읽기 전용 __version__속성으로 노출하고, collections.UserDict에도 이 속성을 추가할 것을 제안했습니다(이 타입은 dictAPI를 모방해야 하기 때문입니다).

여러 문제가 있습니다.

• 일관성을 유지하고 나쁜 예상 밖의 결과를 피하려면 모든 매핑 타입에 버전을 추가해야 합니다. 새로운 매핑 타입을 구현하려면 추가 작업이 필요하지만 실질적인 이점은 없습니다. 실제로 버전은 dict타입에만 필요하기 때문입니다.
• 모든 Python 구현에서 이 새로운 속성을 구현해야 하므로 다른 구현에 더 많은 작업이 생깁니다. 반면 다른 구현에서는 딕셔너리 버전을 전혀 사용하지 않을 수도 있습니다.
• 딕셔너리 버전을 Python 수준에서 노출하면 성능에 대해 잘못된 가정을 하게 될 수 있습니다. Python 수준에서 dict.__version__을 확인하는 것은 딕셔너리 조회보다 빠르지 않습니다. Python에서 딕셔너리 조회에는 48.7ns가 걸리고 버전 확인에는 47.5ns가 걸리므로, 차이는 1.2ns(3%)에 불과합니다.:

  $ python3.6 -m timeit -s 'd = {str(i):i for i in range(100)}' 'd["33"] == 33'
  10000000 loops, best of 3: 0.0487 usec per loop
  $ python3.6 -m timeit -s 'd = {str(i):i for i in range(100)}' 'd.__version__ == 100'
  10000000 loops, best of 3: 0.0475 usec per loop
  

• __version__은 정수 오버플로 시 순환할 수 있습니다. 오류가 발생하기 쉽습니다. dict.__version__ <= guard_version을 사용하는 것은 잘못이며, 정수 오버플로로 인한 버그 위험을 줄이려면 dict.__version__ == guard_version을 사용해야 합니다(실제로 정수 오버플로가 발생할 가능성은 낮더라도 그렇습니다).

속성 이름에 대한 필수적인 지엽적 논의:

• __cache_token__: Alyssa Coghlan이 제안한 이름이며, abc.get_cache_token()에서 유래한 이름입니다.
• __version__
• __version_tag__
• __timestamp__

각 딕셔너리 항목에 버전 추가

딕셔너리마다 하나의 버전만 사용하면 값에 대한 강한 참조를 유지해야 하며, 이로 인해 예상보다 오랫동안 값이 살아 있게 될 수 있습니다. 각 딕셔너리 항목에도 버전을 추가하면, 가드는 값에 대한 강한 참조를 피하기 위해 항목 버전(단순한 정수)만 저장할 수 있습니다. 딕셔너리와 키에 대한 강한 참조만 있으면 됩니다.

변경 사항: PyDictKeyEntry구조체에 me_version_tag필드를 추가하며, 이 필드의 C 타입은 PY_UINT64_T입니다. 키가 생성되거나 수정되면 항목 버전은 딕셔너리 버전으로 설정되며, 딕셔너리 버전은 변경(생성, 수정, 삭제)이 발생할 때마다 증가합니다.

가상의 dict_get_version(dict)및 dict_get_entry_version(dict)함수를 사용하여 딕셔너리 키가 수정되었는지 확인하는 빠른 가드의 의사 코드:

UNSET = object()

class GuardDictKey:
    def __init__(self, dict, key):
        self.dict = dict
        self.key = key
        self.dict_version = dict_get_version(dict)
        self.entry_version = dict_get_entry_version(dict, key)

    def check(self):
        """Return True if the dictionary entry did not change
        and the dictionary was not replaced."""

        # read the version of the dictionary
        dict_version = dict_get_version(self.dict)
        if dict_version == self.version:
            # Fast-path: dictionary lookup avoided
            return True

        # lookup in the dictionary to read the entry version
        entry_version = get_dict_key_version(dict, key)
        if entry_version == self.entry_version:
            # another key was modified:
            # cache the new dictionary version
            self.dict_version = dict_version
            self.entry_version = entry_version
            return True

        # the key was modified
        return False

이 선택지의 가장 큰 단점은 메모리 사용량에 미치는 영향입니다. 각 딕셔너리 항목의 크기가 증가하므로 오버헤드는 버킷 수(사용 중이거나 사용되지 않은 딕셔너리 항목 수)에 따라 달라집니다. 예를 들어 64비트 시스템에서는 각 딕셔너리 항목의 크기가 8바이트 증가합니다.

Python에서는 메모리 풋프린트가 중요하며, 이를 줄이는 추세입니다. 예시는 다음과 같습니다.

• PEP 393 – 유연한 문자열 표현
• PEP 412 – 키 공유 딕셔너리

새로운 dict 서브타입 추가

dict의 서브타입인 새로운 verdict 타입을 추가합니다. 가드가 필요한 경우에는 dict 대신 네임스페이스(모듈 네임스페이스, 타입 네임스페이스, 인스턴스 네임스페이스 등)에 verdict를 사용합니다.

가드를 사용하지 않을 때 오버헤드(CPU, 메모리 풋프린트)가 추가되지 않도록 dict 타입은 변경하지 않습니다.

기술적 문제: CPython 코어를 포함하여 실제로 사용되는 많은 C 코드가 정확한 dict 타입을 기대합니다. 문제:

• exec()는 전역 변수와 지역 변수에 dict를 요구합니다. 많은 코드가 globals={}를 사용합니다. 호출자는 globals 매개변수가 수정되기를 기대하므로 dict를 dict 서브타입으로 형 변환할 수 없습니다(dict는 변경 가능합니다).
• 객체가 dict 서브타입인 경우에도 C 함수는 PyObject_xxx()를 호출하는 대신 PyDict_xxx() 함수를 직접 호출합니다.
• PyDict_CheckExact() 검사는 dict 서브타입에서 실패하지만, 일부 함수는 정확한 dict 타입을 요구합니다.
• Python/ceval.c는 네임스페이스에 대한 dict 서브타입을 완전히 지원하지 않습니다.

exec() 문제는 차단 문제입니다.

기타 문제:

• 가비지 컬렉터에는 dict 인스턴스의 “추적을 해제”하는 특수 코드가 있습니다. 네임스페이스에 dict 서브타입을 사용하면 가비지 컬렉터가 일부 참조 순환을 끊지 못할 수 있습니다.
• 일부 함수에는 dict에 대한 빠른 경로가 있지만 dict 서브타입에서는 이 경로를 사용하지 못하므로 Python이 조금 느려집니다.

기존 사례

메서드 캐시 및 타입 버전 태그

2007년에 Armin Rigo는 메서드 캐시를 구현하는 패치를 작성했습니다. 이 패치는 Python 2.6에 병합되었습니다. 이 패치는 타입에 “타입 속성 캐시 버전 태그”(tp_version_tag)와 “유효한 버전 태그” 플래그를 추가합니다(PyTypeObject 구조체).

타입 버전 태그는 Python 수준에 노출되지 않습니다.

버전 태그의 C 타입은 unsigned int입니다. 캐시는 모든 타입이 공유하는 4096개 항목의 전역 해시 테이블입니다. 캐시는 “빠르고, 결정적이며 메모리 풋프린트가 작고, 무효화하기 쉽도록” 전역으로 유지됩니다. 각 캐시 항목에는 버전 태그가 있습니다. 다음 버전 태그를 생성하는 데 전역 버전 태그가 사용되며, 이 태그의 C 타입도 unsigned int입니다.

기본적으로 타입에는 버전 태그가 유효하지 않음을 나타내도록 “유효한 버전 태그” 플래그가 해제되어 있습니다. 타입의 첫 번째 메서드가 캐시되면 버전 태그와 “유효한 버전 태그” 플래그가 설정됩니다. 타입이 수정되면 해당 타입과 서브클래스의 “유효한 버전 태그” 플래그가 해제됩니다. 이후 이러한 타입의 캐시 항목이 사용되면 버전 태그가 오래되었기 때문에 해당 항목이 제거됩니다.

정수 오버플로가 발생하면 전체 캐시가 지워지고 전역 버전 태그가 0으로 재설정됩니다.

메서드 캐시 (이슈 #1685986) 및 Python 2.6용 Armin의 메서드 캐시 최적화 업데이트 (이슈 #1700288)를 참조하십시오.

전역 변수 / 내장 함수 캐시

2010년에 Antoine Pitrou는 PyDictObject 구조체(dict 타입)에 비공개 ma_version 필드를 추가하는 전역 변수 / 내장 함수 캐시 (이슈 #10401)를 제안했으며, 이 필드의 C 타입은 Py_ssize_t입니다.

이 패치는 함수와 프레임에 “전역 및 내장 캐시”를 추가하고, LOAD_GLOBAL 및 STORE_GLOBAL 명령어가 캐시를 사용하도록 변경합니다.

PyDictObject 구조체의 변경 사항은 이 PEP와 매우 유사합니다.

캐시된 전역 변수+내장 함수 조회

2006년에 Andrea Griffini는 캐시된 전역 변수+내장 함수 조회 최적화를 구현하는 패치를 제안했습니다. 이 패치는 PyDictObject 구조체(dict 타입)에 비공개 timestamp 필드를 추가하며, 이 필드의 C 타입은 size_t입니다.

python-dev의 스레드: 딕셔너리 조회 캐싱에 관하여 (2006년 12월).

반복 중 딕셔너리 변경 방지

2013년에 Serhiy Storchaka는 PyDictObject 구조체(dict 타입)에 ma_count 필드를 추가하는 반복 중 딕셔너리 변경 방지 (이슈 #19332)를 제안했으며, 이 필드의 C 타입은 size_t입니다. 딕셔너리가 수정되면 이 필드가 증가합니다.

PySizer

PySizer: Python용 메모리 프로파일러이자 Nick Smallbone의 2005년 Google Summer of Code 프로젝트입니다.

이 프로젝트에는 딕셔너리 항목에 key_time 및 value_time 필드를 추가하는 CPython 2.4용 패치가 있습니다. 이 패치는 딕셔너리용 프로세스 전체 전역 카운터를 사용하며, 딕셔너리가 수정될 때마다 카운터를 증가시킵니다. 이 시간 값은 자식 객체가 부모 객체에 처음 나타난 시점을 결정하는 데 사용됩니다.

토론

메일링 리스트의 스레드:

• python-dev: 업데이트된 PEP 509
• python-dev: RFC: PEP 509: dict에 비공개 버전 추가
• python-dev: PEP 509: dict에 비공개 버전 추가 (2016년 1월)
• python-ideas: RFC: PEP: dict.__version__ 추가 (2016년 1월)

승인

이 PEP는 2016-09-07에 Guido van Rossum에 의해 수락됨에 의해 수락되었습니다. 이후 PEP 구현이 저장소에 커밋되었습니다.

Copyright

This document has been placed in the public domain.