RRB-트리: 효율적인 불변 벡터

Phil Bagwell Tiark Rompf

EPFL

{first.last}@epfl.ch

초록

불변 벡터는 함수형 프로그래밍을 위한 편리한 자료구조이며 Clojure와 Scala 같은 현대 언어의 표준 라이브러리의 일부이다. 일반적인 구현은 노드당 고정된 수의 자식을 갖는 폭이 넓은 트리를 기반으로 하며, 이를 통해 빠른 인덱스 조회와 갱신 연산이 가능하다. 이 논문에서는 벡터 자료형의 기반 자료구조를 새로운 구조인 Relaxed Radix Balanced Trees(RRB-트리)로 확장하고, 이 구조가 원래 벡터 자료구조의 인덱스, 갱신, 순회 속도를 유지하면서 불변 벡터의 연결, insert-at, 분할을

$O(logN )$

시간에 허용함을 보인다.

1. 서론

불변 자료구조는 멀티코어 환경에서 동시 처리의 몇 가지 문제를 관리하는 편리한 방법이다. 불변 연결 리스트는 수십 년 동안 함수형 프로그래밍에 잘 기여해 왔지만, 그 순차적인 성격 때문에 병렬 처리에는 적합하지 않다. Guy Steele은 유명한 ICFP’09 기조연설을 “Get rid of cons!”라는 말로 마무리했다. 병렬 처리를 위해 입력 데이터를 분해하고 계산된 결과를 효율적으로 다시 조립할 수 있도록, 효율적인 점근적 성질과 좋은 상수 계수를 갖는 새로운 자료구조가 필요하다. 가변 세계에서는 원소에 선형 시간이 아니라 상수 시간에 접근할 수 있고 같은 배열의 서로 분리된 부분을 병렬로 처리할 수 있기 때문에 배열이 리스트보다 더 선호되는 경우가 많다. 즉, 값의 인덱스 가능한 순서 시퀀스라는 의미에서 널리 쓰이는 가변 배열의 효율적인 불변 대응물을 만드는 일은 쉽지 않다. 순진한 불변 버전은 개별 원소 갱신에 허용할 수 없는 선형 비용이 들기 때문이다. 프로그래밍 언어 Clojure [4]가 개척한 불변 벡터 자료구조는 읽기와 쓰기 성능 사이에서 좋은 균형을 이루며, 흔히 사용되는 많은 프로그래밍 패턴을 효율적으로 지원한다. Clojure에서 불변 벡터는 언어 구현 설계의 핵심 요소이다. Ideal Hash Tries(HAMTs) [1]는 불변 해시 맵의 기반으로 사용되었고, 동일한 구조인 32-분기 트리가 불변 벡터에도 사용되었다. 그 결과 설계는 효율적인 순회와 단일 원소 추가를 상수 시간에, 인덱싱을 $log 32 N = 15 lgN$ 시간에, 갱신을 $32 5 lgN$ 시간에 제공한다. 트리 노드로 폭 32의 배열을 사용하면 자료구조가 캐시 친화적이 된다. 인덱스 기반 갱신은 단지

15

lgN번의 간접 메모리 접근만 발생시키므로, 실용적인 목적에서는 프로그래머가 모든 연산을 “사실상 상수 시간”으로 간주할 수 있다. 그러나 병렬 처리는 효율적인 벡터 연결, 분할, 그리고 주어진 인덱스에서의 삽입을 요구하며, 이는 이 구조로는 쉽게 지원되지 않는다. 이 논문에서 제시하는 작업은 기존 연산의 성능을 훼손하지 않으면서, 벡터의 기반 구조를 확장하여 연결과 삽입을 선형 시간이 아닌 O(logN )에 지원한다. 이 새로운 자료구조는 일반적인 종류의 comprehension을 더 효율적으로 병렬화할 수 있게 한다. 벡터는 병렬로 평가될 수 있는 여러 분할로 나뉠 수 있다. filter와 같은 많은 일반적 연산에서는 개별 분할 결과의 크기를 사전에 알 수 없다. 결과로 얻어진 하위 벡터들은 선형 복사 없이 연결되어 결과 벡터를 반환할 수 있다. 이렇게 하면 결과를 조립하는 과정에서 병렬 처리의 이점이 사라지지 않는다. 현재 작업은 프로그래밍 언어 Scala를 대상으로 했지만, 이 자료구조는 Clojure, C, C++ 등 다른 언어 환경에도 적용 가능하다. 다른 사용 사례로는 예를 들어 템플릿 기반 웹 페이지 생성을 용이하게 하는 문자 문자열 특화 구현이 있다. 이 논문의 나머지 부분에서는 Scala와 Clojure에서 사용되는 32-분기 자료구조를 가리켜 벡터라고 부르겠다.

1.1 관련 연구

