O(1) vs O(log n) 격차: 데이터 구조에서의 캐시

## 왜 O(1) 알고리즘이 O(log n)에 밀리는가: 캐시와 실제 성능

RISC-V SoC용 부트로더 개발 중에 문제가 발생했습니다: 500개 요소 테이블에서 장치 설정을 검색하는 데 시간이 너무 오래 걸렸습니다. 평균 O(1) 복잡도의 해시 테이블은 부팅 시간이 100ms를 넘게 소요되며, 이는 3자릿수만큼 나빴습니다. 정렬된 배열에서의 이진 탐색 O(log n)으로 전환하니 40% 빨라졌습니다.

perf로 프로파일링한 결과 캐시 동작 차이가 드러났습니다:

# Hash table
$ perf stat -e cache-references,cache-misses ./bootloader_hash
  1,247,832 cache-references
    892,441 cache-misses (71.5% miss rate)

# Binary search
$ perf stat -e cache-references,cache-misses ./bootloader_binsearch
    423,156 cache-references
     89,234 cache-misses (21.1% miss rate)

해시 테이블의 캐시 미스는 71.5%에 달해 각 미스가 ~100 사이클을 소모했습니다. 이진 탐색은 더 나은 접근 지역성 덕분에 미스를 21.1%로 줄였습니다.

Array vs Linked List: An Experiment

10만 개 정수를 합산하는 작업에서 둘 다 O(n)이지만 엄청난 차이가 나타났습니다:

Array: 70,147 ns (17,557,410 cycles)
Linked list: 179,169 ns (44,740,656 cycles)
Array is 2.55x faster

배열 코드는 순차 접근을 사용합니다:

int array[100000];
for (int i = 0; i < 100000; i++) {
    array[i] = i;
}
long long sum = 0;
for (int i = 0; i < 100000; i++) {
    sum += array[i];
}

연결 리스트:

typedef struct node {
    int value;
    struct node *next;
} node_t;

node_t *head = NULL;
for (int i = 0; i < 100000; i++) {
    node_t *node = malloc(sizeof(node_t));
    node->value = i;
    node->next = head;
    head = node;
}

long long sum = 0;
node_t *curr = head;
while (curr) {
    sum += curr->value;
    curr = curr->next;
}

배열이 공간 지역성 덕분에 승리합니다: 캐시 라인(64바이트)이 한 번에 16개 요소를 로드하기 때문입니다. 연결 리스트는 흩어진 포인터로 인해 ~70% 미스를 유발합니다.

Memory Hierarchy and Latencies

실제 시스템은 다단계 계층 구조를 가집니다:

| 계층 | 크기 | 지연 시간 | 레지스터 대비 |

|-------------|------------|-------------|-----------------------|

| 레지스터 | ~256 B | 1 사이클 | 1× |

| L1 | 32-64 KB | 3-4 사이클 | 3× |

| L2 | 256 KB-1 MB| 12-15 사이클| 12× |

| L3 | 4-32 MB | 40-50 사이클| 40× |

| DRAM | GB | 100-200 사이클| 100× |

단일 DRAM 미스는 100 ALU 연산과 맞먹습니다. 임베디드 RISC-V에서는:

• L1: 16-32 KB (데스크톱의 64 KB 대비)
• L3 없음
• DRAM 100 MHz

작업 세트가 16 KB를 초과하면 지속적인 미스가 발생합니다.

Cache Lines and Locality

CPU는 64바이트 라인을 로드합니다. 순차 접근이 빛을 발합니다:

• 배열: 94% 히트
• 랜덤 접근: 빈번한 미스
• 리스트 노드(16 B): 라인의 75% 낭비

하드웨어 프리페칭은 순차 패턴에는 도움이 되지만 포인터에는 무용지물입니다.

Key Takeaways

• 캐시가 지배한다: 미스는 ALU 연산보다 100배 비쌈
• 지역성이 핵심: 좋은 캐시의 O(n) > 나쁜 캐시의 O(log n)
• 임베디드 더 가혹: 작은 캐시로 L1에 맞춰야 함
• 항상 프로파일링: perf가 진짜 병목을 드러냄
• 알고리즘 진화: 교과서 실리콘에서는 오래됨

— Editorial Team