PEP 3128 – BList: 더 빠른 리스트 유사 형식

Author:: Daniel Stutzbach <daniel at stutzbachenterprises.com>
Discussions-To:: Python-3000 list
Status:: Rejected
Type:: Standards Track
Created:: 30-Apr-2007
Python-Version:: 2.6, 3.0
Post-History:: 30-Apr-2007

Table of Contents

거부 통지
초록
동기
사용 사례별 절충
구현
메모리 사용량
하위 호환성
참조 구현
- 다른 Python 변형으로 포팅하기
논의
진행 중인 작업
참고 자료
Copyright

번역·라이선스 안내

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

거부 통지

Raymond Hettinger의 현명한 조언 [4]에 따라 거부되었습니다:

소스 코드를 살펴본 결과, 이것이 list()를 대체할 가능성은 거의 없다고 생각합니다. 간단한 C API, 작은 리스트에서의 낮은 공간 오버헤드, 일반적인 사용 사례에서의 우수한 성능, 그리고 쉽게 이해할 수 있는 성능에는 너무 큰 가치가 있습니다. BList 구현에는 이러한 장점이 없으며, 일반적인 경우의 약간의 성능을 드문 경우의 훨씬 더 나은 성능과 맞바꿉니다. Py3.0 PEP로서는 거부할 수 있다고 생각합니다.
서드파티 모듈로서 성공하느냐에 따라 collections 모듈에 포함될 가능성은 여전히 있습니다. 핵심 기준은 일부 실제 사용 사례에서 이것이 더 나은 선택인지 여부입니다. 제 코드를 살펴보았지만, 일반 리스트보다 BList가 더 적합했을 만한 경우는 하나도 찾지 못했습니다. 그러나 BList를 사용할 수 있었다면 제가 작성했을 코드를 반영하지 않으므로, 이러한 조사에는 선택 편향이 있습니다. 따라서 몇 달 후에 comp.lang.python에 BList 성공 사례가 있는지 조사할 예정입니다. 그러한 사례가 있다면 collections 모듈에 포함하는 데 아무런 문제가 없습니다. 결국 학습 곡선은 거의 0에 가깝습니다. 유일한 비용은 주어진 작업에 가장 적합한 데이터 구조를 결정하지 못해 발생하는 혼란 요인입니다.

초록

리스트 연산의 일반적인 경우는 작은 리스트에서 발생합니다. 현재의 배열 기반 리스트 구현은 참조 지역성이 높고 메모리 할당 연산이 드물기 때문에 작은 리스트에서 뛰어난 성능을 보입니다. 그러나 배열은 요소를 삽입하고 삭제하는 데 O(n) 시간이 걸리므로 리스트가 커지면 문제가 될 수 있습니다.

이 PEP는 배열과 트리의 특성을 모두 지닌 새로운 데이터 형식인 BList를 소개합니다. 기존 배열 기반 구현과 마찬가지로 작은 리스트에서 우수한 성능을 제공하면서도, 대부분의 연산에서 더 나은 점근적 성능을 제공합니다. 이 PEP는 BList 형식을 Python에 포함하기 위한 상호 배타적인 두 가지 제안을 합니다:

collections 모듈에 추가하거나,
기존 리스트 형식을 대체합니다.

BList는 작은 입력에서는 잘 작동하지만 배열 기반 리스트의 근본적인 O(n) 동작 때문에 큰 입력에서는 O(n**2) 시간이 걸리는 직관적인 알고리즘을 다시 작성해야 했던 불만에서 비롯되었습니다. Python 2.4에서 도입된 deque 형식은 빠른 FIFO 큐가 필요하다는 가장 일반적인 문제를 해결했습니다. 그러나 긴 리스트의 중간에서 요소를 반복적으로 삽입하거나 삭제해야 하는 경우에는 deque 형식이 도움이 되지 않습니다.

매우 다양한 데이터 구조가 삽입 및 삭제에 대해 우수한 점근적 성능을 제공하지만, 다른 연산에서 O(n) 성능을 보이거나(예: 연결 리스트), 작은 리스트에서 성능이 떨어집니다(예: 이진 트리와 스킵 리스트).

이 PEP에서 제안하는 BList 형식은 배열과 트리의 특성을 모두 지닌 B+Trees의 원리에 기반합니다. BList는 작은 리스트에서 배열과 같은 성능을 제공하는 동시에, 모든 삽입 및 삭제 연산에서 O(log n)의 점근적 성능을 제공합니다. 또한 BList는 내부적으로 copy-on-write를 구현하므로 getslice와 같은 연산도 O(log n) 시간이 걸립니다. 아래 표는 현재 배열 기반 리스트 구현의 점근적 성능과 BList의 점근적 성능을 비교합니다.