이전 연구는 연결 문제에 대해 개선된 해법을 제공하는 불변 자료구조들을 제시했는데, 대표적으로 Ropes [3], 2-3 finger trees [5], B-Trees [2]가 있다. 그러나 각각에는 한계가 있다. 원래 문자열의 연결을 지원하기 위해 만들어진 자료구조인 Rope에서는, 두 부분 문자열을 가지로 갖는 이진 트리를 단순히 만드는 방식으로 목표를 달성한다. 노드에 두 문자열의 크기를 추가하면 연결 후에도 효율적인 인덱싱이 가능하다. 분할은 Rope 위에 상한과 하한 분할 경계값을 갖는 분할 노드를 생성함으로써 수행할 수 있다. 그러나 반복적인 연결과 분할이 수행될수록 성능은 저하된다. 인덱스 시간은

s + lg c

이며 여기서 c는 연결 횟수, s는 Rope 트리 경로를 따라 있는 분할 수이다. 최악의 경우 성능을 보존하려면 균형 조정이 필요하다. 복사 없이 분할을 하면, 더 이상 참조되지 않을 때도 원래 문자열의 제외된 부분을 수거할 수 없으므로 메모리 누수가 발생한다. 2-3 finger tree는 인덱싱과 갱신에 $lgN$ 시간을 달성하면서 동시에 벡터에 항목을 추가하는 데 대해 분할 상수 시간을 유지한다. 연결도 $lgN$ 시간에 수행할 수 있다. 매력적이긴 하지만, 이 자료구조를 벡터에 사용하면 인덱스에 대한 $15 lgN$ 시간이 손상되어 이론적으로 5배 느려진다. Okasaki의 책 [6]에서 논의된 자료구조들도 상수 계수 면에서 차이가 있다. 이 논문에서는 벡터 구조를 확장하면서 그 기본 성능 특성을 유지하고 효율적인 연결, 분할, 삽입을 허용하는 새로운 자료구조인 Relaxed Radix Balanced Trees(RRB-트리)를 소개한다.

12012/3/11

그림 1. 기본 벡터 구조: m-분기 트리(예시 m=4)

1.2 벡터

설명을 위해 모든 벡터 구조를 4-분기 트리 예시로 제시한다. 특별히 언급하지 않는 한, 원리는 불변 벡터에서 관심 대상인 32-분기 구조를 포함한 모든 m-분기 트리 구조에 적용된다. 그림 1은 이 관례를 사용한 기본 벡터 구조를 보여준다. 각 4-분기 배열을 32-분기 배열로 마음속에서 바꾸어 생각하면 32-분기 버전을 상상할 수 있다. Clojure의 불변 해시 맵을 개발하면서 수석 개발자 Rich Hickey는 Hash Array Mapped Tries(HAMT) [1]를 기반으로 사용했다. HAMT는 가변 해시 맵을 구현하기 위해 32-분기 구조를 사용한다. Clojure가 개척한 불변 버전은, 맵에 항목을 추가하거나 제거할 때 트리 경로만 다시 쓰면 된다는 이해를 바탕으로 만들어졌다. 이어서 동일한 32-분기 구조가 불변 벡터를 제공하는 데 사용되었다. 이 경우 항목의 ‘키’는 해시값이 아니라 벡터에서의 인덱스이다. 다시 말해, 불변성은 갱신과 추가를 위해 트리 경로만 복사하고 갱신함으로써 달성되며, 32-분기는 $15 lgN$ 인덱스 성능으로 이어진다. 벡터의 m-분기에서 m으로 32를 선택한 것은 이 구조의 서로 다른 사용 사례들 사이의 절충에서 비롯된다. 분기 계수를 늘리면 인덱스와 순회 성능은 향상되지만 갱신과 확장은 느려지는 경향이 있다. 원칙적으로 m이 증가하면 인덱싱 비용은 $log mN$에 비례하고 갱신 비용은 $m log mN$에 비례한다. 그러나 실제로는 현대 프로세서의 메모리 캐시 라인 크기인 64-128 bytes 때문에 이 정도 크기의 작은 블록을 복사하는 비용이 상대적으로 저렴하다. 그림 2에서 볼 수 있듯이 m = 32는 인덱스와 갱신 비용 사이의 좋은 균형을 나타내며, 특히 일반적인 사용 사례는 갱신보다 인덱싱과 순회를 훨씬 더 많이 사용한다. m을 2의 거듭제곱으로 선택하면 인덱스에서 분기값을 추출할 때 다소 더 비싼 나머지 연산 대신 시프트를 사용할 수 있다. 과거에는 중요한 고려사항이었지만, 오늘날 현대 컴퓨터 아키텍처에서는 이점이 미미하다. 그림 2는 m-분기 구조를 이진 트리 또는 2-3 finger tree와 비교했을 때의 장점을 보여준다. 32-분기 자료구조를 사용하면 인덱스 시간은 4배보다 조금 더 빠르고, 갱신 시간은 비슷하다. 이론적인 5배 이점은 상위 트리 노드의 캐싱 때문에 다소 희석된다.

