pkglog
EN

C++ 캐시 친화 코드: AoS vs SoA, 데이터 지향 설계, False Sharing

작성 · · 32분 읽기 · 수정 중급 개념

💡 초보자를 위한 한 줄: 캐시는 “가까운 메모리를 연속으로 읽을수록” 유리합니다. 핫 루프에서 건드리는 필드만 모으려면 SoA를, 객체 단위로 다루면 AoS를 먼저 떠올리면 됩니다. 멀티스레드에선 false sharing(같은 캐시 라인 경쟁)을 한 번 의심하세요. 15-1 프로파일링 다음이 읽기 순서에 맞습니다.

CPU는 메모리를 64바이트(Apple Silicon은 128바이트) 캐시 라인 단위로 가져옵니다. 이 글은 가져온 바이트를 최대한 쓰도록 접근 순서와 데이터 배치를 바꾸는 방법, 즉 행 우선 순회, 구조체 레이아웃, AoS와 SoA, false sharing, 프리페치를 차례로 다룹니다. 효과는 데이터 크기와 접근 패턴에 크게 좌우되므로, 여기 나온 기법은 perf로 캐시 미스를 확인한 루프에만 적용하는 것을 전제로 합니다.

들어가며: 같은 연산인데 순회 방향만으로 달라지는 속도

2차원 배열을 순회하는 코드를 작성했습니다. 순회 방향만 바꿨는데 실행 시간이 크게 달라졌습니다.
CPU는 메모리를 캐시 라인(cache line—CPU 캐시가 한 번에 가져오는 메모리 블록 단위, 보통 64바이트) 단위로 가져오기 때문에, 접근 순서가 “연속된 주소”를 따라가면 캐시 히트(필요한 데이터가 캐시에 있어 빠르게 접근)가 많아지고, 건너뛰며 접근하면 캐시 미스(캐시에 없어 메인 메모리에서 가져와야 함)가 늘어납니다. 행 우선 순회, 구조체 정렬, 연관된 데이터를 한 덩어리로 두는 식의 데이터 지역성(data locality—자주 쓰는 데이터를 가까이·연속으로 두어 캐시 효율을 높이는 것)을 신경 쓰면, 같은 연산이라도 훨씬 빨라질 수 있습니다.

느린 코드:

static int matrix[4096][4096];   // 64MB: 캐시보다 확실히 크게
// ❌ 열 우선 순회 (느림)
for (int col = 0; col < 4096; ++col) {
    for (int row = 0; row < 4096; ++row) {
        sum += matrix[row][col];  // 한 번 읽을 때마다 다른 캐시 라인
    }
}

빠른 코드:

// 복사해 붙여넣은 뒤: g++ -std=c++17 -O2 -o cache_fast cache_fast.cpp && ./cache_fast
#include <iostream>
#include <chrono>
static int matrix[4096][4096];   // 전역(static): 지역 배열로 두면 스택 오버플로
int main() {
    for (int r = 0; r < 4096; ++r)
        for (int c = 0; c < 4096; ++c) matrix[r][c] = r ^ c;   // 0이면 컴파일러가 합을 미리 계산할 수 있음
    long long sum = 0;
    auto start = std::chrono::high_resolution_clock::now();
    // ✅ 행 우선 순회 (빠름)
    for (int row = 0; row < 4096; ++row) {
        for (int col = 0; col < 4096; ++col) {
            sum += matrix[row][col];  // 연속 주소: 캐시 라인 하나로 16번 접근
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "sum=" << sum << " time=" << ms << "ms\n";
    return 0;
}

실행 결과: sum=... time=Nms 형태로 출력됩니다 (환경에 따라 N 값은 다름). 원인: CPU 캐시는 연속된 메모리를 미리 가져옴

이 예제를 처음 작성할 때 int matrix[1000][1000] = {};를 main 안에 지역 변수로 두었다가, 리눅스에서는 잘 돌던 코드가 Windows에서 바로 스택 오버플로로 죽은 적이 있습니다. 4MB 배열은 리눅스 기본 스택(8MB)에는 들어가지만 Windows 기본 스택(1MB)에는 들어가지 않습니다. 큰 배열은 static이나 std::vector로 두세요. 또 배열 크기가 L3 캐시에 다 들어갈 정도로 작으면 열 우선 순회도 캐시에서 대부분 해결돼 차이가 작게 나오고, GCC -O3는 경우에 따라 루프 순서를 스스로 바꾸기도(loop interchange) 해서 “순서를 바꿔도 똑같다”는 결과가 나올 수 있습니다. 차이를 확인하려면 캐시보다 충분히 큰 데이터로, 최적화 옵션을 고정해 재야 합니다.

메모리 계층과 캐시 히트·미스

메모리 계층

CPU Register    < 1ns    (가장 빠름)
    ↓
L1 Cache        ~1ns     (32-64KB)
    ↓
L2 Cache        ~3ns     (256KB-1MB)
    ↓
L3 Cache        ~10ns    (8-32MB)
    ↓
RAM             ~100ns   (수 GB)
    ↓
SSD             ~100us   (수백 GB)
    ↓
HDD             ~10ms    (수 TB, 가장 느림)

캐시 라인: 보통 64바이트 단위로 메모리를 가져옴

메모리 계층 시각화

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

캐시 히트 vs 미스

int arr[1000];
// 캐시 히트: 연속 접근
for (int i = 0; i < 1000; ++i) {
    sum += arr[i];  // 빠름
}
// 캐시 미스: 불규칙 접근
for (int i = 0; i < 1000; i += 64) {
    sum += arr[i];  // 느림 (캐시 라인 낭비)
}

코드 상세 설명: 캐시 히트 (연속 접근):

  • arr[0], arr[1], arr[2], … 순서대로 접근합니다.
  • 캐시 라인은 보통 64바이트(int 16개)를 한 번에 가져옵니다.
  • arr[0]을 읽을 때 arr[0]~arr[15]가 캐시에 함께 로드됩니다.
  • 다음 15번의 접근은 캐시 히트 (매우 빠름, ~1ns).
  • 결과: 1000번 접근 중 약 62번만 메모리에서 가져옴 (1000/16). 캐시 미스 (건너뛰는 접근):
  • arr[0], arr[64], arr[128], … 64칸(256바이트)씩 건너뜁니다.
  • 접근할 때마다 다른 캐시 라인이라, 가져온 64바이트 중 4바이트만 쓰고 나머지는 버립니다.
  • 두 번째 루프는 접근 횟수 자체는 1/64이지만, 접근 한 번당 비용은 첫 번째 루프보다 훨씬 큽니다. 첫 번째 루프는 16번에 한 번만 새 캐시 라인을 가져오고, 나머지 15번은 L1에서 끝납니다.

같은 양의 데이터를 처리할 때 가져온 캐시 라인을 얼마나 알차게 쓰느냐가 속도를 정한다는 것이 이 절의 요점입니다. 다만 1000개짜리 배열(4KB)은 L1에 통째로 들어가서 두 번째 반복부터는 어떤 순서든 빠르므로, 실제 차이는 데이터가 캐시보다 클 때 드러납니다. 하드웨어 프리페처는 일정한 간격(stride)으로 건너뛰는 접근도 어느 정도 예측하기 때문에, 진짜로 느린 것은 rand()나 포인터를 따라가는 예측할 수 없는 접근입니다.

시간적 지역성과 공간적 지역성

시간적 지역성 (Temporal Locality)

// ✅ 좋은 예: 같은 데이터 반복 접근
int sum = 0;
for (int i = 0; i < 100; ++i) {
    sum += data[0];  // data[0]이 캐시에 유지됨
}
// ❌ 나쁜 예: 매번 다른 데이터
for (int i = 0; i < 100; ++i) {
    sum += data[rand() % 10000];  // 캐시 미스 많음
}

공간적 지역성 (Spatial Locality)

struct Point {
    int x, y, z;
};
std::vector<Point> points(1000);
// ✅ 좋은 예: 연속 접근
for (const auto& p : points) {
    sum += p.x + p.y + p.z;  // 캐시 친화적
}
// ❌ 나쁜 예: 포인터 체이싱
struct Node {
    int value;
    Node* next;
};
Node* head = /* ... */;
for (Node* p = head; p != nullptr; p = p->next) {
    sum += p->value;  // 캐시 미스 많음
}

연속 메모리와 행 우선 순회로 캐시 미스 줄이기

패턴 1: 연속 메모리 사용

// ❌ 나쁜 예: 링크드 리스트 (캐시 미스)
std::list<int> data;
for (int val : data) {
    sum += val;  // 노드마다 캐시 미스
}
// ✅ 좋은 예: 벡터 (캐시 친화적)
std::vector<int> data;
for (int val : data) {
    sum += val;  // 연속 메모리, 캐시 히트
}

패턴 2: 행 우선 순회

const int N = 1000;
int matrix[N][N];
// ❌ 열 우선 (느림)
for (int col = 0; col < N; ++col) {
    for (int row = 0; row < N; ++row) {
        matrix[row][col] = 0;  // 캐시 미스
    }
}
// ✅ 행 우선 (빠름)
for (int row = 0; row < N; ++row) {
    for (int col = 0; col < N; ++col) {
        matrix[row][col] = 0;  // 캐시 히트
    }
}

코드 상세 설명: C++ 2차원 배열의 메모리 배치:

  • int matrix[N][N]은 행 우선(row-major) 으로 메모리에 저장됩니다.
  • 메모리 순서: matrix[0][0], matrix[0][1], …, matrix[0][N-1], matrix[1][0], …
  • 같은 행의 요소들이 메모리상에서 연속적으로 배치됩니다. 열 우선 순회 (느림):
접근 순서: matrix[0][0] → matrix[1][0] → matrix[2][0] → ...
메모리 순서: [0][0] [0][1] [0][2] ... [1][0] [1][1] ...
  • matrix[0][0]을 읽으면 matrix[0][0]~[0][15]가 캐시에 로드됩니다.
  • 하지만 다음에 matrix[1][0]을 접근하므로 1000 * 4바이트 = 4KB 떨어진 위치를 읽습니다.
  • 캐시에 로드된 matrix[0][1]~[0][15]는 사용하지 않고 버려집니다.
  • 결과: 거의 모든 접근이 캐시 미스 (매우 느림). 행 우선 순회 (빠름):
접근 순서: matrix[0][0] → matrix[0][1] → matrix[0][2] → ...
메모리 순서: [0][0] [0][1] [0][2] ... (일치!)
  • matrix[0][0]을 읽으면 matrix[0][0]~[0][15]가 캐시에 로드됩니다.
  • 다음 15번의 접근(matrix[0][1]~[0][15])은 모두 캐시 히트.
  • 결과: 16번 중 1번만 캐시 미스 (매우 빠름). 성능 차이 (1000x1000 행렬):
  • 열 우선: 최악의 경우 원소마다 캐시 미스 (약 1,000,000번)
  • 행 우선: 캐시 라인당 한 번 (약 62,500번)
  • 실제 시간 차이는 CPU·캐시 크기·컴파일 옵션에 따라 다르므로 행 우선과 열 우선 순회 벤치마크의 코드로 직접 측정해 보세요. 실무 팁: 행렬 곱셈, 이미지 처리 등에서 순회 순서를 잘못 정하면 성능이 크게 떨어집니다.

패딩 최소화와 핫/콜드 데이터 분리

패딩 최소화

// ❌ 나쁜 예: 패딩 많음 (12바이트)
struct Bad {
    char c1;    // 1바이트
    // 3바이트 패딩
    int i;      // 4바이트
    char c2;    // 1바이트
    // 3바이트 패딩 (배열에서 다음 원소의 int 정렬을 위해)
};
static_assert(sizeof(Bad) == 12);
// ✅ 좋은 예: 큰 멤버부터 (8바이트)
struct Good {
    int i;      // 4바이트
    char c1;    // 1바이트
    char c2;    // 1바이트
    // 2바이트 패딩
};
static_assert(sizeof(Good) == 8);

x86-64와 ARM64의 일반적인 ABI 기준입니다. 구조체 크기가 줄면 캐시 라인 하나에 들어가는 원소 수가 늘어납니다(64바이트 기준 5개 → 8개). 크기를 확인할 때는 static_assert(sizeof(T) == N)을 두거나, pahole(dwarves 패키지)로 바이너리의 실제 구조체 배치와 구멍(hole)을 볼 수 있습니다. GCC·Clang의 -Wpadded는 패딩이 들어가는 곳마다 경고를 내 줍니다.

핫/콜드 데이터 분리

// ❌ 나쁜 예: 자주 쓰는 데이터와 안 쓰는 데이터 섞임
struct Entity {
    int id;              // 자주 사용
    float x, y, z;       // 자주 사용
    std::string name;    // 가끔 사용
    std::string description;  // 거의 안 사용
};
// ✅ 좋은 예: 핫 데이터만 분리
struct EntityHot {
    int id;
    float x, y, z;
};
struct EntityCold {
    std::string name;
    std::string description;
};
std::vector<EntityHot> hotData;
std::vector<EntityCold> coldData;   // 같은 인덱스로 대응 (map보다 캐시·메모리 효율적)

std::string은 구현에 따라 객체 하나가 24~32바이트라서, Entity에 두 개만 들어가도 핫 필드(16바이트)보다 콜드 필드가 훨씬 큰 구조체가 됩니다. 위치만 갱신하는 루프가 이 구조체 배열을 돌면, 가져온 캐시 라인의 대부분이 한 번도 읽지 않는 문자열 객체로 채워집니다. 분리하고 나면 핫 배열은 원소당 16바이트라 캐시 라인 하나에 4개가 들어갑니다.

AoS와 SoA 비교 예제

메모리 배치 비교

flowchart LR
    subgraph AoS["AoS: 구조체 배열"]
        direction TB
        A1["x0 y0 z0 vx0 vy0 vz0 r0 g0 b0"]
        A2["x1 y1 z1 vx1 vy1 vz1 r1 g1 b1"]
        A1 --> A2
    end
    subgraph SoA["SoA: 배열의 구조체"]
        direction TB
        S1["x: x0 x1 x2 ..."]
        S2["vx: vx0 vx1 vx2 ..."]
        S3["r: r0 r1 r2 ..."]
        S1 --> S2 --> S3
    end

AoS (Array of Structures) — 구조체 배열

#include <vector>
#include <chrono>
#include <iostream>
struct ParticleAoS {
    float x, y, z;      // 위치 (12바이트)
    float vx, vy, vz;   // 속도 (12바이트)
    float r, g, b;      // 색상 (12바이트)
    // 총 36바이트
};
void updatePositionsAoS(std::vector<ParticleAoS>& particles) {
    for (auto& p : particles) {
        p.x += p.vx;
        p.y += p.vy;
        p.z += p.vz;
    }
}
int main() {
    std::vector<ParticleAoS> particles(100000);
    // 초기화...
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 100; ++i) {
        updatePositionsAoS(particles);
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "AoS: " << ms << " ms\n";
    return 0;
}

AoS 메모리 배치:

메모리: [x0,y0,z0,vx0,vy0,vz0,r0,g0,b0][x1,y1,z1,vx1,vy1,vz1,r1,g1,b1]...
        ↑ 36바이트 (9 floats)      ↑ 36바이트
캐시 라인(64B)에 약 1.8개 파티클 → 위치·속도(24B)만 쓰는데 색상(12B)까지 로드됨

SoA (Structure of Arrays) — 배열의 구조체

struct ParticleSystemSoA {
    std::vector<float> x, y, z;
    std::vector<float> vx, vy, vz;
    std::vector<float> r, g, b;
    void resize(size_t n) {
        x.resize(n); y.resize(n); z.resize(n);
        vx.resize(n); vy.resize(n); vz.resize(n);
        r.resize(n); g.resize(n); b.resize(n);
    }
    size_t size() const { return x.size(); }
};
void updatePositionsSoA(ParticleSystemSoA& particles) {
    const size_t n = particles.size();
    for (size_t i = 0; i < n; ++i) {
        particles.x[i] += particles.vx[i];
        particles.y[i] += particles.vy[i];
        particles.z[i] += particles.vz[i];
    }
}

SoA 메모리 배치:

x 배열:  [x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,...]
vx 배열: [vx0,vx1,vx2,vx3,vx4,vx5,vx6,vx7,vx8,vx9,vx10,vx11,...]
r 배열:  [r0,r1,r2,r3,r4,r5,r6,r7,r8,r9,r10,r11,r12,r13,r14,r15,...]
캐시 라인(64B)에 16개 float → x[i] 읽을 때 x[i]~x[i+15] 모두 활용

이 예제에서 기대할 수 있는 이득을 정확히 계산해 보면, AoS는 파티클당 36바이트를 가져와서 24바이트(위치·속도)를 쓰므로 활용률이 약 67%입니다. SoA는 쓰는 6개 배열만 가져오므로 100%입니다. 메모리 대역폭만 따지면 약 1.5배 차이이고, “SoA가 5~10배 빠르다”는 수치는 이 예제에서는 나오지 않습니다. SoA의 이득이 크게 나는 것은 구조체가 크고 루프가 그중 일부만 쓸 때(예: 200바이트짜리 엔티티에서 위치 12바이트만 갱신)와, 같은 필드가 연속으로 놓여 컴파일러가 루프를 SIMD로 벡터화할 수 있게 될 때입니다. 저도 처음 SoA로 바꿨을 때 기대만큼 빨라지지 않아 의아했는데, 원래 구조체가 작아서 활용률이 이미 높았던 경우였습니다. 바꾸기 전에 핫 루프가 구조체의 몇 퍼센트를 쓰는지부터 계산해 보는 것이 좋습니다.

AoS vs SoA 선택 가이드

상황권장이유
같은 필드만 대량 처리 (위치 업데이트)SoA캐시 효율 최대
한 객체의 여러 필드를 함께 사용AoS코드 단순
SIMD 벡터화 적용SoA4/8개씩 병렬 처리 용이
개별 엔티티 조회·수정AoS인덱스 하나로 접근

False Sharing (가짜 공유)

False Sharing 발생 원리

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

한 스레드가 counter[0]을 수정하면 같은 캐시 라인에 있는 counter[1], counter[2]의 캐시가 무효화되어, 다른 코어는 매번 그 캐시 라인의 소유권을 다시 가져와야 합니다(캐시 일관성 프로토콜). 변수 자체는 공유하지 않는데 캐시 라인을 공유해서 생기는 경쟁이라 “가짜 공유”라고 부릅니다.

문제: 같은 캐시 라인을 여러 스레드가 수정

#include <thread>
#include <vector>
#include <atomic>
#include <chrono>
#include <iostream>
// ❌ 나쁜 예: false sharing 발생
void badParallelCounter() {
    const int numThreads = 4;
    std::vector<int> counters(numThreads, 0);  // 4개 int = 16바이트, 같은 캐시 라인!
    std::vector<std::thread> threads;
    for (int t = 0; t < numThreads; ++t) {
        threads.emplace_back([&counters, t]() {
            for (int i = 0; i < 10000000; ++i) {
                counters[t]++;  // 다른 스레드의 캐시 라인 무효화 유발 (최적화에 따라 다름, 아래 참고)
            }
        });
    }
    for (auto& th : threads) th.join();
}

원인: counters[0], counters[1], … 가 64바이트 캐시 라인 안에 같이 들어가면, 한 스레드가 counters[0]을 수정할 때마다 해당 캐시 라인이 무효화되고, counters[1]을 쓰는 다른 스레드는 매번 캐시 라인을 다시 가져와야 합니다.

측정할 때 주의: 이 코드를 -O2로 빌드하면 컴파일러가 루프 안에서 counters[t]를 레지스터에 두고 마지막에 한 번만 메모리에 쓰도록 바꿀 수 있습니다. 그러면 false sharing이 거의 일어나지 않아 “정렬해도 차이가 없다”는 결과가 나옵니다. 실제 코드에서 false sharing이 문제 되는 것은 주로 std::atomic 카운터, 락, 다른 스레드가 읽어야 해서 매번 메모리에 써야 하는 상태 값이므로, 벤치마크도 아래처럼 std::atomic(relaxed)으로 재는 것이 현실적입니다.

해결: 캐시 라인 정렬

#include <cstddef>
// ✅ 좋은 예: 캐시 라인 경계에 정렬
struct alignas(64) CacheLineAlignedCounter {
    int value;
    char padding[64 - sizeof(int)];  // 같은 캐시 라인 공유 방지
};
void goodParallelCounter() {
    const int numThreads = 4;
    std::vector<CacheLineAlignedCounter> counters(numThreads);
    std::vector<std::thread> threads;
    for (int t = 0; t < numThreads; ++t) {
        threads.emplace_back([&counters, t]() {
            for (int i = 0; i < 10000000; ++i) {
                counters[t].value++;
            }
        });
    }
    for (auto& th : threads) th.join();
}

C++17 alignas 활용

#include <new>   // std::hardware_destructive_interference_size

// 각 카운터가 별도 캐시 라인에 배치
struct alignas(64) ThreadLocalCounter {
    std::atomic<int64_t> count{0};
};
void benchmarkCounters() {
    const int numThreads = 4;
    std::vector<ThreadLocalCounter> counters(numThreads);
    auto start = std::chrono::high_resolution_clock::now();
    std::vector<std::thread> threads;
    for (int t = 0; t < numThreads; ++t) {
        threads.emplace_back([&counters, t]() {
            for (int i = 0; i < 10000000; ++i) {
                counters[t].count.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 << "Aligned: " << ms << " ms\n";
}

성능 차이: 코어 수와 CPU 구조에 따라 다르지만, 여러 코어가 같은 캐시 라인에 계속 쓰는 경우 정렬만으로 몇 배 빨라지는 것이 드물지 않습니다.

캐시 라인 크기를 64로 고정해도 될까? x86-64는 64바이트가 사실상 표준이지만, Apple Silicon(M 시리즈)은 L2 기준 128바이트 캐시 라인을 씁니다. 64로 정렬하면 두 카운터가 여전히 같은 128바이트 라인에 들어갈 수 있어 맥에서는 false sharing이 남습니다. C++17의 std::hardware_destructive_interference_size는 이런 차이를 담으려고 만든 상수인데, 컴파일 옵션(-mtune)에 따라 값이 달라질 수 있어 헤더의 구조체 레이아웃에 쓰면 ABI가 흔들린다는 문제가 있고, GCC는 이를 -Winterference-size 경고로 알려 줍니다. 실무에서는 대상 플랫폼별로 상수를 정해 두거나, 여유 있게 128바이트로 정렬하는 방식을 많이 씁니다. 메모리를 조금 더 쓰는 대신 x86과 ARM 모두에서 안전합니다.

가장 좋은 방법은 공유 자체를 줄이는 것입니다. 스레드마다 지역 변수에 누적하고, 작업이 끝날 때 한 번만 공유 변수에 더하면 정렬을 신경 쓸 필요가 없습니다.

threads.emplace_back([&total, t]() {
    std::int64_t local = 0;             // 스레드 전용, 레지스터나 스택에 있음
    for (int i = 0; i < 10000000; ++i) ++local;
    total.fetch_add(local, std::memory_order_relaxed);   // 공유 변수 접근은 한 번
});

false sharing이 의심되면 리눅스의 perf c2c record ./app → perf c2c report가 여러 코어 사이를 오가는(HITM) 캐시 라인과 그 라인을 건드린 코드 위치를 직접 보여 줍니다.

프리페치로 링크드 리스트와 간접 접근 가속

기본 사용법

#include <xmmintrin.h>  // _mm_prefetch (또는 GCC/Clang: __builtin_prefetch)
void processWithPrefetch(const std::vector<int>& data) {
    const size_t n = data.size();
    const int PREFETCH_DISTANCE = 8;  // 몇 요소 앞을 미리 로드할지
    for (size_t i = 0; i < n; ++i) {
        // 다음에 쓸 블록 미리 캐시에 로드
        if (i + PREFETCH_DISTANCE < n) {
            __builtin_prefetch(&data[i + PREFETCH_DISTANCE], 0, 3);
            // 인자: (주소, 0=읽기, 3=모든 캐시 레벨)
        }
        process(data[i]);
    }
}

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

struct Node {
    int value;
    Node* next;
};
int sumListWithPrefetch(Node* head) {
    int sum = 0;
    Node* curr = head;
    while (curr != nullptr) {
        // 다음 노드 미리 로드 (포인터 따라가기 전에)
        if (curr->next != nullptr) {
            __builtin_prefetch(curr->next, 0, 3);
        }
        sum += curr->value;
        curr = curr->next;
    }
    return sum;
}

인덱스 배열 따라가기

// indices[i]가 data의 인덱스 → data[indices[i]] 접근
void gatherWithPrefetch(const std::vector<float>& data,
                        const std::vector<size_t>& indices) {
    const size_t n = indices.size();
    float sum = 0;
    for (size_t i = 0; i < n; ++i) {
        if (i + 4 < n) {
            __builtin_prefetch(&data[indices[i + 4]], 0, 3);
        }
        sum += data[indices[i]];
    }
}

주의: 프리페치 거리를 너무 크게 하면 캐시에서 밀려나고, 너무 작으면 효과가 없습니다. 적절한 거리는 “메모리 지연 시간 ÷ 반복 한 번의 시간”으로 정해지므로 루프마다 다르고, 실험으로 찾아야 합니다.

어디에 효과가 있나: 첫 번째 예제처럼 배열을 순서대로 읽는 경우는 CPU의 하드웨어 프리페처가 이미 알아서 다음 캐시 라인을 가져오므로, 소프트웨어 프리페치를 넣어도 거의 이득이 없고 명령만 늘어납니다. 링크드 리스트 예제도 다음 노드 주소를 알게 되는 시점이 바로 직전이라 프리페치가 지연 시간을 숨길 여유가 거의 없습니다. 소프트웨어 프리페치가 실제로 효과를 내는 것은 세 번째 예제처럼 주소를 몇 단계 앞서 계산할 수 있는 간접 접근(data[indices[i + k]], 해시 테이블 버킷 일괄 조회)입니다.

타일링, 루프 융합, 정렬로 지역성 개선

패턴 1: 블록(타일) 단위 처리

1차원 배열을 순서대로 한 번 읽는 루프는 블록으로 나눠도 달라지는 것이 없습니다. 블로킹이 효과를 내는 것은 같은 데이터를 여러 번 다시 쓰는데, 한 방향의 접근이 캐시를 벗어나는 경우입니다. 대표적인 예가 행렬 전치입니다. dst[j][i] = src[i][j]는 한쪽이 행 우선이면 다른 쪽은 반드시 열 우선이 되므로, 작은 타일 안에서만 처리해 타일이 캐시에 머무는 동안 양쪽을 모두 끝냅니다.

constexpr int TILE = 32;   // 32x32 float 타일 = 4KB, L1에 여유 있게 들어감
void transpose_tiled(const float* src, float* dst, int n) {
    for (int ii = 0; ii < n; ii += TILE)
        for (int jj = 0; jj < n; jj += TILE)
            for (int i = ii; i < std::min(ii + TILE, n); ++i)
                for (int j = jj; j < std::min(jj + TILE, n); ++j)
                    dst[j * n + i] = src[i * n + j];
}

행렬 곱셈, 이미지 필터, 스텐실 연산도 같은 원리입니다. 타일 크기는 L1·L2 크기에 맞춰 실험으로 정합니다.

패턴 2: 루프 융합

std::vector<int> data(10000);
// ❌ 나쁜 예: 여러 번 순회
for (int& val : data) {
    val *= 2;
}
for (int& val : data) {
    val += 10;
}
// ✅ 좋은 예: 한 번만 순회
for (int& val : data) {
    val *= 2;
    val += 10;
}

패턴 3: 정렬로 지역성 개선

struct Entity {
    int type;
    // 데이터...
};
std::vector<Entity> entities;
// 타입별로 정렬
std::sort(entities.begin(), entities.end(),
          [](const Entity& a, const Entity& b) {
              return a.type < b.type;
          });
// 같은 타입끼리 연속 처리 (캐시 친화적)
for (const auto& e : entities) {
    processType(e.type, e);
}

패턴 4: 데이터 재배치 (SoA)

// ❌ 나쁜 예: AoS (Array of Structures)
struct Particle {
    float x, y, z;     // 위치
    float vx, vy, vz;  // 속도
    float r, g, b;     // 색상
};
std::vector<Particle> particles(10000);
// 위치만 업데이트 (색상도 캐시에 로드되며, 낭비)
for (auto& p : particles) {
    p.x += p.vx;
    p.y += p.vy;
    p.z += p.vz;
}
// ✅ 좋은 예: SoA (Structure of Arrays)
struct ParticleSystem {
    std::vector<float> x, y, z;
    std::vector<float> vx, vy, vz;
    std::vector<float> r, g, b;
};
ParticleSystem particles;
particles.x.resize(10000);
// ...
// 위치만 업데이트 (위치 데이터만 캐시에 로드)
for (size_t i = 0; i < particles.x.size(); ++i) {
    particles.x[i] += particles.vx[i];
    particles.y[i] += particles.vy[i];
    particles.z[i] += particles.vz[i];
}

SoA 상세 설명:

  • AoS의 문제: 파티클 하나가 36바이트라 캐시 라인(64바이트)에 1.8개 정도 들어갑니다. 위치 갱신 루프는 이 중 위치·속도 24바이트만 쓰므로, 가져온 데이터의 약 1/3(색상)이 낭비됩니다.
  • SoA의 장점: 루프가 쓰는 6개 배열만 캐시로 가져오므로 가져온 바이트를 전부 씁니다. 또 x[i] += vx[i]가 연속된 float 배열 연산이 되어 컴파일러가 SIMD로 벡터화하기 쉽습니다.
  • 성능 향상: 이 예제에서는 메모리 전송량 기준 약 1.5배가 상한이고, 벡터화 이득이 더해질 수 있습니다. 10,000개(파티클당 36바이트, 360KB)는 L2나 L3에 들어가는 크기라 반복 실행 시에는 차이가 더 작게 나올 수 있습니다.

열 우선 순회, false sharing, 과도한 프리페치 문제

에러 1: 열 우선 순회로 인한 극심한 저하

증상: 2D 배열 처리가 예상보다 훨씬 느림. 원인: C/C++ 배열은 행 우선 저장인데 열 우선으로 순회함. 해결:

// ❌ 잘못된 순서
for (int col = 0; col < COLS; ++col)
    for (int row = 0; row < ROWS; ++row)
        process(matrix[row][col]);
// ✅ 올바른 순서 (행 우선)
for (int row = 0; row < ROWS; ++row)
    for (int col = 0; col < COLS; ++col)
        process(matrix[row][col]);

에러 2: False sharing으로 멀티스레드가 느려짐

증상: 스레드 수를 늘렸는데 오히려 느려짐. 원인: 서로 다른 스레드가 같은 캐시 라인에 있는 변수를 수정함. 해결:

// ❌ 같은 캐시 라인 공유
std::atomic<int> counters[8];
// ✅ 캐시 라인 정렬
struct alignas(64) AlignedCounter {
    std::atomic<int> value{0};
};
std::vector<AlignedCounter> counters(8);

에러 3: 프리페치 과다로 성능 저하

증상: __builtin_prefetch를 넣었는데 오히려 느려짐. 원인: 너무 먼 미래 데이터를 프리페치해 유효 데이터가 캐시에서 밀려남. 해결:

// ❌ 거리 너무 큼 (캐시 오염)
__builtin_prefetch(&data[i + 64], 0, 3);
// ✅ 적절한 거리 (4~16)
__builtin_prefetch(&data[i + 8], 0, 3);

에러 4: SoA와 AoS 혼용 시 인덱스 불일치

증상: SoA로 전환 후 일부 파티클이 잘못된 데이터를 참조함. 원인: resize 시 일부 배열만 크기 변경하거나, 인덱스 계산 오류. 해결:

// ✅ SoA 크기 일관성 유지
struct ParticleSystem {
    std::vector<float> x, y, z, vx, vy, vz;
    void resize(size_t n) {
        x.resize(n); y.resize(n); z.resize(n);
        vx.resize(n); vy.resize(n); vz.resize(n);
    }
};

에러 5: list 대신 vector를 써야 할 곳

증상: std::list 순회가 std::vector보다 훨씬 느림. 원인: list는 노드가 흩어져 있어 캐시 미스가 많음. 해결:

// ❌ 순회만 할 때 list
std::list<int> items;
for (auto v : items) sum += v;
// ✅ 순회 위주면 vector
std::vector<int> items;
for (auto v : items) sum += v;

행 우선과 열 우선 순회 벤치마크

벤치마크 1: 행 우선 vs 열 우선

#include <iostream>
#include <chrono>
const int N = 4096;
int matrix[N][N];
void benchmarkRowMajor() {
    long long sum = 0;
    auto start = std::chrono::high_resolution_clock::now();
    for (int row = 0; row < N; ++row) {
        for (int col = 0; col < N; ++col) {
            sum += matrix[row][col];
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "Row-major: " << ms << " ms (sum=" << sum << ")\n";
}
void benchmarkColMajor() {
    long long sum = 0;
    auto start = std::chrono::high_resolution_clock::now();
    for (int col = 0; col < N; ++col) {
        for (int row = 0; row < N; ++row) {
            sum += matrix[row][col];
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "Col-major: " << ms << " ms (sum=" << sum << ")\n";
}
int main() {
    // 행렬을 0이 아닌 값으로 채운 뒤 실행 (0이면 합을 미리 계산해 루프가 사라질 수 있음)
    benchmarkRowMajor();
    benchmarkColMajor();
}

이 글에는 특정 수치를 적지 않았습니다. 같은 코드도 CPU, 메모리, 컴파일러 버전, 데이터 크기에 따라 배율이 몇 배씩 달라지기 때문입니다. 대신 측정할 때 확인할 것을 정리하면 이렇습니다.

  • 데이터 크기: 캐시(특히 L3)보다 작으면 두 번째 반복부터는 어떤 배치든 캐시에서 읽어 차이가 줄어듭니다. 실제 서비스의 데이터 크기로 재세요.
  • 컴파일러의 개입: 결과를 쓰지 않으면 루프가 사라지고, -O3는 루프 순서를 바꾸거나 벡터화해 “수동 최적화 전”과 “후”의 차이를 지웁니다. 비교하려는 변환 외에는 조건을 고정합니다.
  • 카운터로 원인 확인: 시간만 보지 말고 perf stat -e cycles,instructions,cache-misses,LLC-load-misses ./bench로 캐시 미스 수가 실제로 줄었는지 확인하면, 빨라진 이유가 캐시인지 벡터화인지 구분됩니다.
  • list vs vector: std::list를 한꺼번에 만든 직후에는 노드가 메모리에 거의 연속으로 할당되어 순회가 생각보다 빠르게 나옵니다. 실제 프로그램처럼 삽입·삭제를 섞어 노드가 흩어진 뒤에 재야 차이가 드러납니다.

ECS 스타일 SoA와 데이터 지향 설계

패턴 1: ECS (Entity-Component-System) 스타일 SoA

// 게임 엔진에서 흔한 패턴
struct TransformComponent {
    std::vector<float> x, y, z;
    std::vector<float> rotX, rotY, rotZ;
};
struct RenderComponent {
    std::vector<uint32_t> textureId;
    std::vector<float> r, g, b, a;
};
void updateTransforms(TransformComponent& tf, float dt) {
    for (size_t i = 0; i < tf.x.size(); ++i) {
        tf.x[i] += 0.1f * dt;  // 위치만 연속 접근
        tf.y[i] += 0.1f * dt;
        tf.z[i] += 0.1f * dt;
    }
}

패턴 2: 캐시 라인 크기 상수화

namespace cache {
    constexpr size_t LINE_SIZE = 64;
    constexpr size_t L1_SIZE = 32 * 1024;
    constexpr size_t L2_SIZE = 256 * 1024;
}
template<typename T>
struct alignas(cache::LINE_SIZE) CacheLineAligned {
    T value;
};

패턴 3: 프로파일링 후 최적화

// 1. 프로파일러로 캐시 미스 확인 (perf, VTune)
// 2. 캐시 미스 많은 루프 식별
// 3. 순회 순서, SoA 전환, 프리페치 적용
// 4. 벤치마크로 검증

패턴 4: 데이터 지향 설계 체크리스트

- [ ] 연속 메모리 사용 (vector > list)
- [ ] 행 우선 순회 (2D 배열)
- [ ] SoA 고려 (같은 필드 대량 처리 시)
- [ ] 핫/콜드 분리 (자주 쓰는 필드만 묶기)
- [ ] 멀티스레드 시 캐시 라인 정렬 (false sharing 방지)
- [ ] 프리페치 실험 (포인터 체이닝, 인덱스 배열)

성능 비교 요약

최적화효과가 큰 조건적용 난이도
행 우선 순회데이터가 캐시보다 클 때, 열 방향 접근을 없앨 수 있을 때쉬움
패딩·핫/콜드 분리구조체가 크고 핫 루프가 일부 필드만 쓸 때쉬움
SoA 전환루프가 구조체의 작은 일부만 쓰고, 벡터화 여지가 있을 때중간
False sharing 제거여러 코어가 인접한 변수에 계속 쓸 때쉬움
list → vector순회가 많고 중간 삽입·삭제가 적을 때쉬움
소프트웨어 프리페치주소를 미리 계산할 수 있는 간접 접근중간
타일링같은 데이터를 여러 방향으로 재사용할 때 (전치, 행렬 곱)중간

자주 묻는 질문 (FAQ)

Q. std::unordered_map이 느린 것도 캐시 때문인가요?

A. 상당 부분 그렇습니다. 표준 std::unordered_map은 버킷마다 노드를 따로 할당하는 체이닝 구조라, 조회할 때 버킷 배열 → 노드 → 값으로 포인터를 여러 번 따라가며 캐시 미스가 납니다. 조회가 핫 경로라면 연속 메모리에 원소를 두는 오픈 어드레싱 해시맵(Abseil의 flat_hash_map, Boost.Unordered의 boost::unordered_flat_map 등)이 캐시 측면에서 훨씬 유리합니다. 원소 수가 작다면 정렬된 std::vector에 이진 탐색이 더 빠른 경우도 많습니다.

관련 글