이진 탐색 트리: O(log n) 및 캐시 성능

실전 이진 탐색 트리: O(log n)이 항상 빠르지 않은 이유

이론 컴퓨터 과학 분야에서 이진 탐색 트리(BST)와 레드-블랙 트리와 같은 자가 균형 변형은 동적 데이터 구조에서 효율성의 표준으로 여겨집니다. 삽입, 검색, 삭제 작업에 대한 O(log n)의 점근적 복잡도는 이상적으로 보입니다. 그러나 현대 프로세서 아키텍처의 다단계 캐시 메모리 환경에서는 BST의 성능이 이론적으로 유사한 복잡도를 가진 더 단순한 구조보다 현저히 떨어질 수 있습니다. 이 글에서는 이러한 불일치의 원인을 탐구하고 데이터 구조 선택에 대한 실용적인 권장 사항을 제시합니다.

예상치 못한 컴파일러 성능 저하

다음과 같은 시나리오를 상상해 보십시오. 컴파일러가 시간의 60%를 파싱이나 코드 생성에 쓰는 것이 아니라, 테이블에서 심볼을 조회하는 데 사용합니다. 수천 개의 심볼을 가진 임베디드 시스템에서는 이는 용납할 수 없는 일입니다. 변수 이름, 함수, 타입을 저장하는 심볼 테이블은 고전적인 자가 균형 BST인 레드-블랙 트리로 구현되었습니다. 이론적으로 O(log n)은 높은 속도를 보장했어야 합니다.

그러나 perf 프로파일러는 우려스러운 상황을 드러냈습니다:

$ perf stat -e cache-misses,instructions ./compiler test.c
  Performance counter stats:
    2,847,234 cache-misses
    8,500,000 instructions

850만 명령어에 거의 280만 캐시 미스 — 이는 세 개의 명령어당 하나의 캐시 미스입니다. 이러한 지표는 심각한 메모리 접근 문제를 지적합니다. 실험으로 레드-블랙 트리를 이진 탐색을 사용하는 정렬된 배열로 교체했는데, 이 역시 이론적 복잡도는 O(log n)입니다. 결과는 놀라웠습니다: 컴파일러 속도가 3배 빨라졌습니다.

동일한 점근적 복잡도를 가진 두 데이터 구조가 어떻게 이렇게 엄청나게 다른 성능을 보일 수 있을까요? 그 답은 캐시 메모리 작동 방식의 특수성에 있습니다.

원인 분석: 캐시 메모리와 미스

perf를 사용한 상세 분석은 의심을 확증했습니다. 레드-블랙 트리와 정렬된 배열을 비교한 결과 캐시 동작에서 결정적인 차이가 드러났습니다:

# Red-Black Tree Version
$ perf stat -e cache-references,cache-misses,cycles ./compiler_rbtree test.c
  Performance counter stats:
    3,247,832  cache-references
    2,847,234  cache-misses  (87.7% miss rate)
   24,000,000  cycles

# Sorted Array Version
$ perf stat -e cache-references,cache-misses,cycles ./compiler_array test.c
  Performance counter stats:
    1,123,456  cache-references
      234,567  cache-misses  (20.9% miss rate)
    8,000,000  cycles

레드-블랙 트리는 87.7%의 캐시 미스율을 보인 반면, 정렬된 배열은 단 20.9%를 기록했습니다. RISC-V 시스템에서 각 캐시 미스는 최대 100 CPU 사이클의 비용이 발생할 수 있습니다. 이는 레드-블랙 트리가 계산을 수행하기보다는 대부분 유휴 상태로 주 메모리에서 데이터를 기다리는 데 시간을 보냈다는 것을 의미합니다.

이론 대 실제: 포인터 추적 문제

데이터 구조 교과서는 다양한 작업에서 균형 잡힌 성능을 제공하는 BST를 강조합니다. 이들은 삽입, 검색, 삭제에 대해 O(log n)을 보장하며, 요소를 정렬된 순서로 유지합니다. AVL 트리나 레드-블랙 트리와 같은 균형 잡힌 변형은 최악의 경우 O(n)으로 성능이 저하되는 것을 방지하여 로그 높이를 보장합니다.

그러나 이러한 이론적 장점은 현대 컴퓨터의 메모리 계층 구조를 고려하지 않습니다. BST의 핵심 문제는 포인터 추적에 있습니다. 노드에서 자식(왼쪽 또는 오른쪽)으로의 각 순회는 임의의 메모리 주소에 있는 포인터를 따라가는 것을 포함합니다. 이는 캐시 활용 효율성을 크게 떨어뜨립니다.