1.3 연결

그림 3에는 두 개의 벡터가 보인다. 이것들을 하나의 벡터로 연결하는 순진한 접근은 “왼쪽 시프트”와 함께 오른쪽 벡터의 모든 노드를 연결된 벡터의 적절한 위치로 복사해야 하며, 이 과정은 오른쪽 벡터의 크기에 선형이다. 또는 오른쪽 벡터를 순회하면서 항목들을 왼쪽 벡터에 추가할 수도 있는데, 이 역시 선형 과정이다. 이 논문의 나머지 부분에서는 제안하는 RRB-트리 구조가 어떻게 효율적인 연결을 허용하는지 보일 것이다.

2. RRB-트리

RRB-트리는 고정 분기 계수 m을 완화함으로써 주어진 벡터 구조를 확장한다. 그렇게 할 때 트리 표현이 선형 연결 리스트로 퇴화하는 것을 방지하고 $lgN$ 트리 높이를 유지하는 것이 중요하다.

2.1 균형 트리

균형 트리 구조는 각 레벨에서 최대 및 최소 분기 계수 $mm$와 $ml$ 사이의 관계를 유지한다. 이들은 주어진 항목 수 $N$을 표현하는 데 필요한 최대 높이 $hm$와 최소 높이 $hl$를 각각 결정한다. 그러면 $hl = log mm N$ 이고 $hm = log ml N$

또는

$hl = 1$

lgm m

$lgN$ 이고 $hm = 1$

lg m l

$lgN$

이다.

더 잘 균형 잡힌 트리는 높이 비율 $hr$이 1, 즉 완전 균형에 더 가깝다.

$hr = lg m l$

$lg m m$

22012/3/11

그림 4. RRB 트리: 가장 왼쪽 슬롯 A가 누적 크기 테이블을 가리킨다.

$ml$이 $mm$에 가까울수록 트리는 더 완전하게 균형 잡힌다. B-트리의 경우 $ml = 12 mm$ 이므로

$hr = lg 12 mm$

$lg m m$

$hr = lg m m − 1$

$lg m m$

$hr = (1 − 1$

$lg m m$

$)$

이다.

$mm$가 커질수록 B-트리는 잘 알려진 특성대로 완전 균형에 가까워진다.

2.2 완화된 기수 검색

벡터의 경우 분기 계수 m은 항상 32이고 트리는 완전하게 균형 잡혀 있다. 상수 m 덕분에 기수 검색은 인덱싱 중 자식 노드를 직접 찾을 수 있다. 두 개의 이런 트리를 연결할 때, 복사의 선형 비용을 피하기 위해 이 제약을 완화해야 한다. 노드에는 m개보다 적은 항목 또는 하위 트리가 저장될 수 있다. 그러나 이는 더 이상 기수 검색을 단순한 방식으로 사용할 수 없음을 뜻한다. 기수 검색은 주어진 레벨에서 각 하위 트리가 정확히 $mh−1$ 개의 항목을 가진다고 기대한다는 사실에 의존한다. 따라서 인덱스 i는 그 노드의 하위 트리 $bi/ (mh−1)c$ 에서 발견된다. 관례적으로 인덱스와 노드 오프셋은 0 기반이다. 기대한 수보다 적은 항목이 있다면 다른 방법을 사용해야 하며, 이를 완화된 기수 검색이라고 부르겠다. B-트리에서는 부모 노드에 키 범위를 저장하고 선형 또는 이진 검색을 수행하여 필요한 키를 포함하는 하위 트리를 찾는다. RRB-트리에서도 비슷한 방식을 사용할 수 있지만, 키 대신 인덱스 범위를 부모 노드의 배열에 저장하며, m 슬롯 폭이 아닌 노드를 포함하는 하위 트리를 가진 노드에만 저장한다. 그림 4는 RRB 트리의 기본 구조를 보여준다. 트리 노드 A는 하위 트리 C, D, E를 가리키는 포인터 배열로 이루어져 있다. 이 배열과 연관된 범위 배열은 이 하위 트리들에 있는 리프 항목의 누적 총수를 포함한다. 편의를 위해 포인터와 그에 대응하는 범위를 슬롯이라고 부르겠다. 예시에서 슬롯 0은 노드 C를 가리키며 3개의 하위 트리를 포함한다고 말한다. 이 경우에는 그것들이 리프 항목이다. 인덱스 위치 3의 항목, 즉 노드 D의 첫 번째 항목을 가져오고 싶다고 하자. 인덱스를 4로 정수 나눗셈하면 슬롯 0이 선택된다. 그러나 그 슬롯에 저장된 범위값 3과 같거나 더 크므로 다음 슬롯 1을 검사해야 한다. 여기서는 인덱스가 범위보다 작으므로 인덱싱은 슬롯 1의 하위 트리 노드 D에서 계속된다. 그 전에 이전 슬롯 0의 범위 3을 인덱스에서 빼서, 계속되는 검색을 위한 새로운 0 기반 인덱스 0을 만든다. 그러면 노드 D의 위치 0에서 원하는 항목을 찾는다. 일반적으로 $ml$이 m에 가까우면 부모 노드에서의 기수 검색은 원하는 슬롯 근처에 떨어진다. 예를 들어 $ml = m − 1$ 이면 높이 2인 트리의 최악의 경우 항목 수는 $(m−1) 2$ 개뿐이다. m번째 슬롯을 인덱싱할 때 보통은 선택된 슬롯에서 하위 트리를 찾을 것으로 기대하지만, 어떤 경우에는 다음 슬롯도 검사해야 한다. 인덱싱 중 하위 트리를 따라가기 전에 어떤 하위 트리를 따라야 하는지 확인하기 위해 하위 트리 범위값을 검사해야 한다. 역추적은 필요 없다. 범위값은 실제로 그 슬롯과 그 왼쪽 슬롯들에 있는 리프의 실제 항목 수이다. 정확한 경로에 직접 인덱싱하는 대신 두 개의 가능한 범위값을 검사해야 할 수도 있다. 이 추가 검사는 현대 기계에서 상대적으로 저렴한데, 첫 번째 값을 읽으면 캐시 라인이 로드되고 인접한 다음 몇 개의 값도 동시에 캐시에 올라오기 때문이다. 짧은 선형 검색을 수행하는 오버헤드는 매우 작다. 더 나아가 가능한 모든 인덱스를 고려하고 노드가 무작위로 m 또는 $m − 1$ 이라면, 기수 검색이 $34$ 확률로 성공할 것으로 기대된다. 슬롯당 평균 항목 수는 $m − 12$ 이다. 첫 번째 슬롯부터 시작하면 해당 슬롯에서 항목을 찾지 못할 확률은 0.5

