C++ 캐시 최적화 실전 | 캐시 라인·프리페치·False Sharing·타일링

들어가며: 같은 O(n)인데 속도가 크게 다른 이유

#15-2 캐시 친화적 코드와 #39-1 데이터 지향 설계에서 캐시 기초를 다뤘다면, 이 글은 실전 캐시 최적화를 집중적으로 다룬다. 현대 CPU에서는 메모리 접근 지연(~100ns)이 연산(~1ns)보다 수십 배 크기 때문에, 캐시를 제대로 활용하지 않으면 병목이 됩니다. 비유: 캐시는 “책상 위에 자주 쓰는 책을 올려두는 것”이다. 책상(캐시)이 작으므로, 필요한 책만 가까이 두고 순서대로 읽어야 효율적입니다. 책을 무작위로 꺼내면 책장(메모리)을 매번 왔다 갔다 해야 합니다. 이 글을 읽으면:

• 캐시 친화적 데이터 구조를 설계·구현할 수 있습니다.
• 프리페치로 랜덤 접근 시 지연을 숨길 수 있습니다.
• False Sharing을 방지해 멀티스레드 성능을 확보할 수 있습니다.
• 문제가 접근 패턴인지 데이터 레이아웃인지 구분할 수 있습니다. 레이아웃 재설계(SoA, ECS, 핫/콜드 분리)는 #51-6 데이터 지향 설계에서 다룹니다.
• 프로덕션에서 검증된 패턴을 적용할 수 있습니다. 요구 환경: C++17 이상 (alignas, std::hardware_destructive_interference_size)

---

cache-misses가 병목으로 드러나는 상황

파티클 시스템이 프레임 드랍을 유발할 때

"10만 개 파티클의 위치만 매 프레임 갱신하는데 16ms를 넘습니다."
"프로파일러에서 연산 자체는 O(n)인데, 메모리 접근이 병목입니다."

상황: 게임에서 Particle 구조체에 위치(x,y,z), 속도(vx,vy,vz), 색상(r,g,b), 수명 등이 한 덩어리로 있습니다. “위치만 갱신”해도 캐시 라인(64바이트)당 실제로 쓰는 데이터는 12바이트뿐이며, 나머지는 낭비됩니다. 해결 포인트: 이 경우는 접근 패턴이 아니라 데이터 레이아웃의 문제입니다. 순차로 잘 읽고 있어도 가져온 바이트의 대부분을 버리기 때문입니다. 위치 배열만 따로 두는 SoA로 바꾸는 방법과 벤치마크는 #51-6 데이터 지향 설계에 있습니다. 이 글의 “접근 패턴 문제인가, 레이아웃 문제인가”에서는 레이아웃 문제인지 판별하는 방법만 봅니다.

스레드를 늘렸는데 오히려 느려질 때

"8스레드로 병렬 카운팅했는데 단일 스레드와 별 차이가 없어요."
"perf stat에서 cache-misses가 매우 많아요."

상황: std::atomic<int> counters[8]처럼 8개 카운터가 같은 캐시 라인에 있습니다. 한 스레드가 counters[0]을 수정할 때마다 다른 스레드의 counters[1]이 있는 캐시 라인이 무효화됩니다. False Sharing입니다. 해결 포인트: alignas(64)로 각 카운터를 별도 캐시 라인에 배치하면 코어 사이의 캐시 라인 왕복이 사라져, 스레드를 늘린 만큼 처리량이 늘어나는 쪽으로 바뀝니다.

링크드 리스트·트리 순회가 느릴 때

"BST를 순회하는데, 노드마다 캐시 미스가 나요."
"포인터를 따라가므로 다음 주소를 미리 알 수 있는데 활용이 안 돼요."

상황: 노드가 힙에 흩어져 있어 순차 접근이 불가능합니다. 하지만 다음 노드 주소를 미리 알 수 있으므로, __builtin_prefetch로 다음 블록을 미리 로드하면 지연을 숨길 수 있습니다. 해결 포인트: 프리페치로 다음 노드를 미리 캐시에 올리면 메모리 대기 시간을 현재 노드 처리 시간 뒤에 숨길 수 있습니다. 다만 노드당 처리가 너무 짧으면 숨길 시간이 없고, 너무 멀리 프리페치하면 캐시에서 밀려나므로 효과는 측정으로 확인해야 합니다.

대용량 행렬 연산이 병목일 때

