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 항목에 버전 추가하기
  • 새 dict 서브타입 추가
• 선행 사례
  • 메서드 캐시와 타입 버전 태그
  • 전역 / 내장 캐시
  • 캐시된 전역+내장 조회
  • 이터레이션 중 딕셔너리 변경 방지
  • PySizer
• 논의
• 수락
• Copyright

번역·라이선스 안내

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

초록

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

근거

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

Python은 거의 모든 것이 가변적이기 때문에 최적화하기 어렵습니다. 내장 함수, 함수 코드, 전역 변수, 지역 변수 등을 런타임에 수정할 수 있습니다. Python 의미를 지키면서 최적화를 구현하려면 “무언가가 바뀌는” 시점을 감지해야 합니다. 이러한 검사를 “가드(guard)”라고 부르겠습니다.

최적화로 얻는 속도 향상은 가드 검사의 속도에 달려 있습니다. 이 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는 메서드 호출을 최적화하는 패치를 작성했습니다. 이 패치는 “implement per-opcode cache in ceval” 패치에 의존하며, 이 패치는 전역 딕셔너리나 내장 딕셔너리가 수정되었을 때 캐시를 무효화하기 위해 딕셔너리 버전을 필요로 합니다.

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

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

PEP 510은 가드를 사용하는 특수화된 함수를 지원하기 위한 API를 제안합니다. 이 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.

변경 사항

PyDictObject 구조체에 C 타입이 PY_UINT64_T(64비트 부호 없는 정수)인 ma_version_tag 필드를 추가합니다. 또한 전역 딕셔너리 버전도 추가합니다.

딕셔너리가 생성될 때마다 전역 버전이 증가하고, 딕셔너리 버전은 전역 버전으로 초기화됩니다.

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

• 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()

키를 이전 값과 같은 새 값으로 설정하는 것도 딕셔너리 내용을 수정하는 연산으로 간주합니다.

버전만으로 딕셔너리를 식별할 수 있으려면 서로 다른 두 빈 딕셔너리는 서로 다른 버전을 가져야 합니다. 이를 통해 딕셔너리에 대한 강한 참조를 저장하지 않고도 가드에서 네임스페이스가 교체되지 않았음을 검증할 수 있습니다. 빌린 참조(borrowed reference)를 사용하는 방법은 통하지 않습니다. 이전 딕셔너리가 파괴되면 새 딕셔너리가 같은 메모리 주소에 할당될 수 있기 때문입니다. 덧붙여, 딕셔너리는 약한 참조를 지원하지 않습니다.

버전 증가는 원자적이어야 합니다. 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 모듈이 이러한 가드를 구현합니다. fat.GuardDict는 딕셔너리 버전을 기반으로 합니다.

정수 오버플로

구현에서는 버전을 저장하는 데 C 타입 PY_UINT64_T, 즉 64비트 부호 없는 정수를 사용합니다. C 코드는 version++를 사용합니다. 정수 오버플로가 발생하면 C 표준에 따라 버전이 0으로 되돌아갑니다(그리고 그 뒤로 계속 증가합니다).

정수 오버플로 후에는 감시하던 딕셔너리 키가 수정되었는데도 가드가 통과할 수 있습니다. 이 버그는 이전 가드 검사 이후 딕셔너리 생성이나 수정이 정확히 2 ** 64 번 일어난 경우에만 가드 검사에서 발생합니다.

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

584년마다 한 번 버그가 생길 위험은 받아들일 만합니다.

대안

버전을 Python 수준에서 읽기 전용 __version__ 프로퍼티로 노출하기

이 PEP의 첫 번째 버전은 딕셔너리 버전을 Python 수준에서 읽기 전용 __version__ 프로퍼티로 노출하고, 이 프로퍼티를 collections.UserDict에도 추가할 것을 제안했습니다(이 타입은 dict API를 흉내 내야 하기 때문입니다).

여기에는 여러 가지 문제가 있습니다.

• 일관성을 유지하고 예상치 못한 문제를 피하려면 모든 매핑 타입에 버전을 추가해야 합니다. 실제로 버전이 필요한 타입은 dict 타입뿐이므로, 새 매핑 타입을 구현하려면 아무 이점도 없는 추가 작업이 필요합니다.
• 모든 Python 구현이 이 새 프로퍼티를 구현해야 하므로 다른 구현에 일이 늘어나지만, 정작 그 구현들은 딕셔너리 버전을 전혀 사용하지 않을 수도 있습니다.
• 딕셔너리 버전을 Python 수준에 노출하면 성능에 대해 잘못된 가정을 하게 만들 수 있습니다. Python 수준에서 dict.__version__을 검사하는 것은 딕셔너리 조회보다 빠르지 않습니다. Python에서 딕셔너리 조회에는 48.7 ns가 들고 버전 검사에는 47.5 ns가 들어, 차이는 1.2 ns(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__

각 dict 항목에 버전 추가하기

딕셔너리마다 버전을 하나만 두면 값에 대한 강한 참조를 유지해야 하므로, 값이 예상보다 오래 살아 있을 수 있습니다. 딕셔너리 항목마다 버전을 추가로 두면, 가드는 값에 대한 강한 참조를 피하기 위해 항목 버전(단순한 정수)만 저장할 수 있습니다. 이 경우 딕셔너리와 키에 대한 강한 참조만 있으면 됩니다.

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

exec() 문제는 진행을 가로막는 문제입니다.

기타 문제:

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

선행 사례

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

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

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

버전 태그의 C 타입은 unsigned int입니다. 캐시는 모든 타입이 공유하는 4096개 항목의 전역 해시 테이블입니다. 캐시는 “빠르게 동작하고, 결정적이면서 적은 메모리 사용량을 가지며, 쉽게 무효화할 수 있도록” 전역으로 되어 있습니다. 각 캐시 항목에는 버전 태그가 있습니다. 다음 버전 태그를 만드는 데 전역 버전 태그가 사용되며, 이 태그의 C 타입 역시 unsigned int입니다.

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

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

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

전역 / 내장 캐시

2010년에 Antoine Pitrou는 전역 / 내장 캐시 (이슈 #10401)를 제안했습니다. 이 제안은 PyDictObject 구조체(dict 타입)에 비공개 ma_version 필드를 추가하며, 이 필드의 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는 이터레이션 중 딕셔너리 변경 방지 (이슈 #19332)를 제안했습니다. 이 제안은 PyDictObject 구조체(dict 타입)에 ma_count 필드를 추가하며, 이 필드의 C 타입은 size_t입니다. 이 필드는 딕셔너리가 수정될 때 증가합니다.

PySizer

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

이 프로젝트에는 딕셔너리 항목에 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.