정렬된 배열: 데이터 지역성

정렬된 배열을 사용할 때 요소는 메모리에 연속적으로 저장됩니다. 예를 들어:

Memory: [10][20][30][40][50][60][70][80]
          ↑   ↑   ↑   ↑   ↑   ↑   ↑   ↑
       0x1000 ...연속적이며 캐시 친화적...

프로세서가 array[4]에 접근할 때, 예를 들어 64바이트의 메모리 블록을 캐시 라인으로 로드합니다. 이 블록에는 array[4]와 여러 인접 요소(예: array[5], array[6])가 포함됩니다. 이 인접 요소에 대한 후속 접근은 캐시 히트가 되어 단 1 CPU 사이클만 소요됩니다.

이진 탐색 트리: 데이터 분산

BST에서 각 노드는 일반적으로 동적으로 할당(예: malloc())되며 힙의 임의의 위치에 있을 수 있습니다. 이는 메모리 단편화로 이어집니다:

       40 (@ 0x5000)
      /  \
    20    60 (@ 0x2000, @ 0x8000)
   /  \   /  \
  10  30 50  70 (@ 0x1000, @ 0x3000, @ 0x6000, @ 0x9000)

BST에서 검색할 때, 각 포인터 순회는 현재 캐시 라인 내에 없는 완전히 새로운 메모리 영역에 접근해야 할 가능성이 높습니다. 이는 캐시 미스를 초래하며, 주 메모리에서 데이터가 로드될 때까지 수백 CPU 사이클의 지연 시간을 발생시킵니다.

값 70을 검색하는 경우를 고려해 봅시다:

정렬된 배열 (이진 탐색):

* 1단계: 중간 요소 [40] @ 0x1020에 접근. 캐시 미스 (100 사이클). [30][40][50][60]을 포함하는 캐시 라인이 로드됩니다.

* 2단계: [60] @ 0x1030에 접근. 캐시 히트 (1 사이클).

* 3단계: [70] @ 0x1038에 접근. 캐시 히트 (1 사이클).

* 총: 약 102 사이클, 1 캐시 미스.

이진 탐색 트리:

* 1단계: 루트 [40] @ 0x5000에 접근. 캐시 미스 (100 사이클). 0x5000에 있는 캐시 라인이 로드됩니다.

* 2단계: 오른쪽으로 순회하여 [60] @ 0x8000에 접근. 캐시 미스 (100 사이클). 다른 캐시 라인에 있는 주소입니다.

* 3단계: 오른쪽으로 순회하여 [70] @ 0x9000에 접근. 캐시 미스 (100 사이클). 또 다른 새로운 주소입니다.

* 총: 약 300 사이클, 3 캐시 미스.

두 알고리즘 모두 동일한 수의 논리적 비교를 수행하지만, 캐시 미스로 인해 BST는 현저히 느립니다.

성능 및 코드 비교

설명을 위해 검색 코드 예제와 벤치마크 결과를 제공합니다.

BST 검색:

// 이진 탐색 트리 노드
typedef struct bst_node {
    int key;
    void *value;
    struct bst_node *left;
    struct bst_node *right;
} bst_node_t;

void* bst_search(bst_node_t *root, int key) {
    while (root) {
        if (key == root->key) return root->value;
        root = (key < root->key) ? root->left : root->right;
    }
    return NULL;
}

정렬된 배열 검색:

typedef struct {
    int key;
    void *value;
} array_entry_t;

void* array_search(array_entry_t *arr, int n, int key) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid].key == key) return arr[mid].value;
        if (key < arr[mid].key) right = mid - 1;
        else left = mid + 1;
    }
    return NULL;
}

다양한 크기의 데이터셋에서 10,000개의 무작위 검색 작업을 테스트한 결과:

데이터셋: 1000개 요소

* BST: 검색 작업당 2400 사이클

* 정렬된 배열: 검색 작업당 800 사이클

* 속도 향상: 3배

데이터셋: 10000개 요소

* BST: 검색 작업당 3200 사이클

* 정렬된 배열: 검색 작업당 1100 사이클

* 속도 향상: 2.9배

perf 캐시 미스 통계:

BST: 검색 작업당 8.5 미스
정렬된 배열: 검색 작업당 2.1 미스

정렬된 배열은 일관되게 3배 더 나은 성능을 보여줍니다. 그 이유는 다음과 같습니다:

