PEP 603 – collections에 frozenmap 타입 추가

Author:: Yury Selivanov <yury at edgedb.com>
Discussions-To:: Discourse thread
Status:: Draft
Type:: Standards Track
Created:: 12-Sep-2019
Post-History:: 12-Sep-2019

Table of Contents

번역·라이선스 안내

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

초록

영속 자료 구조는 데이터가 수정될 때 데이터의 이전 버전을 보존하는 자료 구조로 정의됩니다. 이러한 자료 구조에 대한 연산은 구조를 제자리에서 갱신하지 않고 항상 갱신된 새 구조를 내놓으므로, 이러한 자료 구조는 사실상 불변입니다(자세한 내용은 [0]을 참고하십시오).

이 PEP는 frozenmap이라는 완전히 영속적이고 불변인 새 매핑 타입을 collections 모듈에 추가할 것을 제안합니다.

frozenmap 참조 구현의 대부분은 이미 CPython에서 contextvars 모듈을 구현하는 데 사용되고 있습니다.

근거

Python에는 tuple과 frozenset이라는 두 가지 불변 컬렉션 타입이 있습니다. 이 타입들은 불변 리스트와 집합을 표현하는 데 사용할 수 있습니다. 하지만 불변 매핑을 표현하는 방법은 아직 존재하지 않으며, 이 PEP는 불변 매핑을 구현하기 위해 frozenmap을 제안합니다.

제안하는 frozenmap 타입은:

collections.abc.Mapping 프로토콜을 구현하고,
피클링을 지원하며,
“수정된” 버전을 효율적으로 생성하기 위한 API를 제공합니다.

다음 사용 사례들은 불변 매핑이 왜 바람직한지를 보여 줍니다.

불변 매핑은 해시 가능하므로 딕셔너리 키나 집합 원소로 사용할 수 있습니다.
이러한 해시 가능 속성 덕분에 @functools.lru_cache() 데코레이터가 적용된 함수가 불변 매핑을 인자로 받을 수 있습니다. 불변 매핑과 달리, 일반 dict를 그러한 함수에 전달하면 오류가 발생합니다.
불변 매핑은 복잡한 상태를 담을 수 있습니다. 불변 매핑은 참조로 복사할 수 있으므로, 상태의 트랜잭션 방식 변경을 효율적으로 구현할 수 있습니다.
불변 매핑을 사용하면 스레드와 비동기 태스크의 경계를 넘어 딕셔너리를 안전하게 공유할 수 있습니다. 불변성 덕분에 스레드와 비동기 태스크에 대해 추론하기가 더 쉬워집니다.

마지막으로, CPython [1]에는 frozenmap 구현에 필요한 C 코드의 주요 부분이 이미 포함되어 있습니다. 이 C 코드는 contextvars 모듈을 구현하기 위해 이미 존재합니다(자세한 내용은 PEP 567을 참고하십시오). 이 C 코드를 공개 컬렉션 타입으로 노출하면 코드의 사용자 수가 크게 늘어납니다. 이는 버그를 발견하고 성능을 개선함으로써 코드 품질을 높이는 결과로 이어집니다. 대부분의 프로그램이 contextvars 모듈을 간접적으로 사용하기 때문에, frozenmap 컬렉션이 없다면 이는 매우 어려울 것입니다.

명세

새로운 공개 불변 타입 frozenmap이 collections 모듈에 추가됩니다.

생성

frozenmap은 dict와 유사한 생성 API를 구현합니다.

frozenmap()은 비어 있는 새 불변 매핑을 생성합니다.
frozenmap(**kwargs)는 **kwargs로부터 매핑을 생성합니다. 예: frozenmap(x=10, y=0, z=-1)
frozenmap(collection)은 전달된 collection 객체로부터 매핑을 생성합니다. 전달되는 collection 객체는 다음 중 하나일 수 있습니다.
- dict,
- 다른 frozenmap,
- 일련의 키/값 튜플을 반환할 것으로 기대되는 items() 메서드를 가진 객체, 또는
- 키/값 튜플의 이터러블.

데이터 접근

frozenmap은 collection.abc.Mapping 프로토콜을 구현합니다. 따라서 getter, 멤버십 검사, 이터레이션은 dict에서와 같은 방식으로 동작합니다.:

m = frozenmap(foo='bar')