m

이다. 두 번째 슬롯은 1.0

m

, 세 번째는 1.5

m

, 이런 식으로 m번째 슬롯은 0.5mm 이다. 이 급수를 합하면 평균 실패 확률은 0.25이다.

2.3 캐시 라인 인식과 이진 검색

캐시 라인 로드가 짧은 선형 검색을 동반한 기수 검색에 이런 이점을 준다는 점을 이해하면, 노드에서 이진 검색이나 심지어 단순 선형 검색도 매력적일 수 있다고 기대할 수 있다. 최종적인 연결 알고리즘에서 이진 검색은 더 적은 제약을 요구하므로 바람직하다. 그러나 $m = 32$ 인 경우의 이진 검색은 여러 번의 캐시 미스를 유발할 수 있고, 그에 따른 캐시 라인 로드와 캐시 프리패칭을 쉽게 활용할 수 없다. 실험적 테스트는 완화된 기수 검색이 노드에서의 이진 검색이나 순수 선형 검색보다 전체 인덱싱 속도가 거의 3배 빠름을 보여준다(벤치마크 참조).

2.4 연결

그림 5는 두 RRB-트리의 연결을 보여준다. 단순화를 위해 다시 $m = 4$ 인 경우를 고려하지만, 같은 원리를 더 큰 값에도 적용할 수 있다. 과정은 왼쪽 트리의 오른쪽 가장자리 바닥과 오른쪽 트리의 왼쪽 가장자리 바닥에서 시작한다. B-트리는 노드 분기 크기를 m과 2m 사이로 제한함으로써 균형을 보장한다. 그러나 앞서 언급했듯이 B-트리 노드는 기수 검색을 쉽게 해주지 않는다. 대신 우리는 노드 크기가 m

과 $m − 1$ 사이에 있도록 허용하는 초기 불변식을 선택했다. 이는 잘 알려진 2-3 트리, 3-4 트리, 그리고 (m=32의 경우) 31-32 트리에서 시작하는 균형 트리 계열을 정의한다. 이 불변식은 균형을 보장하고 대부분의 경우 기수 분기 검색을 달성한다. 가끔은 올바른 분기를 찾기 위해 기수 검색 뒤에 몇 단계의 선형 검색이 필요하다. 필요한 추가 단계 수는 더 높은 레벨에서 증가한다. 트리의 최소 리프 항목 수는 $(m−1) h$ 이다. 최대 리프 항목 수는 $mh$ 이다. 최상위에서의 최악의 추가 단계 수는 최대값에서 최소값을 빼고 그 레벨의 슬롯 크기로 나눈 값이다.

$mh − (m − 1) h$

$m(h−1)$

또는 $m = 32$ 이고 $h = 5$ 일 때 4.69이다. 노드 크기가 $m − 1$ 과 m 사이에 무작위로 분포한다고 가정하면 기대되는 최악의 경우는 평균 2.49이다.

32012/3/11

그림 5. 벡터 연결, 3-4 트리 바닥 레벨