연산	배열 기반 리스트	BList
복사	O(n)	O(1)
추가	O(1)	O(log n)
삽입	O(n)	O(log n)
항목 가져오기	O(1)	O(log n)
항목 설정	O(1)	O(log n)
항목 삭제	O(n)	O(log n)
반복	O(n)	O(n)
슬라이스 가져오기	O(k)	O(log n)
슬라이스 삭제	O(n)	O(log n)
슬라이스 설정	O(n+k)	O(log k + log n)
확장	O(k)	O(log k + log n)
정렬	O(n log n)	O(n log n)
곱셈	O(nk)	O(log k)

Python의 배열 기반 리스트와 BList를 광범위하게 경험적으로 비교한 결과는 [2]에서 확인할 수 있습니다.

사용 사례별 절충

BList는 많은 작업에서 우수한 성능을 제공하지만, 모든 작업에서 그런 것은 아닙니다. 특정 사용 사례에 적합한 데이터 형식을 선택하려면 어떤 작업이 사용되는지를 고려해야 합니다. 내장 데이터 형식으로 적합한 데이터 형식을 선택하려면 다양한 사용 사례의 중요도와 성능 차이의 크기 사이에서 균형을 잡아야 합니다.

소규모 리스트라는 일반적인 사용 사례에서는 배열 기반 리스트와 BList의 성능 특성이 유사합니다.

다소 덜 일반적인 대규모 리스트의 경우에는 기존 배열 기반 리스트가 기존 BList 참조 구현보다 성능이 우수한 두 가지 일반적인 사용 사례가 있습니다. 다음과 같습니다:

많은 .append() 및 .pop(-1) 연산이 수행되는 대규모 LIFO 스택입니다. 배열 기반 리스트에서는 각 작업이 O(1)이지만, BList에서는 O(log n)입니다.
크기가 변경되지 않는 대규모 리스트입니다. 배열 기반 리스트에서는 getitem 및 setitem 호출이 O(1)이지만, BList에서는 O(log n)입니다.

10,000개 요소로 구성된 리스트의 성능 테스트에서 BList는 이 두 사용 사례에 대해 각각 실행 시간이 50% 및 5% 증가했습니다.

루트 노드 내의 가장 오른쪽 리프에 대한 포인터를 캐시하면 LIFO 사용 사례의 성능을 O(n) 시간으로 개선할 수 있습니다. 크기가 변경되지 않는 리스트에서는 루트 노드에 캐시하여 순차 액세스라는 일반적인 경우의 성능도 O(n) 시간으로 개선할 수 있습니다. 그러나 이러한 접근 방식의 성능은 경험적으로 테스트되지 않았습니다.

배열 기반 리스트에서 BList로 전환하면 많은 작업에서 엄청난 속도 향상(O(n)에서 O(log n)으로)이 나타납니다. 10,000개 요소로 구성된 리스트의 성능 테스트에서 getslice, setslice, FIFO 방식의 삽입 및 삭제와 같은 BList의 작업은 배열 기반 리스트에 필요한 시간의 1%만 소요됩니다.

많은 작업에서 성능이 크게 향상된다는 점을 고려하면, 일부 작업에서 발생하는 작은 성능 비용은 많은 애플리케이션에서, 모든 애플리케이션은 아니더라도, 감수할 만한 가치가 있습니다.

구현

BList는 B+트리 데이터 구조를 기반으로 합니다. BList는 폭이 넓고 가지가 많은 트리이며, 각 노드는 자식에 대한 포인터를 최대 128개까지 담는 배열을 포함합니다. 노드가 리프인 경우, 해당 노드의 자식은 사용자가 리스트에 배치한 사용자에게 표시되는 객체입니다. 노드가 리프가 아닌 경우, 해당 노드의 자식은 사용자에게 표시되지 않는 다른 BList 노드입니다. 리스트에 요소가 몇 개만 포함된 경우, 모든 요소는 루트이면서 동시에 리프인 하나의 노드의 자식이 됩니다. 노드는 사실상 포인터 배열에 불과하므로, 작은 리스트는 배열 기반 데이터 형식과 실질적으로 동일한 방식으로 동작하며 동일한 우수한 성능 특성을 공유합니다.

BList는 삽입 및 삭제 연산의 순서와 관계없이 우수한 (O(log n)) 점근적 성능을 보장하기 위해 몇 가지 불변 조건을 유지합니다. 주요 불변 조건은 다음과 같습니다.

각 노드에는 자식이 최대 128개 있습니다.
루트가 아닌 각 노드에는 자식이 최소 64개 있습니다.
리스트에 요소가 2개 미만으로 포함된 경우를 제외하면, 루트 노드에는 자식이 최소 2개 있습니다.
트리의 깊이는 균일합니다.