assert m['foo'] == 'bar'
assert m.get('foo') == 'bar'
assert 'foo' in m

assert 'baz' not in m
assert m.get('baz', 'missing') == 'missing'

assert m == m
assert m != frozenmap()  # m is not equal to an empty frozenmap

assert len(m) == 1

# etc.

변경

frozenmap 인스턴스는 불변입니다. 그렇지만 불변 인스턴스의 변경된 복사본을 효율적으로 만들어 낼 수 있습니다.

변경 연산의 복잡도는 O(log N)이며, 구조적 공유를 사용하기 때문에 결과로 생성되는 frozenmap 복사본은 대개 추가 메모리를 거의 소비하지 않습니다(자세한 내용은 [6]을 참고하십시오.)

frozenmap.including(key, value)

이 메서드는 새로운 key / value 쌍이 추가된 새 frozenmap 복사본을 생성합니다.:

m = frozenmap(foo=1)
m2 = m.including('bar', 100)

print(m)   # will print frozenmap({'foo': 1})
print(m2)  # will print frozenmap({'foo': 1, 'bar': 100})

frozenmap.excluding(key)

이 메서드는 삭제된 key를 포함하지 않는 frozenmap의 복사본을 생성합니다.:

m = frozenmap(foo=1, bar=100)

m2 = m.excluding('foo')

print(m)   # will print frozenmap({'foo': 1, 'bar': 100})
print(m2)  # will print frozenmap({'bar': 1})

m3 = m.excluding('spam')  # will throw a KeyError('spam')

frozenmap.union(mapping=None, **kw)

이 메서드는 frozenmap의 복사본을 생성하고, 생성된 복사본에 여러 키/값을 추가하거나 수정합니다. 이 메서드의 시그니처는 frozenmap 생성자의 시그니처와 같습니다.:

m = frozenmap(foo=1)

m2 = m.union({'spam': 'ham'})
print(m2)  # will print frozenmap({'foo': 1, 'spam': 'ham'})

m3 = m.union(foo=100, y=2)
print(m3)  # will print frozenmap({'foo': 100, 'y': 2})

print(m)   # will print frozenmap({'foo': 1})

N개의 키를 추가/교체할 때 union() 메서드를 호출하는 것이 including() 메서드를 N번 호출하는 것보다 효율적입니다.

frozenmap.mutating()

이 메서드를 사용하면 여러 수정 사항이 적용된 frozenmap 인스턴스 복사본을 효율적으로 만들 수 있습니다. 이 메서드는 해당 frozenmap에 수천 개의 키/값 쌍이 들어 있고, 코드에서 성능이 중요한 구간에서 그중 다수를 갱신해야 할 때 특히 유용합니다.

frozenmap.mutating() 메서드는 frozenmap 객체의 변경 가능한 dict 형태 복사본, 즉 collections.FrozenMapCopy의 인스턴스를 반환합니다.

FrozenMapCopy 객체는 다음과 같습니다.

자신을 생성한 원본 frozenmap 인스턴스 데이터에 대한 copy-on-write 뷰입니다.
변경 가능하지만, 이 객체에 가한 변경은 자신을 생성한 원본 frozenmap 인스턴스에 영향을 주지 않습니다.
frozenmap 생성자에 전달할 수 있으며, FrozenMapCopy 객체로부터 frozenmap을 생성하는 것은 O(1) 연산입니다.
get/set 연산의 복잡도는 O(log N)이며, 이 객체를 생성하는 것은 O(1) 연산입니다.
이후의 모든 데이터 접근/변경을 막는 FrozenMapCopy.close() 메서드가 있습니다.
컨텍스트 관리자로 사용할 수 있습니다.

아래 예제는 mutating()을 컨텍스트 관리자와 함께 사용하는 방법을 보여 줍니다.:

numbers = frozenmap((i, i ** 2) for i in range(1_000_000))

with numbers.mutating() as copy:
    for i in numbers:
        if not (numbers[i] % 997):
            del copy[i]

    numbers_without_997_multiples = frozenmap(copy)

    # at this point, *numbers* still has 1_000_000 key/values, and
    # *numbers_without_997_multiples* is a copy of *numbers* without
    # values that are multiples of 997.

    for i in numbers:
        if not (numbers[i] % 593):
            del copy[i]

    numbers_without_593_multiples = frozenmap(copy)

    print(copy[10])  # will print 100.

