C언어 스택 큐 캐시 최적화 성능 향상 가이드

스택과 큐: C 언어에서의 캐시 최적화와 성능

호출 스택은 모든 프로그램에 존재하지만, 커스텀 스택과 큐를 구현할 때 데이터 구조 선택은 성능에 결정적인 영향을 미칩니다. 연결 리스트는 캐시 미스와 malloc/free 오버헤드로 인해 최대 37배 더 많은 사이클을 소모할 수 있습니다. 배열 기반의 링 버퍼는 예측 가능한 메모리 사용량과 최대 35배의 속도 향상을 제공합니다.

스택 구현: 배열 vs 연결 리스트

전통적인 교과서적 스택 구현은 캐시 동작에서 차이를 보입니다.

배열 기반 스택 (고정 크기, O(1)):

#define MAX_SIZE 1000

typedef struct {
    int data[MAX_SIZE];
    int top;
} stack_t;

void push(stack_t *s, int value) {
    if (s->top < MAX_SIZE) {
        s->data[s->top++] = value;
    }
}

int pop(stack_t *s) {
    if (s->top > 0) {
        return s->data[--s->top];
    }
    return -1;
}

연결 리스트 기반 스택 (동적, O(1)):

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

typedef struct {
    node_t *top;
} stack_t;

void push(stack_t *s, int value) {
    node_t *node = malloc(sizeof(node_t));
    node->value = value;
    node->next = s->top;
    s->top = node;
}

int pop(stack_t *s) {
    if (s->top) {
        node_t *node = s->top;
        int value = node->value;
        s->top = node->next;
        free(node);
        return value;
    }
    return -1;
}

벤치마크 (1000회 연산):

| 구현 방식 | 사이클 | 캐시 미스 |

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

| 배열 | 12K | 45 |

| 연결 리스트 | 450K | 2100 |

연결 리스트 성능 저하 원인:

• malloc/free 오버헤드 (연산당 약 100 사이클)
• 힙에 흩어진 노드들 (L1/L2 캐시 미스)
• 포인터 추적 (데이터 의존성)

선택 가이드라인:

• 배열: 임베디드 시스템, 실시간 애플리케이션
• 연결 리스트: 예측 불가능한 크기 + 여유 메모리가 있는 경우

링 버퍼: 효율적인 큐의 기초

단순한 배열 기반 큐는 버퍼 끝에 도달하면 문제가 발생합니다:

void enqueue(queue_t *q, int value) {
    if (q->rear < MAX_SIZE) {
        q->data[q->rear++] = value;
    }
}

문제점: front==rear가 빈 큐와 가득 찬 큐를 구분할 수 없음.

링 버퍼는 모듈러 연산을 사용해 이 문제를 해결합니다:

typedef struct {
    int data[MAX_SIZE];
    int head;
    int tail;
    int count;
} ring_buffer_t;

void enqueue(ring_buffer_t *q, int value) {
    if (q->count < MAX_SIZE) {
        q->data[q->tail] = value;
        q->tail = (q->tail + 1) % MAX_SIZE;
        q->count++;
    }
}

int dequeue(ring_buffer_t *q) {
    if (q->count > 0) {
        int value = q->data[q->head];
        q->head = (q->head + 1) % MAX_SIZE;
        q->count--;
        return value;
    }
    return -1;
}

벤치마크 (100만 회 연산):

| 구현 방식 | 사이클 | 캐시 미스 |

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

| 링 버퍼 | 15M | 1234 |

| 연결 리스트 | 520M | 980K |

캐시 지역성 덕분에 35배의 속도 향상.

링 버퍼 최적화

% 연산 (10-40 사이클)이 병목 현상을 일으킵니다.

최적화 1: 2의 거듭제곱 크기 사용

#define MAX_SIZE 1024
#define MASK (MAX_SIZE - 1)

q->tail = (q->tail + 1) & MASK;  // 30 사이클 대신 1 사이클

결과: 1.76배 속도 향상 (15M → 8.5M 사이클).

최적화 2: Count 변수 제거

int is_empty(ring_buffer_t *q) {
    return q->head == q->tail;
}

int is_full(ring_buffer_t *q) {
    return ((q->tail + 1) & MASK) == q->head;
}

트레이드오프: 최대 MAX_SIZE-1개의 요소만 저장 가능.

락 프리 링 버퍼 (SPSC)

단일 생산자/단일 소비자 시나리오(인터럽트, 코어)용:

typedef struct {
    volatile int data[MAX_SIZE];
    volatile int head;  // 소비자 전용
    volatile int tail;  // 생산자 전용
} spsc_ring_buffer_t;

void enqueue(spsc_ring_buffer_t *q, int value) {
    int next_tail = (q->tail + 1) & MASK;
    if (next_tail != q->head) {
        q->data[q->tail] = value;
        __sync_synchronize();
        q->tail = next_tail;
    }
}

핵심 요소:

• volatile: 컴파일러 최적화 방지
• 약한 메모리 모델(ARM, RISC-V)용 메모리 배리어
• 원자적 연산 불필요

RISC-V 버전:

asm volatile("fence w, w" ::: "memory");

우선순위 큐: 이진 힙

최소 힙 (루트에 최소 요소):

typedef struct {
    int data[MAX_SIZE];
    int size;
} heap_t;

void heap_push(heap_t *h, int value) {
    int i = h->size++;
    h->data[i] = value;
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (h->data[i] <= h->data[parent]) break;
        // 교환
        int temp = h->data[i];
        h->data[i] = h->data[parent];
        h->data[parent] = temp;
        i = parent;
    }
}

복잡도: O(log n), 작은 n에 대해 좋은 캐시 지역성.

핵심 요약

• 스택/큐에 연결 리스트 사용 시 캐시 미스로 인해 30-40배 성능 저하
• 크기가 2^n인 링 버퍼는 비트 AND 연산으로 1.76배 속도 향상
• 락 프리 SPSC 버퍼는 인터럽트와 RTOS에 이상적
• 이진 힙은 O(log n) 복잡도로 배열의 장점 유지
• 임베디드 시스템에서는 고정 크기 = 결정성 보장

— Editorial Team