그림 6. 벡터 연결, 3-4 트리 첫 번째 레벨 그림 5는 3-4 트리를 이용한 연결/균형 조정 알고리즘을 보여준다. 다시 말해, 이 원리는 m=32를 포함한 전체 트리 계열에 적용된다. 먼저 왼쪽 트리의 오른쪽 가장자리와 오른쪽 트리의 왼쪽 가장자리를 따라 내려간다. 그런 다음 한 레벨 위로 올라간다. 올바른 형태의 트리를 얻기 위해서는 상자 안에 포함된 노드들을 불변식에 맞도록 재균형화해야 한다. 이를 위해 각 슬롯 수가 $m − 1$ 과 m 사이가 될 때까지 오른쪽에서 왼쪽으로 분기 항목을 복사해야 한다. 또한 순차적 순서를 유지해야 한다. 예시에서는 3번째 노드의 항목과 4번째 노드의 세 항목을 새로운 노드로 복사해야 하며, 이 노드는 이제 불변식을 만족한다. 그러나 일반적으로는 불변식을 만족할 때까지 여러 노드, 심지어 모든 노드를 복사해야 할 수도 있다. 최악의 경우 각 균형 조정마다 $m2$ 개의 노드를 복사해야 한다. 1개에서 m개 항목을 가진 슬롯을 m개의 슬롯에 재분배하여 불변식을 만족시키는 것은 항상 가능하다. 따라서 연결의 최악 비용은 $m2$

lgm

$lgN$ 또는 O(logN )에 비례한다. 이는 벡터의 값 하나를 단순한 불변 갱신으로 완료하는 비용의 상수 배이다. 결과 노드 중 앞의 네 개는 왼쪽 트리에 대한 새로운 오른쪽 노드를 형성하고, 나머지 두 노드는 다음 레벨로 올려서 그 레벨의 균형 조정에 포함시킨다. 이는 그림 6에 나타나 있다. 여기서 오른쪽의 두 노드는 결합되어 새로운 4-분기 노드를 이루고, 연결을 완료하기 위해 한 단계 위의 새로운 노드가 생성된다. 일반적으로 이 과정은 트리의 맨 위에 도달할 때까지 반복된다. 수정된 트리 가장자리 노드들만 다시 쓰인다는 점에 주목하라. 트리의 나머지 부분은 손대지 않으며 연결 결과는 새로운 불변 벡터가 된다.

2.5 두 레벨에 걸친 합산

더 자세히 살펴보면, 원하는 완화된 기수 검색을 직접 달성하면서 평균적으로 연결 비용을 약 3배 줄이는 덜 제약적인 접근이 가능함을 알 수 있다. 노드의 모든 슬롯을 고려할 때, 어떤 슬롯들이 총 $p$ 개의 하위 트리 분기를 포함한다면 최대 추가 선형 검색 단계 수 $e$ 는 $e = a − (b p−1$

m

$c + 1)$ 로 주어진다. 완전한 기수 검색을 위해서는 정확히 m개의 항목을 포함하는 슬롯이 $b p−1$

m

$c + 1$ 개만 필요하지만 실제로는 a개가 있다. 이제 이전과 똑같이 균형 조정 단계를 수행할 수 있지만, 개별 노드는 추가 검색 단계 $e$ 를 넘지 않는 한 어떤 수의 하위 트리도 가질 수 있다. $e = 1$ 인 이 제약을 사용한 균형 조정 예가 그림 7에 나와 있다. 아래쪽에는 균형 조정을 위해 고려할 6개의 노드가 있고 총 항목 수는 16이다. 이 경우

$e = 6 − b 16 −14 c − 1$ 또는 2이며, 허용된 기수 검색 오차보다 하나 더 많다. 따라서 균형 조정이 필요하다. 왼쪽부터 시작해서 m개의 항목을 가진 슬롯은 건너뛴다. 모든 노드가 이 크기라면 불변식은 자동으로 만족되고, 모든 노드가 m 크기이고 오른쪽 노드만 예외인 표준 벡터 연결의 전형적인 사용 사례로 되돌아간다. 첫 번째 작은 슬롯부터 시작해 오른쪽으로 진행하면서, 작은 슬롯부터의 모든 슬롯 합이 슬롯 수를 하나 줄이기에 충분해질 때까지 계속한다(타원으로 둘러싸인 부분). 그다음 진행하면서 슬롯을 복사해 노드 수를 줄인다. 이 레벨의 노드는 어차피 복사될 것이므로, 이 경우 총합이 m 또는 4가 되도록 충분한 슬롯을 복사해 넣는 기회를 활용한다. 가능한 총 슬롯 수는 $2m$, 즉 왼쪽에서 m, 오른쪽에서 m이므로, 이렇게 하면 오른쪽에 남아 위로 올릴 슬롯이 m개를 넘지 않게 되고, 그 노드는 보통 다음 레벨 재균형화에서 건너뛰어지므로 추가 작업이 없다. 이제 나머지를 다음 레벨로 올리고 같은 작업을 반복한다. 그림 8에서는 왼쪽 트리의 오른쪽 첫 번째 레벨 노드가 슬롯을 두 개만 가진다. 여기서는 고려할 노드가 4개이고 총 하위 노드 수는 11개이다. 이 경우 $e = 4 − b 11 −14 c − 1$ 또는 1이다. 균형 조정이 필요 없으므로 맨 위의 4-슬롯 노드를 구성하면 연결이 완료된다. 일반적으로 $m − e$

