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를 소개합니다. BList는 작은 리스트에서 기존 배열 기반 구현과 똑같이 좋은 성능을 보이면서도, 대부분의 연산에서 더 우수한 점근적 성능을 제공합니다. 이 PEP는 BList 타입을 Python에 포함하기 위한, 서로 배타적인 두 가지 제안을 합니다:

collections 모듈에 추가하거나,
기존 list 타입을 대체합니다

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

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

이 PEP에서 제안하는 BList 타입은 배열과 트리의 특성을 모두 갖춘 B+트리의 원리에 기반합니다. 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개의 자식만 가지므로, 메모리 사용량은 최선의 경우의 배열 구현의 약 두 배가 됩니다. 리프 노드의 수가 리프가 아닌 노드의 수보다 최소 63배 많으므로, 리프가 아닌 노드가 사용하는 추가 메모리는 무시할 수 있는 수준입니다.

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

요약하면, 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를 사용하지 않고 문서화되지 않은 리스트 구조를 직접 사용하는 소수의 확장 모듈은 동작하지 않게 됩니다. 코어 코드 자체는 접근자 매크로를 상당히 일관되게 사용하므로 쉽게 이식할 수 있을 것입니다.
기존 list 타입은 폐기 예정으로 지정하되, 계속 포함합니다. 새 BList 타입을 사용하려는 확장 모듈은 명시적으로 그렇게 해야 합니다. BList C 인터페이스를 기존 PyList 인터페이스에 맞게 변경할 수 있으므로, 모듈 작성자의 99%는 단순한 찾아 바꾸기만으로 충분할 것입니다.
기존 모듈은 변경 없이 계속 컴파일되고 동작하겠지만, BList로 이전하려면 의도적인(그러나 작은) 노력이 필요할 것입니다.

이 접근 방식의 단점은 BList를 사용하는 모듈과 배열 기반 리스트를 사용하는 모듈을 섞어 쓸 때 변환이 자주 필요하면 속도가 느려질 수 있다는 것입니다.

참조 구현

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

소스 패키지에는 순수 Python 구현도 포함되어 있으며, 이는 원래 CPython 버전의 프로토타입으로 개발된 것입니다. 당연히 순수 Python 버전은 상당히 느리며, 리스트가 꽤 커지기 전까지는 점근적 개선의 이점이 드러나지 않습니다.

Py_DEBUG로 컴파일하면, C 구현은 대부분의 함수에 진입하고 빠져나올 때 BList 불변 조건을 검사합니다.

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

다른 Python 변형으로의 이식

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

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

논의

이 제안은 Python-3000 메일링 리스트 [3]에서 간략하게 논의되었습니다. 여러 사람이 이 제안을 지지했지만, 몇 가지 반대 의견도 있었습니다. 아래는 스레드에 글을 올린 사람들이 제시한 장단점을 요약한 것입니다.

일반적인 의견:

장점: 대부분의 경우 배열 기반 리스트보다 성능이 뛰어날 것입니다
장점: “이것의 변형을 … 몇 차례 구현해 본 적이 있습니다”
단점: 실제 애플리케이션에서의 필요성과 성능이 입증되지 않았습니다

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

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

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

단점: 확장 모듈에 미치는 영향(Backwards Compatibility에서 다룹니다)
단점: BList가 더 느린 사용 사례가 중요합니다(이를 어떻게 해결할 수 있는지는 Use Case Trade-offs를 참고하십시오).
단점: 배열 기반 리스트 코드는 단순하고 유지 보수하기 쉽습니다

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

Guido van Rossum은 데이터 타입이 난립하는 것에는 반대하지만, 하위 호환성 문제를 해결할 수 있고 BList의 성능이 모든 면에서 더 낫다면 배열 기반 리스트를 대체하는 데 찬성한다고 언급했습니다.

진행 중인 작업

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

참고 문헌

Copyright

This document has been placed in the public domain.