삽입으로 인해 노드의 자식 수가 128개를 초과하게 되면, 해당 노드는 형제 노드를 생성하고 자식의 절반을 형제 노드로 옮깁니다. 형제 노드는 해당 노드의 부모에 삽입됩니다. 해당 노드가 루트 노드인 경우(따라서 부모가 없는 경우), 새 부모가 생성되고 트리의 깊이가 1 증가합니다.

삭제로 인해 노드의 자식 수가 64개 미만이 되면, 가능한 경우 해당 노드는 형제 노드 중 하나에서 요소를 가져옵니다. 두 형제 노드에도 자식이 각각 64개만 있는 경우에는 두 노드가 병합되고, 비어 있는 노드는 부모에서 제거됩니다. 루트 노드의 자식이 하나만 남게 되면, 해당 하나의 자식이 새로운 루트가 됩니다(즉, 트리의 깊이가 1 감소합니다).

BList는 트리와 같은 점근적 성능 및 작은 리스트에서의 배열과 같은 성능에 더해, 투명한 copy-on-write를 지원합니다. 리프가 아닌 노드를 복사해야 하는 경우(getslice, copy, setslice 등), 해당 노드는 복사되는 대신 여러 부모 사이에서 공유됩니다. 이후 해당 노드를 수정해야 하면 그 시점에 복사됩니다. 이 과정은 완전히 내부적으로 처리되며, 사용자의 관점에서는 BList가 일반 Python 리스트와 똑같이 작동합니다.

메모리 사용량

최악의 경우 BList의 리프 노드에는 최대 128개가 아닌 자식이 각각 64개만 있으므로, 메모리 사용량은 최선의 경우의 배열 구현보다 약 2배 많습니다. 리프가 아닌 노드는 추가 메모리를 무시할 수 있을 정도만 사용하는데, 리프 노드의 수가 리프가 아닌 노드의 수보다 최소 63배 많기 때문입니다.

기존 배열 기반 리스트 구현은 항목이 추가되고 제거됨에 따라 크기가 증가하고 감소해야 합니다. 효율성을 위해 리스트의 크기가 지수적으로 증가하거나 감소했을 때만 크기를 늘리거나 줄입니다. 최악의 경우 이 구현 역시 최선의 경우보다 메모리를 2배 많이 사용합니다.

요약하면, BList의 메모리 사용량은 기존 배열 기반 구현과 크게 다르지 않습니다.

하위 호환성

BList를 collections 모듈에 추가하면 하위 호환성은 문제가 되지 않습니다. 이 절에서는 기존 배열 기반 리스트를 BList로 대체하는 방안에 중점을 둡니다. Python 인터프리터 사용자의 관점에서 BList는 현재 리스트 구현과 동일한 인터페이스를 제공합니다. 실행 속도를 제외하면 거의 모든 연산에서 동작이 동일합니다.

C API에서 BList는 기존 리스트 구현과 다른 인터페이스를 가집니다. BList는 구조가 더 복잡하므로 외부 소스가 이를 직접 이리저리 조작하기에 적합하지 않습니다. 다행히 기존 리스트 구현은 리스트 객체의 데이터에 접근하기 위한 함수와 매크로의 API를 정의합니다. Google Code Search에 따르면 대부분의 서드파티 모듈은 리스트의 구조에 직접 의존하기보다 잘 정의된 API를 사용합니다. 아래 표는 검색 질의와 결과를 요약합니다.

검색 문자열	결과 수
PyList_GetItem	2,000
PySequence_GetItem	800
PySequence_Fast_GET_ITEM	100
PyList_GET_ITEM	400
[^a-zA-Z_]ob_item	100

이는 다음 두 가지 방법 중 하나로 달성할 수 있습니다.

