연결 리스트: 캐시 미스와 벤치마크

연결 리스트와 캐시 미스: 실무에서 배열에 밀리는 이유

연결 리스트는 동적 작업에 이상적인 선택처럼 보입니다: O(1) 삽입과 삭제, 재할당 없음. 하지만 실제로는 캐시 미스로 인해 배열에 자주 뒤처집니다. next 포인터를 통한 각 점프가 메모리 서브시스템에 부하를 주며, 이론적 우위를 병목 현상으로 바꿔버립니다.

10만 개 요소에 대한 테스트에서 그 차이가 드러납니다:

| 작업 | 배열 | 연결 리스트 | 지연 |

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

| 순차 순회 | 70 μs | 179 μs | ×2.5 |

| 랜덤 접근 | 95 μs | 2847 μs | ×30 |

| 추가 | 42 μs | 1234 μs | ×29 |

삽입 작업조차 연결 리스트가 우위를 점해야 할 곳에서 재할당과 캐시 미스로 인해 느려집니다.

캐시 미스 메커니즘

CPU 캐시 라인은 한 번에 64바이트를 가져옵니다. 배열에서는 요소가 순차적으로 배치되어 한 번의 미스로 16개의 int에 접근할 수 있습니다. 반면 연결 리스트에서는 노드가 힙 전체에 흩어져 있습니다:

// 전형적인 노드
struct node {
    int value;     // 4 bytes
    node *next;    // 8 bytes
}; // 패딩 포함 16 bytes

리스트를 순회할 때 각 노드마다 미스가 발생합니다(~100 사이클 지연). 10만 개 노드라면 배열의 62.5만 사이클에 비해 1천만 사이클이 소요됩니다. 배열은 400 KB를 사용하지만 리스트는 1.6 MB(4배 오버헤드)를 씁니다.

메모리 할당 비용

리스트 생성에는 10만 번의 malloc() 호출이 필요합니다:

for (int i = 0; i < 100000; i++) {
    node *n = malloc(sizeof(node)); // 힙 검색, 메타데이터, 단편화
    n->value = i;
    n->next = head;
    head = n;
}

배열은 한 번의 호출만으로 충분합니다. 벤치마크 차이: 42 μs 대 1234 μs.

연결 리스트가 정당화되는 드문 시나리오

연결 리스트는 특수한 경우에만 적합합니다:

• 커널의 침투형 리스트 (Linux list_head): 구조체에 노드를 내장해 지역성을 개선.
• 락-프리 구조체: 배열 대비 포인터의 원자적 CAS가 더 간단.
• 작고 정적인 데이터셋에 드문 삽입.

Treiber의 락-프리 스택 예시:

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

void push(node_t **head, node_t *node) {
    do {
        node->next = *head;
    } while (!atomic_compare_exchange(head, &node->next, node));
}

사용해야 할 때의 최적화 기법

객체 풀

노드 배열을 미리 할당합니다:

#define POOL_SIZE 10000
node_t pool[POOL_SIZE];
int idx = 0;

node_t *alloc() {
    return idx < POOL_SIZE ? &pool[idx++] : NULL;
}

속도: 287 μs (malloc 대비 ×4.3, 배열 대비 ×6.8).

언롤링 리스트

노드당 여러 요소 저장:

#define N 16
typedef struct {
    int values[N];
    int count;
    struct node *next;
} unrolled_t;

순회: 45 μs (표준 리스트보다 빠르며, 순차 접근 시 배열과 비슷).

XOR 연결 리스트

prev^next의 XOR로 메모리 절약:

typedef struct {
    int value;
    node *xor_ptr; // prev ^ next
} xor_node;

// 순회 시 prev 추적 필요
node *next = (uintptr_t)prev ^ (uintptr_t)curr->xor_ptr;

단점: 디버깅 복잡, 양방향 순회 불가. 권장하지 않음.

RTOS 사례: 왜 거기서는 리스트가 잘 작동하나

FreeRTOS의 스케줄러는 우선순위별(32단계) 리스트 배열을 사용합니다:

list_head ready_tasks[MAX_PRIORITIES];

성공 이유:

• 작은 리스트(1~5 태스크).
• task_struct에 노드 내장.
• 우선순위별 O(1) 작업.

Cortex-M4 벤치마크: 삽입 0.8 μs, 삭제 0.6 μs.

주요 교훈

• 캐시가 지배적: O(1) 작업에서도 포인터 미스가 성능을 떨어뜨립니다.
• 메모리 오버헤드: 포인터 + 단편화로 4배 증가.
• 동적 배열 선호: 캐시 패널티 없이 완전 희석 O(1) 삽입.
• 최적화는 어느 정도 도움: 풀과 언롤링 리스트가 격차를 좁히지만 앞서진 못함.
• RTOS 예외: 내장 노드 + 작은 크기로 선택 정당화.

— Editorial Team