2

개 이상 항목을 가진 슬롯을 건너뛰는 것이 타당함을 보일 수 있다. 가장 작은 슬롯에 도달하면 언제나 오른쪽에서 복사해 와서 e를 올바른 값으로 줄일 만큼 충분한 노드가 있다. 작은 슬롯이 n번째이고 직접 기수 검색을 위한 슬롯 수가 위에서 설명한 총 하위 노드 수로부터 계산된 r이라고 하자. 그러면 최종 개수는 $r + e$ 이다. n번째 슬롯 왼쪽의 각 노드는 $m − e$

2

와 m 사이이므로 건너뛰어진다. 균형 조정할 슬롯 수는 최대 $2m$ 개이다. 따라서 작은 슬롯이 $2m$ 번째라고 하더라도 그 왼쪽의 최소 총 하위 노드/항목 수는

$2m(m− e$

2

$)$ 또는 $2m2 −em$ 이다. 그러나 직접 기수 검색을 위해 필요한 슬롯 수는 $2m−e$ 이므로, 총 하위 노드/항목 수는 $m(2 m − e)$ 또는 $2m2 − em$ 이어야 한다. 이는 작은 슬롯이 $2m$ 번째 위치에 있도록 허용하는 데 필요한 수와 같다. 실제 구현에서는 복사 작업을 줄이기 위해 먼저 모든 새 노드 크기를 계산한다. 실제 복사는 한 번만 수행된다. 지금까지는 최대 오차 e가 1이라고 가정했지만 더 큰 값도 사용할 수 있다. 허용되는 기수 검색 오차가 커질수록 값을 인덱싱하는 시간은 증가하고 연결 비용은 감소한다. $m = 32$ 인 경우 실험적 테스트는 $e = 2$

가 좋은 절충임을 보여주며, 인덱스 시간에는 작은 영향만 주면서도

42012/3/11

그림 7. 두 레벨 합산, 3-4 트리 바닥 레벨

그림 8. 두 레벨 합산, 3-4 트리 첫 번째 레벨 낮은 연결 비용을 유지한다. 결과 트리는 평균적으로 $ml + 2 = m = 32$ 이므로 완전 균형에 매우 가깝다. 깊이의 미세한 증가는 인덱스 시간 증가에 기여한다. 현재의 균형 조정 전략에서는 가장 작은 슬롯이 가장 왼쪽에 있고 그 오른쪽은 마지막 두 개를 제외하고 모두 m인 최악의 경우가 생길 수 있다. 이 경우 균형 조정은 모든 $2m$ 슬롯을 재배치하게 하여 최악의 복사 비용이 $2m(m − e)$ 가 되는데, 여전히 상수이다. 위에서 설명한 재배치 과정은 우리가 원하는 성능 특성을 제공한다고 판단한 휴리스틱이다. 방금 설명한 최악의 경우는 어느 작은 슬롯에서 시작하는 것이 가장 저렴한지를 먼저 확인함으로써 쉽게 피할 수 있다. 전역적으로 최적의 재배치를 달성하려는 동적 계획법 기반 알고리즘 같은 대안도 사용할 수 있지만, 선택한 알고리즘은 실제로 좋은 성능을 보인다.

3. 벤치마크 결과

우리는 여러 경험적 설정에서 RRB-트리의 성능을 평가한다. 가장 중요한 두 속성은 연결이 인덱싱 성능에 미치는 영향과 RRB-트리를 연결하는 데 필요한 시간이다.

표 1. 인덱스 시간 비교 나노초 n 2n RegV RRB RRB RRB RRB Bin Srch

p = 1 p = 0 .25 p = 0 .17 p = 0 .12 p = 0 p = 0

10 1024 23 45 46 45 46 93 11 2048 28 45 43 46 47 98 12 4096 28 44 82 47 47 116 13 8192 41 39 45 50 48 118 14 16384 27 50 46 46 66 130 15 32768 27 53 56 57 64 155 16 65536 31 53 57 62 66 161 17 131072 35 53 59 58 66 175 18 262144 33 58 60 61 66 189 19 524288 34 66 59 61 67 200 20 1048576 34 63 64 71 80 225 21 2097152 38 63 62 74 82 230 22 4194304 38 61 69 69 82 243 23 8388608 37 59 54 66 82 258 Average 32 54 57 58 65 171