연속적인 메모리 배치: 배열 요소는 연속적인 블록에 저장되어 캐시에 이상적입니다.
효율적인 캐시 라인 활용: 각 미스 발생 시 전체 캐시 라인(예: 64바이트)이 로드되며, 한 번에 여러 배열 요소를 포함하여 향후 미스를 최소화합니다.
하드웨어 프리페칭: 현대 프로세서에는 순차적 접근 패턴을 인식하고 데이터를 캐시로 선제적으로 로드하여 지연 시간을 더욱 줄이는 하드웨어 프리페처가 있습니다.

BST는 이러한 장점이 없습니다. 검색 중 각 포인터 역참조는 새로운 캐시 미스로 이어질 수 있습니다.

메모리 오버헤드 및 균형 트리

캐시 문제 외에도 BST는 포인터 저장으로 인해 더 큰 메모리 오버헤드를 가집니다.

BST 노드 (64비트 시스템, 정렬 포함):

```c

struct bst_node {

int key; // 4 바이트

void *value; // 8 바이트

struct bst_node *left; // 8 바이트

struct bst_node *right; // 8 바이트

// 패딩: 4 바이트

};

// 총: 요소당 32 바이트

```

정렬된 배열 요소 (정렬 포함):

```c

struct array_entry {

int key; // 4 바이트

void *value; // 8 바이트

// 패딩: 4 바이트 (정렬을 위해)

};

// 총: 요소당 16 바이트

```

1000개 요소의 경우 BST는 32KB를 필요로 하는 반면, 배열은 16KB를 필요로 합니다. BST의 증가된 메모리 사용량은 캐시에 들어갈 수 있는 노드의 수가 적다는 것을 의미하며, 이는 캐시 미스 문제를 악화시킵니다.

많은 개발자들은 균형 트리(예: 레드-블랙 또는 AVL)가 모든 BST 문제를 해결한다고 믿습니다. 이들은 실제로 로그 트리 높이를 보장하여 불리한 입력 데이터로 인한 연결 리스트로의 성능 저하를 방지합니다. 균형 유지를 위해 사용되는 노드 회전은 저비용 포인터 업데이트 작업입니다. 그러나 이러한 메커니즘은 근본적인 캐시 문제를 해결하지 못합니다: 노드들은 여전히 메모리 전체에 흩어져 있습니다.

컴파일러의 레드-블랙 트리에서 캐시 미스는 거의 모든 단계에서 발생했습니다:

$ perf stat -e cache-misses,L1-dcache-load-misses ./compiler_rbtree test.c
  Performance counter stats:
    2,847,234 cache-misses
    2,654,123 L1-dcache-load-misses

균형 트리는 알고리즘적 최악의 경우 문제를 해결하지만, 메모리 계층 구조와 관련된 하드웨어적 한계를 해결하지는 못합니다.

이진 탐색 트리는 언제 사용해야 할까요?

앞서 설명한 단점에도 불구하고 BST가 쓸모없는 것은 아닙니다. BST의 사용이 정당하고 심지어 더 선호될 수 있는 시나리오가 있습니다.

BST의 주요 장점은 잦은 삽입 및 삭제 작업이 있는 상황에서 나타납니다. 정렬된 배열에서는 이러한 작업이 많은 수의 요소를 이동해야 하므로 O(n)의 복잡도를 가집니다:

정렬된 배열에 삽입: O(n)
정렬된 배열에서 삭제: O(n)

BST의 경우 삽입 및 삭제는 O(log n) 작업으로 유지되며, 이는 몇 개의 포인터를 업데이트하고 균형 유지를 위해 몇 번의 회전만 필요하기 때문입니다. 1000개의 무작위 삽입/삭제 작업을 벤치마크한 결과:

정렬된 배열: 작업당 12000 사이클 (이동으로 인해)
레드-블랙 트리: 작업당 3500 사이클
BST 속도 향상: 3.4배

따라서 데이터 구조가 지속적으로 변화하고(많은 삽입 및 삭제) 검색 작업의 빈도가 지배적이지 않다면, 잠재적인 캐시 문제에도 불구하고 BST(특히 균형 잡힌 트리)가 더 나은 선택이 될 수 있습니다. 그렇지 않고 검색 작업이 주로 이루어지는 정적 또는 거의 수정되지 않는 데이터셋의 경우, 정렬된 배열 또는 다른 캐시 최적화된 구조(예: B-트리)가 종종 우월한 성능을 보여줍니다.