"4096×4096 행렬을 열 우선으로 순회하는데 너무 느려요."
"행 우선으로 바꾸기만 해도 10배 빨라진다고 하던데."

상황: C/C++ 2차원 배열은 행 우선(row-major) 저장입니다. 열 우선 순회는 매 접근마다 다른 행을 건너뛰어 캐시 미스가 폭발합니다. 해결 포인트: 행 우선 순회로 바꾸고, 가능하면 타일링(작은 블록 단위 처리)을 적용합니다. 같은 계열의 증상으로 “100만 건 중 한 필드만 집계하는데 전체 행을 읽는다”, “x, y, z가 구조체마다 떨어져 있어 자동 벡터화가 안 된다”도 있습니다. 둘 다 레이아웃 문제이므로 #51-6의 SoA·컬럼형 저장으로 해결합니다.

시나리오별 권장 기법

시나리오	특징	권장 기법
파티클·엔티티 대량 업데이트	특정 필드만 반복 처리	SoA (#51-6)
멀티스레드 per-thread 카운터	같은 배열에 스레드별 쓰기	캐시 라인 정렬
링크드 리스트·트리 순회	포인터 체이닝, 다음 주소 예측 가능	프리페치
행렬·이미지 처리	2차원 순회	행 우선 + 타일링
필드별 집계·SIMD	일부 필드만 사용, 연속 배열 필요	SoA, 컬럼형 (#51-6)

---

캐시 기초와 메모리 계층

메모리 계층

CPU Register    < 1ns     (가장 빠름)
    ↓
L1 Cache        ~1ns      (32-64KB per core)
    ↓
L2 Cache        ~3ns      (256KB-1MB per core)
    ↓
L3 Cache        ~10ns     (8-32MB shared)
    ↓
RAM             ~100ns    (수 GB)
    ↓
SSD             ~100μs    (수백 GB)

캐시 라인: CPU는 메모리를 64바이트 단위(캐시 라인)로 가져옵니다. 한 주소를 읽으면 그 주변 64바이트가 함께 로드됩니다.

캐시 히트 vs 미스

// g++ -std=c++17 -O2 -o cache_basic cache_basic.cpp
#include <vector>
#include <chrono>
#include <iostream>
int main() {
    const size_t N = 1000000;
    std::vector<int> data(N, 1);
    // ✅ 캐시 히트: 연속 접근
    auto start = std::chrono::high_resolution_clock::now();
    long long sum = 0;
    for (size_t i = 0; i < N; ++i) {
        sum += data[i];
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto ms_seq = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    // ❌ 캐시 미스: 64칸씩 건너뛰기 (캐시 라인당 1개만 사용)
    start = std::chrono::high_resolution_clock::now();
    sum = 0;
    for (size_t i = 0; i < N; i += 16) {  // int 16개 = 64바이트
        sum += data[i];
    }
    end = std::chrono::high_resolution_clock::now();
    auto ms_strided = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "Sequential: " << ms_seq << " ms, Strided: " << ms_strided << " ms\n";
    return 0;
}

설명: 연속 접근은 캐시 라인당 16개 int를 활용하지만, 16칸씩 건너뛰면 캐시 라인당 1개만 쓰고 나머지는 낭비됩니다. 실제로는 strided 접근이 더 적은 원소를 읽지만, 캐시 미스가 많아 오히려 느릴 수 있습니다.

메모리 계층 시각화

flowchart TB
    subgraph fast["빠른 접근 (~1ns)"]
        R[Register]
        L1[L1 Cache 32KB]
        L2[L2 Cache 256KB]
    end
    subgraph slow["느린 접근 (~100ns)"]
        L3[L3 Cache 8MB]
        RAM[RAM]
    end
    R --> L1 --> L2 --> L3 --> RAM

---

캐시 친화적 데이터 구조

연속 메모리 사용

// ❌ 나쁜 예: 링크드 리스트 (노드마다 캐시 미스)
struct Node {
    int value;
    Node* next;
};
void sum_list(Node* head) {
    for (Node* p = head; p; p = p->next) {
        sum += p->value;  // 매 노드마다 다른 메모리 블록
    }
}
// ✅ 좋은 예: 벡터 (연속 메모리, 캐시 히트)
void sum_vector(const std::vector<int>& v) {
    for (int x : v) {
        sum += x;  // 연속 접근, 캐시 효율 최고
    }
}

행 우선 순회

// g++ -std=c++17 -O2 -o matrix_order matrix_order.cpp
#include <vector>
#include <chrono>
#include <iostream>
const int N = 2048;
// ❌ 열 우선 순회 (느림): 매 접근마다 N*4바이트 건너뜀
void col_major(std::vector<std::vector<int>>& m) {
    for (int c = 0; c < N; ++c) {
        for (int r = 0; r < N; ++r) {
            m[r][c] = r + c;
        }
    }
}
// ✅ 행 우선 순회 (빠름): 연속 접근
void row_major(std::vector<std::vector<int>>& m) {
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            m[r][c] = r + c;
        }
    }
}
int main() {
    std::vector<std::vector<int>> m(N, std::vector<int>(N));
    auto start = std::chrono::high_resolution_clock::now();
    row_major(m);
    auto end = std::chrono::high_resolution_clock::now();
    auto ms_row = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    start = std::chrono::high_resolution_clock::now();
    col_major(m);
    end = std::chrono::high_resolution_clock::now();
    auto ms_col = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "Row-major: " << ms_row << " ms, Col-major: " << ms_col << " ms\n";
    return 0;
}

자주 쓰는 필드끼리 모으기

구조체 안에 매 프레임 쓰는 필드와 가끔 쓰는 필드(std::string 이름, 설명 등)가 섞여 있으면, 캐시 라인마다 쓰지 않는 바이트가 함께 올라옵니다. 이를 둘로 나누는 핫/콜드 분리와 인덱스 동기화 방법은 #51-6의 핫/콜드 분리 절에서 다룹니다. 여기서 기억할 점은, 이런 구조체 변경은 호출하는 코드 전체에 영향을 주므로 False Sharing 방지 절의 정렬이나 프리페치 절의 프리페치보다 비용이 큰 최적화라는 것입니다. “접근 패턴 문제인가, 레이아웃 문제인가”의 방법으로 레이아웃이 실제 원인인지 먼저 확인하는 편이 좋습니다.

구조체 패딩 최소화

// ❌ 나쁜 예: 패딩으로 크기 증가
struct Bad {
    char a;      // 1바이트 + 3바이트 패딩
    int b;       // 4바이트
    char c;      // 1바이트 + 3바이트 패딩
};  // 총 12바이트
// ✅ 좋은 예: 큰 타입 먼저 배치
struct Good {
    int b;       // 4바이트
    char a;      // 1바이트
    char c;      // 1바이트 + 2바이트 패딩
};  // 총 8바이트

---

접근 패턴 문제인가, 레이아웃 문제인가

캐시 미스가 많다는 것만으로는 무엇을 고쳐야 할지 알 수 없습니다. 크게 두 갈래로 나뉩니다.

• 접근 패턴 문제: 데이터는 잘 배치되어 있지만 순회 순서가 나쁘다(열 우선 순회, 포인터 체이닝, 캐시보다 큰 작업 집합). 코드의 루프만 바꾸면 되므로 이 글의 행 우선 순회, 행렬 타일링 예제, 프리페치 부분으로 해결합니다.
• 레이아웃 문제: 순회 순서는 이미 순차적인데, 가져온 캐시 라인 중 실제로 쓰는 바이트가 적습니다. 구조체 설계를 바꿔야 하므로 #51-6 데이터 지향 설계의 SoA·핫/콜드 분리가 필요합니다.

둘을 구분하는 간단한 계산이 있습니다. 루프가 원소 하나당 실제로 읽고 쓰는 바이트 수를 원소 크기(sizeof)로 나눈 값입니다. 36바이트짜리 파티클 구조체에서 위치 12바이트와 속도 12바이트만 쓰는 루프라면 24/36, 약 67%입니다. 이 비율이 낮을수록 메모리 대역폭의 상당 부분이 쓰지 않는 필드를 나르는 데 쓰이고 있다는 뜻이고, 루프 순서를 아무리 다듬어도 그 이상 좋아지지 않습니다.

측정으로 확인하려면 perf stat으로 캐시 미스 수와 메모리 대역폭을 함께 봅니다. 순차 순회인데 LLC 미스가 원소 수에 비례해 많고 대역폭이 포화에 가깝다면 레이아웃 문제일 가능성이 높습니다. 반대로 대역폭은 여유가 있는데 미스가 많고 IPC가 낮다면, 메모리 지연을 기다리는 접근 패턴 문제(포인터 체이닝 등)일 가능성이 높습니다. 이 구분을 먼저 해 두면, SoA로 바꿨는데 효과가 없었다거나 프리페치를 넣었는데 효과가 없었다는 헛수고를 줄일 수 있습니다.

---

False Sharing 방지

False Sharing 원리

flowchart LR
    subgraph CacheLine["캐시 라인 64B"]
        C0["counter[0]"]
        C1["counter[1]"]
        C2["counter[2]"]
    end
    T1[스레드1] -->|수정| C0
    T2[스레드2] -->|수정| C1
    C0 -.->|캐시 무효화| C1

한 스레드가 counter[0]을 수정하면, 같은 캐시 라인에 있는 counter[1]의 캐시가 무효화됩니다. 다른 스레드가 counter[1]을 읽으려면 메모리에서 다시 가져와야 합니다.

잘못된 예: 같은 캐시 라인 공유

// bad_false_sharing.cpp
#include <thread>
#include <vector>
#include <atomic>
#include <chrono>
#include <iostream>
void bad_parallel_counter() {
    const int num_threads = 8;
    std::atomic<int64_t> counters[8];  // 8*8 = 64바이트, 한 캐시 라인!
    for (int i = 0; i < 8; ++i) counters[i].store(0);
    auto start = std::chrono::high_resolution_clock::now();
    std::vector<std::thread> threads;
    for (int t = 0; t < num_threads; ++t) {
        threads.emplace_back([&counters, t]() {
            for (int i = 0; i < 10000000; ++i) {
                counters[t].fetch_add(1, std::memory_order_relaxed);
            }
        });
    }
    for (auto& th : threads) th.join();
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "Bad (false sharing): " << ms << " ms\n";
}

올바른 예: 캐시 라인 정렬

// good_cache_line_aligned.cpp
#include <thread>
#include <vector>
#include <atomic>
#include <chrono>
#include <iostream>
#include <new>
// C++17: 하드웨어 캐시 라인 크기
constexpr size_t CACHE_LINE_SIZE = std::hardware_destructive_interference_size;
struct alignas(CACHE_LINE_SIZE) AlignedCounter {
    std::atomic<int64_t> value{0};
};
void good_parallel_counter() {
    const int num_threads = 8;
    std::vector<AlignedCounter> counters(num_threads);
    auto start = std::chrono::high_resolution_clock::now();
    std::vector<std::thread> threads;
    for (int t = 0; t < num_threads; ++t) {
        threads.emplace_back([&counters, t]() {
            for (int i = 0; i < 10000000; ++i) {
                counters[t].value.fetch_add(1, std::memory_order_relaxed);
            }
        });
    }
    for (auto& th : threads) th.join();
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "Good (aligned): " << ms << " ms\n";
}

C++17 이전 환경에서의 정렬

// alignas(64)는 대부분의 x86-64에서 캐시 라인 크기
struct alignas(64) CacheLineAlignedCounter {
    std::atomic<int64_t> value{0};
};
// 또는 수동 패딩
struct PaddedCounter {
    std::atomic<int64_t> value{0};
    char padding[64 - sizeof(std::atomic<int64_t>)];
};

---

프리페치 활용

기본 사용법

// prefetch_example.cpp
#include <xmmintrin.h>  // _mm_prefetch (SSE)
// 또는 GCC/Clang: __builtin_prefetch
void process_with_prefetch(const int* data, size_t n) {
    constexpr int PREFETCH_DISTANCE = 8;  // 8*4=32바이트 앞서 로드
    for (size_t i = 0; i < n; ++i) {
        // 다음 블록을 미리 캐시에 로드
        if (i + PREFETCH_DISTANCE < n) {
            __builtin_prefetch(&data[i + PREFETCH_DISTANCE], 0, 3);
            // 0: 읽기, 3: temporal locality (L1에 유지)
        }
        // 현재 데이터 처리
        int x = data[i];
        // ...
    }
}

링크드 리스트 순회 시 프리페치

struct Node {
    int value;
    Node* next;
};
int sum_list_prefetch(Node* head) {
    int sum = 0;
    for (Node* p = head; p; p = p->next) {
        // 다음 노드를 미리 로드 (다음 반복에서 사용)
        if (p->next) {
            __builtin_prefetch(p->next, 0, 3);
        }
        sum += p->value;
    }
    return sum;
}

프리페치 주의사항

// ❌ 나쁜 예: 너무 멀리 프리페치 (캐시에서 밀려남)
for (size_t i = 0; i < n; ++i) {
    if (i + 64 < n) {
        __builtin_prefetch(&data[i + 64], 0, 3);  // 너무 멂
    }
    process(data[i]);
}
// ✅ 좋은 예: 적당한 거리 (4~16 요소 앞)
for (size_t i = 0; i < n; ++i) {
    if (i + 8 < n) {
        __builtin_prefetch(&data[i + 8], 0, 3);
    }
    process(data[i]);
}

프리페치 locality 힌트:

• 0: 낮은 지역성 (L3에만)
• 1: 중간 (L2)
• 2: 높음 (L1에 가깝게)
• 3: temporal (L1에 오래 유지)

---

워커 통계 정렬과 행렬 타일링 예제

멀티스레드 워커 통계 (캐시 라인 정렬)

// worker_stats.cpp
#include <thread>
#include <vector>
#include <atomic>
#include <cstddef>
constexpr size_t CACHE_LINE = 64;
struct alignas(CACHE_LINE) WorkerStats {
    std::atomic<uint64_t> requests_processed{0};
    std::atomic<uint64_t> bytes_sent{0};
};
class ThreadPoolStats {
public:
    explicit ThreadPoolStats(size_t num_workers)
        : stats_(num_workers) {}
    void record(size_t worker_id, uint64_t bytes) {
        stats_[worker_id].requests_processed.fetch_add(1, std::memory_order_relaxed);
        stats_[worker_id].bytes_sent.fetch_add(bytes, std::memory_order_relaxed);
    }
    uint64_t total_requests() const {
        uint64_t sum = 0;
        for (const auto& s : stats_) {
            sum += s.requests_processed.load(std::memory_order_relaxed);
        }
        return sum;
    }
private:
    std::vector<WorkerStats> stats_;
};

행렬 타일링 (캐시에 맞는 블록 처리)

// matrix_tiling.cpp
#include <vector>
#include <algorithm>
constexpr int TILE = 32;  // L1 캐시에 맞는 타일 크기
void matmul_tiled(const std::vector<float>& A,
                  const std::vector<float>& B,
                  std::vector<float>& C,
                  int N) {
    for (int i0 = 0; i0 < N; i0 += TILE) {
        for (int j0 = 0; j0 < N; j0 += TILE) {
            for (int k0 = 0; k0 < N; k0 += TILE) {
                int i_end = std::min(i0 + TILE, N);
                int j_end = std::min(j0 + TILE, N);
                int k_end = std::min(k0 + TILE, N);
                for (int i = i0; i < i_end; ++i) {
                    for (int j = j0; j < j_end; ++j) {
                        float sum = C[i * N + j];
                        for (int k = k0; k < k_end; ++k) {
                            sum += A[i * N + k] * B[k * N + j];
                        }
                        C[i * N + j] = sum;
                    }
                }
            }
        }
    }
}

---

alignas 후에도 남는 False Sharing, 역효과 프리페치: 에러 해결

alignas로 패딩했는데도 False Sharing 발생

증상: alignas(64)를 썼는데 perf stat에서 cache-misses가 여전히 많음. 원인: std::vector<AlignedCounter>에서 AlignedCounter가 64바이트여도, 벡터가 연속 할당되면 첫 번째 요소가 64바이트 경계에 있지 않을 수 있습니다.

// ❌ 잘못된 예: 벡터 내부 요소 정렬 보장 안 됨
std::vector<AlignedCounter> counters(8);
// counters[0]의 주소가 64의 배수가 아닐 수 있음

해결법:

// ✅ 올바른 예: alignas가 있는 타입은 vector가 정렬된 메모리 할당 요청
// C++17: std::vector는 alignas를 가진 타입에 대해 정렬된 할당을 요청함
// 추가 보장: std::allocator가 over-aligned 타입 지원
std::vector<AlignedCounter> counters(8);
// 또는 수동으로 aligned_alloc 사용
AlignedCounter* counters = static_cast<AlignedCounter*>(
    std::aligned_alloc(64, 8 * sizeof(AlignedCounter)));

실제로는 std::vector가 C++17 이상에서 over-aligned 타입을 지원하므로, alignas(64) 구조체가 요소로 있으면 정렬이 보장됩니다. 문제가 있다면 std::unique_ptr + aligned_alloc을 사용하세요.

SoA로 바꿨는데 오히려 느려짐

한 원소의 여러 필드를 함께 쓰는 루프를 SoA로 바꾸면 동시에 여러 배열 스트림을 오가게 되어 이득이 없거나 오히려 느려집니다. 앞의 “접근 패턴 문제인가, 레이아웃 문제인가”에서 본 “실제로 쓰는 바이트 비율”이 이미 높았던 경우입니다. 원인과 하이브리드 레이아웃은 #51-6의 에러 절에 있습니다.

프리페치를 넣었는데 성능이 떨어짐

증상: __builtin_prefetch 추가 후 오히려 느려짐. 원인: (1) 프리페치 거리가 너무 멂 — 캐시에 로드된 데이터가 사용되기 전에 밀려남. (2) 순차 접근인데 프리페치 — 컴파일러/하드웨어가 이미 충분히 예측하고 있어서 불필요한 명령만 추가됩니다. (3) 캐시에 이미 있는 데이터를 프리페치 — 낭비.

// ❌ 순차 접근에는 프리페치 불필요 (CPU가 이미 예측함)
for (size_t i = 0; i < n; ++i) {
    __builtin_prefetch(&data[i + 1], 0, 3);  // 불필요
    process(data[i]);
}

해결법: 랜덤 접근 또는 포인터 체이닝에서만 프리페치. 순차 접근은 제거. 거리는 4~16 요소 정도로 실험.

구조체 크기가 캐시 라인의 배수로 커짐

증상: sizeof(Entity)가 128바이트 이상으로 커져서, 10만 개일 때 12MB 이상 사용. 원인: 모든 필드에 alignas(64)를 써서 불필요한 패딩이 생김. 멀티스레드에서 공유되는 변수만 캐시 라인 정렬이 필요합니다.

// ❌ 과도한 정렬: 단일 스레드에서만 쓰는 구조체
struct Entity {
    alignas(64) float x, y, z;   // 불필요
    alignas(64) float vx, vy, vz; // 불필요
};

해결법: 스레드별로 수정되는 변수만 alignas(64) 적용. 일반 구조체는 패딩 최소화만.

행 우선 순회인데도 느림

증상: 2차원 배열을 행 우선으로 순회하는데 여전히 느림. 원인: std::vector<std::vector<int>>는 행마다 별도 할당이라, 행이 메모리에 연속하지 않습니다. 열 우선이든 행 우선이든 캐시 미스가 많을 수 있습니다.

// ❌ 행이 연속이 아님
std::vector<std::vector<int>> m(N, std::vector<int>(N));
for (int r = 0; r < N; ++r) {
    for (int c = 0; c < N; ++c) {
        m[r][c] = 0;  // m[r]과 m[r+1]이 다른 메모리 블록
    }
}

해결법:

// ✅ 1차원 배열로 연속 저장
std::vector<int> m(N * N);
for (int r = 0; r < N; ++r) {
    for (int c = 0; c < N; ++c) {
        m[r * N + c] = 0;
    }
}

---

2의 거듭제곱 크기 배열을 열 방향으로 돌면 유독 느림

float m[1024][1024]처럼 한 행이 4KB(2의 거듭제곱)인 배열을 열 방향으로 순회하면, 행 우선 순회로 고치기 전 단계에서 예상보다 훨씬 더 느린 경우가 있습니다. 매 접근 주소가 정확히 4KB씩 떨어지면 모두 같은 캐시 세트에 매핑되어, 캐시 전체 용량과 상관없이 몇 줄만 들어가고 서로를 계속 밀어냅니다(conflict miss). 행 우선 순회로 바꾸는 게 1순위이고, 열 순회가 불가피한 알고리즘(전치, 일부 행렬 연산)이라면 행 길이에 패딩을 조금 줘서(float m[1024][1024 + 16]) 주소가 같은 세트에 몰리지 않게 하는 방법이 쓰입니다. 행렬 크기를 1000에서 1024로 “보기 좋게” 바꿨더니 느려졌다는 사례가 이 유형입니다.

적용 순서와 측정 방법

적용 전 점검 항목

- [ ] 프로파일러로 cache-misses 확인 후 최적화 (perf stat -e cache-misses)
- [ ] 연속 메모리 사용: vector 우선, list는 꼭 필요할 때만
- [ ] 2차원 데이터: 행 우선 순회, 1차원 배열로 연속 저장
- [ ] 멀티스레드 per-thread 데이터: alignas(64) 또는 std::hardware_destructive_interference_size
- [ ] 순차 순회인데도 미스가 많으면: 원소당 사용 바이트 비율 확인 → 낮으면 레이아웃 재설계([#51-6](/blog/cpp-series-51-6-data-oriented-design/))
- [ ] 랜덤 접근·포인터 체이닝: 프리페치 실험 (거리 4~16)
- [ ] 구조체: 큰 타입 먼저 배치해 패딩 최소화
- [ ] 과도한 alignas 금지: 스레드 공유 변수만

성능 측정 명령

# g++ -std=c++17 -O2 -o bench cache_bench.cpp && perf stat -e cache-misses,cache-references ./bench
perf stat -e cache-misses,cache-references,L1-dcache-load-misses ./my_program

# False Sharing 의심 시: 어느 캐시 라인을 여러 코어가 번갈아 수정하는지 보여 줌
perf c2c record ./my_program
perf c2c report   # "Shared Data Cache Line Table"에서 HITM이 높은 라인과 그 라인의 필드 오프셋 확인

perf stat은 “캐시 미스가 많다”까지만 알려 줍니다. 멀티스레드에서 스레드를 늘릴수록 느려지는 증상이라면 perf c2c로 어느 변수가 문제인지까지 좁히는 편이 빠릅니다. 추측으로 alignas(64)를 여기저기 붙이다가 정작 문제인 필드를 놓치는 경우가 흔하기 때문입니다.

의사 결정 플로우

flowchart TD
    A[성능 병목] --> B{프로파일러}
    B -->|cache-misses 높음| C{메모리 접근 패턴}
    C -->|순차 접근| D[연속 메모리? 행 우선?]
    C -->|랜덤 접근| E[프리페치 활용]
    C -->|멀티스레드 per-thread| F[캐시 라인 정렬]
    C -->|특정 필드만 조회| G[SoA 검토]
    D --> H[vector, 1차원 배열]
    E --> I[__builtin_prefetch]
    F --> J["alignas(64)"]
    G --> K["레이아웃 재설계 (51-6 참고)"]

---

벤치마크 결과 읽는 법

AoS와 SoA를 비교하는 벤치마크 코드는 #51-6의 성능 벤치마크에 있습니다. False Sharing은 False Sharing 방지 절의 코드를 스레드 수 1, 2, 4, 8로 바꿔 가며 돌리면 추세를 볼 수 있습니다.

결과를 읽는 법

구체적인 ms 값은 CPU, 캐시 크기, 컴파일 옵션에 따라 크게 달라 여기 고정값을 적지 않았습니다. 직접 돌려 보면 보통 이런 경향이 나옵니다.

• 행 우선 vs 열 우선: 행렬이 캐시보다 작으면 차이가 거의 없고, 캐시(특히 LLC)보다 커지는 순간 열 우선 쪽이 급격히 느려집니다. 크기를 바꿔 가며 측정하면 이 꺾이는 지점이 캐시 크기를 드러냅니다.
• False Sharing: 같은 캐시 라인을 공유하는 카운터는 스레드를 늘릴수록 오히려 느려지고, 캐시 라인 정렬 후에는 스레드 수에 비례해 빨라지는 쪽으로 바뀝니다. “몇 배”보다 스레드 수를 늘렸을 때의 추세를 보는 게 진단에 더 유용합니다.
• 벤치마크는 반드시 -O2 이상, 결과값을 실제로 사용하는 형태로 작성해야 합니다. 최적화 빌드에서 쓰지 않는 결과는 컴파일러가 루프째 지워서 “둘 다 0ms”가 나옵니다.

캐시 라인 크기는 64바이트로 고정이 아니다

x86-64는 64바이트가 사실상 표준이지만, Apple M 시리즈 같은 일부 ARM 칩은 128바이트입니다. alignas(64)로 False Sharing을 막아 둔 코드가 Apple Silicon에서는 효과가 절반이 될 수 있습니다. 여러 플랫폼을 지원한다면 std::hardware_destructive_interference_size(C++17, 컴파일러가 대상 아키텍처 기준 값을 제공)를 쓰거나, 플랫폼별 상수를 두는 편이 안전합니다. 다만 이 상수는 ABI에 영향을 줄 수 있어 GCC가 헤더에서 쓰면 경고(-Winterference-size)를 내므로, 라이브러리 공개 헤더보다는 구현 파일 안에서 쓰는 것이 무난합니다.

---

워커 통계 정렬과 독립 조회 겹치기

HTTP 서버 워커 통계 (캐시 라인 정렬)

struct alignas(64) WorkerMetrics {
    std::atomic<uint64_t> requests{0};
    std::atomic<uint64_t> bytes{0};
};
std::vector<WorkerMetrics> workers(num_threads);
// 각 워커 스레드가 자신의 인덱스만 수정

여러 개의 독립적인 조회를 겹치기

트리 탐색 하나는 다음 노드가 현재 노드의 비교 결과로 정해지므로, 다음 노드를 미리 가져올 방법이 없습니다(비교가 끝났을 때는 이미 늦습니다). 프리페치가 효과를 내는 것은 서로 독립적인 조회가 여러 개 있을 때입니다. 해시 테이블 일괄 조회처럼, 여러 키의 버킷 주소를 먼저 계산해 모두 프리페치한 뒤 실제 비교를 하면 메모리 지연이 겹쳐집니다.

// 키 배치를 한 번에 조회: 주소 계산 → 프리페치 → 실제 접근
void batch_lookup(const Table& t, const uint64_t* keys, size_t n, Value** out) {
    constexpr size_t B = 8;
    for (size_t i = 0; i < n; i += B) {
        size_t m = std::min(B, n - i);
        const Bucket* b[B];
        for (size_t j = 0; j < m; ++j) {
            b[j] = t.bucket_for(keys[i + j]);
            __builtin_prefetch(b[j], 0, 3);
        }
        for (size_t j = 0; j < m; ++j) out[i + j] = b[j]->find(keys[i + j]);
    }
}

B-tree처럼 노드가 여러 캐시 라인에 걸치는 경우에는, 노드에 도착한 직후 그 노드의 나머지 캐시 라인을 프리페치하는 것이 효과적입니다. 이는 다음 노드가 아니라 현재 노드 안의 순차 접근을 앞당기는 것입니다.

---

기법별 효과 요약

기법	용도	효과가 큰 조건
레이아웃 재설계 (#51-6)	같은 필드만 대량 처리	원소당 사용 바이트 비율이 낮을 때
캐시 라인 정렬	멀티스레드 per-thread	여러 스레드가 인접한 변수를 자주 쓸 때
행 우선 순회	2차원 배열	행렬이 캐시보다 클 때 (열 우선은 매 접근이 다른 캐시 라인)
프리페치	랜덤 접근·포인터 체이닝	다음 주소를 미리 알 수 있고 노드당 처리 시간이 있을 때
연속 메모리	list → vector	순회가 잦을 때 (프리페처가 순차 패턴을 따라감)

핵심 원칙:

1. 프로파일링 먼저: cache-misses 확인 후 최적화
2. 순차인데도 느리면 → 레이아웃 문제인지 확인 (#51-6)
3. 멀티스레드 per-thread → alignas(64)
4. 2차원 → 1차원 연속 + 행 우선
5. 랜덤 접근 → 프리페치 실험 (거리 4~16)
6. 과도한 패딩 금지: 스레드 공유 변수만

---

자주 묻는 질문 (FAQ)

Q. SoA vs AoS, 언제 어느 쪽을 써야 하나요?

A. 같은 필드만 대량 순회하면 SoA, 한 객체의 여러 필드를 함께 쓰면 AoS가 유리합니다. 판단 기준과 하이브리드 구성, 벤치마크는 #51-6 데이터 지향 설계에서 자세히 다룹니다.

Q. std::hardware_destructive_interference_size가 0입니다.

A. C++17 미지원 환경이거나 컴파일러가 아직 구현하지 않았을 수 있습니다. 이 경우 alignas(64)를 사용하세요. x86-64에서는 64바이트가 표준입니다.

Q. 프리페치를 넣었는데 효과가 없습니다.

A. 순차 접근에서는 CPU가 이미 예측하므로 프리페치가 불필요합니다. 랜덤 접근·포인터 체이닝에서만 시도하며, 거리(4~16 요소)를 실험해 보세요.

같이 보면 좋은 글

• C++ 프로파일러 비교
• C++ SIMD 최적화: SSE·AVX2·AVX-512·NEON 인트린직, 자동 벡터화, C++26 std::simd
• C++ 데이터 지향 설계 실전 | SoA·캐시 친화적 레이아웃·ECS·핫/콜드 분리 가이드
• C++ 캐시 효율적인 코드: 데이터 지향 설계 가이드
• C++ 캐시 친화 코드: AoS vs SoA, 데이터 지향 설계, False Sharing

---