Factor 1.00 1.66 1.77 1.79 2.00 5.27 3.1 인덱스 성능 벤치마크

표 1은 서로 다른 크기의 벡터와 서로 다른 정도의 연결을 거친 벡터를 인덱싱할 때의 인덱스당 비용 벤치마크를 보여준다. 연결할 두 테스트 벡터의 크기는 무작위로 선택된다. 그리고 각 벡터는 일반 벡터를 만들거나, 크기를 무작위로 두 부분 크기로 나눈 뒤 같은 분할을 반복하는 방식으로 생성된다. 크기를 다시 분할할지 여부는 각 벤치마크에 대해 설정된 확률 $p$ 에 따라 무작위로 선택된다. 결과는 $p = 1$, 0.25, 0.17, 0.125

및 0에 대해 제시된다. 확률 $p$ 가 선택되면, 더 이상 크기 세분화를 하지 않고 일반 벡터를 생성할 확률이 $p$ 이다. 두 하위 벡터가 생성되면 그것들을 연결한다. 이 연결 과정은 다음 레벨에서 계속되어, 결국 처음 요구된 크기의 벡터가 최종적으로 구성된다. 이런 방식으로 일반 벡터인 $p = 1$, 많은 작은 무작위 벡터를 연결한 결과인 $p = 0$, 또는 그 중간 어디쯤에 해당하는 벡터들이 생성된다. 많은 시행을 수행하고 각 벡터 크기 범위에서 결과를 평균냈다. 요약 성능 계수는 일반 벡터를 기준으로 했을 때 RRB-트리 구조 사용 비용에 대한 지침을 제공한다. 갱신과 순회는 속도 손실이 무시할 만하다는 점을 언급할 가치가 있다. 두 경우 모두 범위 정보는 갱신할 필요가 없고, 순회는 일반 벡터와 동일하게 분기 참조만 따라가기 때문이다. 마지막 열은 완화된 기수 검색 대신 노드 분기에서 이진 검색을 사용한, 거의 일반 벡터 부분이 없는 RRB-트리의 인덱스 시간을 보여준다. 이 인덱스 시간은 일반 벡터보다 5배 이상 길고, 기수 검색을 사용하는 경우보다도 거의 3배 길다.

3.2 연결 비용

테스트 벡터는 인덱스 테스트와 같은 방식으로 생성되었고, 최종 연결 동안 복사된 총 메모리 위치 수를 기록했다. 여기에는 트리 노드, 리프 항목, 범위 배열, 그리고 연결 및 균형 조정 과정 중 생성된 임시 크기 배열이 포함된다. 결과는 표 2에서 볼 수 있다. 이는 단순 값 갱신을 완료하는 비용인 $32 5 lg N$ 또는 5레벨 트리의 경우 160과 비교할 수 있다.

52012/3/11

표 2. RRB-트리 연결의 복사 비용 n 2n RegV RRB RRB RRB RRB

p = 1 p = 0 .25 p = 0 .17 p = 0 .12 p = 0

10 1024 76 272 273 307 307 11 2048 152 484 534 531 572 12 4096 160 225 260 220 240 13 8192 173 319 318 393 489 14 16384 194 508 556 547 757 15 32768 226 786 871 808 1009 16 65536 315 1164 1149 1145 1304 17 131072 313 619 567 648 795 18 262144 325 570 793 616 887 19 524288 326 808 871 1006 1191 20 1048576 371 1114 1149 1345 1410 21 2097152 456 1417 1687 1617 1674 22 4194304 464 755 923 1106 1183 23 8388608 473 871 938 1100 1631

a)비용에는 모든 원소 복사 - 항목, 하위 트리 참조, 크기 정보가 포함됨

3.3 관찰

크기가 경계값 10, 15, 20을 지날 때 인덱스 속도와 연결 비용이 추가된 트리 레벨을 반영한다는 점에 주목하라.

4. 분할과 Insert At

분할 연산은 벡터에서 왼쪽과 오른쪽 슬라이스를 제거한 결과로 이해하는 것이 더 쉽다. 오른쪽 슬라이스는 오른쪽 슬라이스 인덱스로 정의된 가장자리를 따라 내려가서 그것을 트리의 오른쪽 가장자리로 만들면 간단히 수행된다. 인덱스 오른쪽의 노드들은, 트리의 새로운 오른쪽 가장자리를 만들기 위해 인덱스상의 노드들을 복사할 때 단순히 버려진다. 마찬가지로 왼쪽 슬라이스는 왼쪽 슬라이스 인덱스로 정의된 가장자리를 따라 내려가서 그것을 왼쪽 가장자리로 만듦으로써 수행된다. 인덱스 왼쪽의 노드들은 버려지고, 왼쪽 가장자리를 만들기 위해 복사할 때 오른쪽의 노드들은 왼쪽으로 시프트된다. 이렇게 만들어진 트리는 위에서 설명한 불변식을 만족하지 않을 수 있다. 주어진 레벨에 대해 e보다 하나 더 많은 추가 슬롯이 있을 수 있다. 그러나 이후의 연결은 불변식을 복원할 것이다. 이런 지연된 접근을 취함으로써 중복되는 균형 조정을 피할 수 있다. 분할의 비용은 갱신과 동일하며, 즉 $mlg m lgN$ 이다.