listobject.h의 다양한 접근자 함수와 매크로를 BList에 접근하도록 대신 재정의하십시오. 인터페이스는 변경되지 않습니다. 함수는 쉽게 재정의할 수 있습니다. 매크로는 좀 더 주의가 필요하며 큰 리스트에서는 함수 호출을 사용해야 합니다.
매크로는 인자를 두 번 이상 평가해야 하므로, 인자에 부작용이 있으면 문제가 될 수 있습니다. Google Code Search에서 “PyList_GET_ITEM([^)]+(“을 검색한 결과 이러한 경우는 몇 건에 불과했으므로 영향은 적을 것으로 보입니다.

API를 사용하지 않고 리스트의 문서화되지 않은 구조를 직접 사용하는 소수의 확장 모듈은 작동하지 않게 됩니다. 핵심 코드 자체는 접근자 매크로를 상당히 일관되게 사용하므로 쉽게 이식할 수 있을 것입니다.
기존 리스트 타입을 폐기하지만 계속 포함합니다. 새로운 BList 타입을 사용하려는 확장 모듈은 이를 명시적으로 수행해야 합니다. BList C 인터페이스를 기존 PyList 인터페이스에 맞게 변경하면 간단한 검색-대체만으로 모듈 작성자의 99%에게 충분하도록 만들 수 있습니다.
기존 모듈은 변경 없이 계속 컴파일되고 작동하지만, BList로 마이그레이션하려면 의도적인(그러나 작은) 노력이 필요합니다.

이 접근 방식의 단점은 변환이 자주 필요할 경우 BList를 사용하는 모듈과 배열 기반 리스트를 사용하는 모듈을 혼합하면 성능이 저하될 수 있다는 점입니다.

참조 구현

CPython용 BList 참조 구현은 [1]에서 사용할 수 있습니다.

소스 패키지에는 CPython 버전의 프로토타입으로 처음 개발된 순수 Python 구현도 포함되어 있습니다. 당연히 순수 Python 버전은 상당히 느리며, 리스트가 상당히 커질 때까지는 점근적 성능 향상이 효과를 발휘하지 않습니다.

Py_DEBUG로 컴파일하면 C 구현은 대부분의 함수에 진입하고 종료할 때 BList 불변식을 검사합니다.

소스 패키지에는 광범위한 테스트 사례 집합도 포함되어 있습니다. 테스트 사례에는 기존 Python 시퀀스 및 리스트 테스트 사례가 하위 집합으로 포함되어 있습니다. 인터프리터를 Py_DEBUG로 빌드하면 테스트 사례는 참조 누수도 검사합니다.

다른 Python 변형으로 포팅하기

BList를 collections 모듈에 추가하면 다른 Python 변형은 다음 세 가지 방법 중 하나로 이를 지원할 수 있습니다.

blist를 list의 별칭으로 만듭니다. 점근적 성능은 그만큼 좋지 않지만 작동합니다.
순수 Python 참조 구현을 사용합니다. 작은 리스트에서의 성능은 그만큼 좋지 않지만 작동합니다.
참조 구현을 포팅합니다.

논의

이 제안은 Python-3000 메일링 리스트 [3]에서 간략히 논의되었습니다. 여러 사람이 이 제안을 지지했지만, 일부 반대 의견도 있었습니다. 아래에서는 해당 스레드의 게시자들이 관찰한 장단점을 요약합니다.

일반적인 의견:

장점: 대부분의 경우 배열 기반 리스트보다 성능이 뛰어납니다.
장점: “저는 이것의 변형을 … 몇 번 서로 다르게 구현했습니다.”
단점: 실제 애플리케이션에서의 유용성과 성능은 입증되지 않았습니다.

collections 모듈에 BList를 추가하는 것에 대한 의견:

장점: 리스트 API와 일치하므로 학습 곡선을 거의 0으로 줄입니다.
장점: 중급 사용자에게 유용하며 초보자의 사용을 방해하지 않습니다.
단점: 데이터 타입이 늘어나면 개발자가 선택하기가 더 어려워집니다.

배열 기반 리스트를 BList로 교체하는 것에 대한 의견:

단점: 확장 모듈에 미치는 영향(Backwards Compatibility에서 다룹니다)
단점: BList가 더 느린 사용 사례가 중요합니다(Use Case Trade-offs에서 이러한 문제를 해결할 방법을 확인하십시오).
단점: 배열 기반 리스트 코드는 단순하고 유지 관리하기 쉽습니다.

실제 애플리케이션에서의 도입 가치와 성능을 평가하기 위해 Raymond Hettinger는 BList를 확장 모듈로 릴리스할 것을 제안했습니다(현재 [1]에서 사용할 수 있습니다). 이것이 유용한 것으로 입증된다면 collections 모듈의 일부로 2.6에 포함할 유력한 후보가 될 것이라고 생각했습니다. 널리 인기를 얻는다면 배열 기반 리스트를 교체하는 방안을 고려할 수 있지만, 그렇지 않으면 고려하지 않을 것입니다.

Guido van Rossum은 데이터 타입의 증식에는 반대했지만, 하위 호환성 문제를 해결할 수 있고 BList의 성능이 전반적으로 더 뛰어나다면 배열 기반 리스트를 교체하는 것을 선호한다고 말했습니다.

진행 중인 작업

작은 리스트의 메모리 사용량 줄이기
BList에 TimSort를 구현하여 최선의 경우 정렬이 O(log n) 대신 O(n)이 되도록 합니다.
__reversed__ 구현
LIFO 연산이 O(n) 시간에 수행되도록 루트에 가장 오른쪽 리프를 가리키는 포인터를 캐시합니다.

참고 자료

Copyright

This document has been placed in the public domain.