print(copy[10])  # This will throw a ValueError as *copy*
                 # has been closed when the "with" block
                 # was executed.

이터레이션

frozenmap은 표준 collections.abc.Mapping 프로토콜을 구현하므로, 예상되는 모든 이터레이션 방식을 지원합니다.:

assert list(m) == ['foo']
assert list(m.items()) == [('foo', 'bar')]
assert list(m.keys()) == ['foo']
assert list(m.values()) == ['bar']

frozenmap의 이터레이션은 dict와 달리 삽입 순서를 보존하지 않습니다.

해싱

frozenmap 인스턴스는 tuple 객체와 마찬가지로 해시 가능할 수 있습니다.:

hash(frozenmap(foo='bar'))  # works
hash(frozenmap(foo=[]))     # will throw an error

타이핑

frozenmap에는 표준 타이핑 표기법을 사용할 수 있습니다.:

m: frozenmap[str, int] = frozenmap()

구현

제안하는 frozenmap 불변 타입은 해시 배열 매핑 트라이(Hash Array Mapped Trie, HAMT) 자료 구조를 사용합니다. Clojure와 같은 함수형 프로그래밍 언어는 불변 해시 테이블, 벡터, 집합을 효율적으로 구현하기 위해 HAMT를 사용합니다.

HAMT

HAMT의 핵심 설계 계약은 키의 해시가 주어지면 예측 가능한 값을 보장한다는 것입니다. 키와 값의 쌍에서, 키의 해시를 사용하여 해시 맵 트리에서 값의 위치를 결정할 수 있습니다.

HAMT로 구현된 불변 매핑은 set()과 get() 연산에서 O(log N) 성능을 보입니다. 이러한 효율이 가능한 것은 변경 연산이 트리의 한 브랜치에만 영향을 미치므로 변경되지 않은 브랜치를 재사용할 수 있고, 따라서 수정되지 않은 데이터의 복사를 피할 수 있기 때문입니다.

HAMT에 대한 자세한 내용은 [5]를 참고하십시오. CPython 구현 [1]에도 알고리즘에 대한 상당히 자세한 설명이 있습니다.

성능

../_images/pep-0603-hamt_vs_dict.png — Figure 1. Benchmark code can be found here: [3].

위 차트는 다음을 보여 줍니다.

HAMT로 구현된 frozenmap은 벤치마크한 모든 딕셔너리 크기에서 O(1)에 가까운 성능을 보입니다.
dict.copy()는 항목이 약 100~200개일 때 효율이 떨어집니다.

../_images/pep-0603-lookup_hamt.png — Figure 2. Benchmark code can be found here: [4].

그림 2는 dict와 HAMT 기반 불변 매핑의 조회 비용을 비교합니다. HAMT 조회 시간은 평균적으로 Python dict 조회보다 약 30% 느립니다. 이러한 성능 차이는 얕은 트리를 순회하는 것이 평평한 연속 배열에서 조회하는 것보다 덜 효율적이기 때문에 발생합니다.

더 나아가 [6]을 인용하면 다음과 같습니다. “[HAMT를 사용한다는 것은] 실제로 영속 해시 배열 매핑 트라이에 대한 삽입, 삭제, 조회의 계산 복잡도가 O(log n)이지만, 대부분의 애플리케이션에서는 사실상 상수 시간이라는 것을 의미합니다. 어떤 연산이든 십여 단계를 넘기려면 극도로 많은 수의 항목이 필요하기 때문입니다.”

설계 시 고려 사항

“FrozenMap”이 아니라 “frozenmap”인 이유

소문자 “frozenmap”은 frozenset 내장 타입뿐만 아니라 collections.defaultdict 같은 타입과도 잘 어울립니다.

“frozendict”가 아니라 “frozenmap”인 이유

“Dict”는 Python에서 매우 구체적인 의미를 가집니다.

dict는 get과 set 연산이 O(1)인 abc.MutableMapping의 구체적인 구현입니다(frozenmap의 복잡도는 O(log N)입니다);
Python 딕셔너리는 삽입 순서를 보존합니다.

제안된 frozenmap에는 앞서 언급한 이러한 속성이 없습니다. 대신 frozenmap의 set/get 연산 비용은 O(log N)이며, abc.Mapping 프로토콜만 구현합니다.

Python 개선 제안 한국어 번역