5. 구현 고려사항

원래 Scala와 Clojure의 Vector 구현은 32-분기 배열을 담은 내부 노드를 사용한다. 이 구현에서는 노드가 RRB 트리 노드로 변환될 때 배열 크기를 하나 늘린다. 0번째 원소는 범위값을 담은 배열에 대한 참조를 담는다. 연결되지 않은 벡터에는 오버헤드가 없다. 또한 범위/포인터 객체가 아니라 별도의 범위 배열을 사용함으로써 흔한 사용 사례인 순회의 속도는 영향을 받지 않는다. 연결 후 일부 노드에서는 0번째 원소가 범위값 배열을 가리키게 된다. 이 추가 원소는 내부 노드에만 존재하므로 추가 메모리 오버헤드는 대략 $m2$ 분의 1, 즉 1024분의 1에 가깝고 무시할 수 있다고 볼 수 있다. 연결 후의 전형적인 벡터는 표준 32-분기 하위 트리를 가진 노드와 범위값을 가진 RRB-트리 노드가 섞여 있게 된다. JVM 구현에서는 객체 타입을 사용하여 최적화된 표준 벡터 인덱스 방법을 사용할지, 더 느린 RRB 트리 인덱스 방법을 사용할지 결정할 수 있다. 연결과 슬라이스 기능을 사용하지 않을 때는 표준 벡터에서 속도 손실이나 메모리 오버헤드가 없다.

5.1 상수 시간 추가

Clojure 벡터 구현에는 단일 원소의 상수 시간 append를 허용하는 최적화가 포함되어 있다. 마지막 폭 32의 원소 블록은 트리 구조 밖에 유지되므로 여러 트리 레벨을 거치지 않고 상수 시간에 접근할 수 있다. Clojure Vector의 오른쪽 끝에 원소를 추가하려면 이 최대 폭 32 배열만 복사하면 된다. 이 모델은 여러 레벨과 다양한 위치로 확장할 수 있다. Scala 표준 라이브러리 구현에서 벡터는 focus라는 개념을 갖는데, 이는 상수 시간에 접근 가능한 하나의 폭 32 블록을 식별한다. 왼쪽 끝, 오른쪽 끝, 또는 다른 어느 위치에서든 모든 갱신 연산은 대상 블록을 focus 상태로 만든다. ‘focus 상태’의 블록에 대한 갱신은 그 특정한 폭 32 블록만 복사한다. 더 나아가 루트에서 focus 상태의 블록까지의 모든 트리 노드는 display, 즉 상수 시간 스택에 유지된다. focus를 인접한 32-블록으로 이동시키는 것은 display를 통한 한 번의 간접 참조만 필요로 하며, 경우에 따라 한 레벨 위 노드를 복사할 수도 있다. 인덱스 기반 읽기도 간접 참조 수를 최소화하기 위해 display를 사용한다. 어떤 위치를 focus 상태로 만들 때 아래쪽 포인터들은 null 항목으로 대체된다. focus가 그 블록 안에 머무는 한 맨 아래 배열만 복사하면 된다. focus가 인접 블록으로 이동하면 display 슬롯 1을 복사해야 하며, 이전 focus 위치에는 포인터를 다시 넣고 새로 focus된 위치는 null로 만든다. 이 모델 뒤의 설계 결정은 공간-시간적 접근 지역성을 최적화하는 것이다. 임의의 위치에서 시작해 벡터의 일부를 순차적으로 다시 쓰는 것이 흔한 연산이라는 가정이며, 마지막 갱신 근처의 원소를 읽는 경우도 마찬가지이다.

6. 결론

RRB-트리 기반 벡터는 Clojure와 Scala에서 사용되는 기존의 32-분기 불변 벡터를 실현 가능하게 확장하여, 다른 연산에 수반되는 기본 비용을 유지하면서 $O(logN )$ 연결과 분할을 제공한다. 실용적인 목적에서는 이들을 상수 시간으로 간주할 수 있다. 이 자료구조는 어떤 언어를 사용하든 문자열 구현의 기반이나 메모리 내 데이터베이스 구조의 기반으로도 매력적일 수 있다. 벡터를 분할하고 다시 연결할 수 있는 능력은 전형적인 병렬 comprehension을 수행할 때 매우 바람직하다. 현재의 노드 재배치 휴리스틱은 매우 만족스러운 결과를 내지만, 추가 연구를 통해 특정 사용 사례를 더 잘 최적화하는 대안 알고리즘을 검토할 수 있다.

참고문헌