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

작성 0xmote · 2026년 2월 28일 · 27분 읽기 · 수정 2026년 10월 18일 중급 개념

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

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

큰 2차원 배열의 합을 구하는 두 루프는 더하는 원소도, 덧셈 횟수도 같지만 순회 방향만 다르면 실행 시간이 크게 달라질 수 있습니다. CPU는 메모리를 캐시 라인(cache line, CPU 캐시가 한 번에 가져오는 메모리 블록) 단위로 가져오기 때문에, 접근 순서가 연속된 주소를 따라가면 필요한 데이터가 이미 캐시에 있는 캐시 히트가 많아지고, 건너뛰며 접근하면 메인 메모리까지 가야 하는 캐시 미스가 늘어납니다. 자주 쓰는 데이터를 가까이, 연속으로 두는 것을 데이터 지역성(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::steady_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::steady_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은 환경마다 다릅니다.

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

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

메모리 계층

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

수치는 세대와 제품마다 다른 대략적인 자릿수이며, 캐시와 메모리 사이의 데이터 이동은 x86-64에서 보통 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번의 접근은 L1 캐시에서 끝납니다. 결국 1000번 접근 중 새 캐시 라인을 가져오는 것은 약 63번(1000/16)뿐입니다(배열이 64바이트 경계에 정렬되어 있다고 가정).

두 번째 루프는 64칸(256바이트)씩 건너뛰므로 접근할 때마다 다른 캐시 라인을 가져오고, 가져온 64바이트 중 4바이트만 쓰고 나머지는 버립니다. 접근 횟수 자체는 1/64이지만 접근 한 번당 비용은 첫 번째 루프보다 훨씬 큽니다.

같은 양의 데이터를 처리할 때 가져온 캐시 라인을 얼마나 알차게 쓰느냐가 속도를 정한다는 것이 이 절의 요점입니다. 다만 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;  // 캐시 미스 많음
}

시간적 지역성은 한 번 쓴 데이터를 곧 다시 쓰는 성질이고, 공간적 지역성은 한 번 쓴 데이터 근처를 곧 쓰는 성질입니다. 연결 리스트가 느린 이유는 공간적 지역성이 없어서만이 아닙니다. 다음 노드의 주소를 현재 노드를 읽어야 알 수 있으므로, 캐시 미스가 나면 CPU가 그 지연을 다른 로드와 겹쳐 숨길 수 없고 미스 하나하나의 지연을 순서대로 다 기다려야 합니다.

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

패턴 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++의 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 떨어진 위치입니다. 행 하나 전체(N개의 캐시 라인)가 캐시에 머물 만큼 캐시가 크지 않다면, 올려 둔 matrix[0][1][0][15]는 다시 쓰이기 전에 밀려나고 거의 모든 접근이 캐시 미스가 됩니다.

행 우선으로 순회하면 두 순서가 일치합니다.

접근 순서: matrix[0][0] → matrix[0][1] → matrix[0][2] → ...
메모리 순서: [0][0] [0][1] [0][2] ... (일치!)

이번에는 matrix[0][0]을 읽을 때 올라온 캐시 라인으로 이어지는 15번의 접근을 처리하므로, 16번에 한 번만 미스가 납니다. 1000×1000 행렬이라면 열 우선은 최악의 경우 원소마다 한 번씩 약 1,000,000번, 행 우선은 캐시 라인당 한 번씩 약 62,500번의 미스가 납니다. 실제 시간 차이는 CPU, 캐시 크기, 컴파일 옵션에 따라 다르므로 아래 벤치마크 코드로 직접 재 보는 것이 좋습니다. 행렬 곱셈이나 이미지 처리처럼 2차원 데이터를 다루는 코드에서 이 순서를 잘못 잡으면 다른 최적화가 무의미해질 만큼 느려집니다.

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

패딩 최소화

// ❌ 나쁜 예: 패딩 많음 (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 비교 예제

64바이트 구조체 배열(AoS)과 필드별 배열(SoA)에서 x만 읽을 때의 메모리 배치 차이와 측정값

그림: 직접 측정: 400만 원소를 10번 더하는 데 AoS 58~~97ms, SoA 30~~35ms (Apple clang 21, arm64, -O2).

메모리 배치 비교

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::steady_clock::now();
    for (int i = 0; i < 100; ++i) {
        updatePositionsAoS(particles);
    }
    auto end = std::chrono::steady_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로 바꿔도 기대만큼 빨라지지 않으므로, 바꾸기 전에 핫 루프가 구조체의 몇 퍼센트를 쓰는지부터 계산해 보는 것이 좋습니다. SoA는 객체 하나를 다루는 코드가 여러 배열에 흩어진 인덱스를 함께 관리해야 하는 비용도 있습니다. resize나 삭제를 한 배열에만 적용하면 인덱스가 어긋나 엉뚱한 파티클의 데이터를 읽게 되므로, 위 ParticleSystemSoA처럼 모든 배열을 함께 바꾸는 멤버 함수만 통해 크기를 바꾸도록 감싸 두는 것이 안전합니다.

AoS vs SoA 선택 가이드

상황	권장	이유
같은 필드만 대량 처리 (위치 업데이트)	SoA	가져온 바이트를 모두 사용
한 객체의 여러 필드를 함께 사용	AoS	코드 단순
SIMD 벡터화 적용	SoA	연속된 float를 4개(SSE)·8개(AVX)씩 한 번에 처리하기 쉬움
개별 엔티티 조회·수정	AoS	인덱스 하나로 접근

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();
}

atomic 카운터로 측정하기

alignas는 C++11부터 있는 지정자입니다. 아래는 앞에서 말한 대로 std::atomic(relaxed)으로 재는 버전입니다.

// 각 카운터가 별도 캐시 라인에 배치
struct alignas(64) PaddedCounter {
    std::atomic<int64_t> count{0};
};
void benchmarkCounters() {
    const int numThreads = 4;
    std::vector<PaddedCounter> counters(numThreads);
    auto start = std::chrono::steady_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::steady_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "Aligned: " << ms << " ms\n";
}

같은 코드에서 alignas(64)를 빼고 재 보면 차이를 확인할 수 있습니다. 코어 수와 CPU 구조에 따라 다르지만, 여러 코어가 같은 캐시 라인에 계속 쓰는 경우 정렬만으로 몇 배 빨라지는 것이 드물지 않습니다.

같은 캐시 라인의 두 atomic 카운터와 alignas(64)로 분리한 카운터의 실행 시간 비교

그림: 직접 측정 — 스레드 2개가 각자 1억 번 증가시킬 때 같은 캐시 라인은 792~~816ms, alignas(64)로 분리하면 188~~193ms(Apple clang 21, arm64, -O2, 3회).

캐시 라인 크기를 64로 고정해도 될지는 따져 봐야 합니다. x86-64의 캐시 라인은 64바이트이지만 Intel CPU의 인접 라인 프리페처는 두 라인을 128바이트 쌍으로 함께 가져오는 경우가 있고, Apple Silicon(M 시리즈)은 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) 캐시 라인과 그 라인을 건드린 코드 위치를 직접 보여 줍니다.

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

기본 사용법

// GCC/Clang 내장 함수 __builtin_prefetch 사용 (MSVC는 <xmmintrin.h>의 _mm_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=읽기/1=쓰기, 시간 지역성 0~3; 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]] 접근
float 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]];
    }
    return sum;   // 결과를 쓰지 않으면 컴파일러가 루프를 지울 수 있음
}

프리페치 거리를 너무 크게 잡으면 미리 가져온 데이터가 쓰이기 전에 캐시에서 밀려나거나 지금 쓰는 데이터를 밀어내고, 너무 작으면 데이터가 도착하기 전에 루프가 따라잡아 효과가 없습니다. 적절한 거리는 “메모리 지연 시간 ÷ 반복 한 번의 시간”으로 정해지므로 루프마다 다르고, 실험으로 찾아야 합니다. __builtin_prefetch를 넣었더니 오히려 느려졌다면 거리부터 줄여 보고, 하드웨어 프리페처가 이미 처리하는 순차 접근에 넣은 것은 아닌지 확인합니다.

어디에 효과가 있는지도 중요합니다. 첫 번째 예제처럼 배열을 순서대로 읽는 경우는 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;
}

루프 융합은 데이터가 캐시보다 커서 두 번째 순회 때 이미 밀려나 있을 때 의미가 있습니다. 위처럼 10,000개(40KB)라면 대부분 L2에 남아 있어 차이가 작고, 융합한 루프가 너무 많은 일을 하면 오히려 벡터화가 막힐 수도 있습니다.

패턴 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);
}

타입별로 정렬하면 같은 처리 함수와 그 함수가 쓰는 데이터가 연속으로 쓰여 명령 캐시와 데이터 캐시 모두에 유리하고, 타입에 따라 갈리는 분기도 예측하기 쉬워집니다. 다만 정렬 자체가 O(n log n) 비용이므로, 매 프레임 정렬하기보다 삽입 시점에 타입별 배열에 나눠 담는 편이 나은 경우가 많습니다.

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

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

#include <iostream>
#include <chrono>
const int N = 4096;
static int matrix[N][N];   // 64MB, 전역(static)으로 둬야 스택 오버플로가 나지 않음
void benchmarkRowMajor() {
    long long sum = 0;
    auto start = std::chrono::steady_clock::now();
    for (int row = 0; row < N; ++row) {
        for (int col = 0; col < N; ++col) {
            sum += matrix[row][col];
        }
    }
    auto end = std::chrono::steady_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::steady_clock::now();
    for (int col = 0; col < N; ++col) {
        for (int row = 0; row < N; ++row) {
            sum += matrix[row][col];
        }
    }
    auto end = std::chrono::steady_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이 아닌 값으로 채워 둠: 페이지를 처음 건드리는 비용(page fault)이
    // 먼저 실행되는 쪽에만 몰리지 않게 하고, 컴파일러가 합을 미리 계산하지 못하게 함
    for (int r = 0; r < N; ++r)
        for (int c = 0; c < N; ++c) matrix[r][c] = r ^ c;
    benchmarkRowMajor();
    benchmarkColMajor();
}

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

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

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

게임 엔진의 ECS(Entity-Component-System) 구조는 SoA를 설계 전체로 넓힌 것입니다. 엔티티는 인덱스(ID)일 뿐이고, 위치·렌더링 정보 같은 컴포넌트는 종류별로 따로 연속 배열에 저장되며, 시스템은 자신이 필요한 컴포넌트 배열만 순회합니다.

// 게임 엔진에서 흔한 패턴
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;
    }
}

이동 시스템은 TransformComponent만, 렌더링 시스템은 RenderComponent만 읽으므로 각 루프가 가져오는 캐시 라인이 모두 그 루프가 쓰는 데이터로 채워집니다. 반대로 엔티티 하나의 모든 정보를 모아 보려면 여러 배열을 같은 인덱스로 찾아다녀야 하므로, 에디터나 디버깅 도구 쪽 코드는 더 번거로워집니다.

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

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

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

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

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

정렬·프리페치가 기대대로 동작하지 않을 때

alignas(64)를 했는데도 False Sharing이 남음

C++17 이상에서 std::vector<AlignedCounter>의 원소 정렬은 보장되므로, 원인은 대개 다른 곳에 있습니다.

인텔 CPU 일부는 인접한 두 64바이트 라인을 쌍으로 가져오는 공간 프리페처(adjacent line prefetch)가 있어, 64바이트로 분리해도 128바이트 단위에서 간섭이 남을 수 있습니다. 그래서 folly 같은 라이브러리는 x86에서도 128바이트 정렬을 씁니다.
정렬된 카운터 바로 옆에 다른 스레드가 자주 쓰는 변수(락, 큐 인덱스 등)가 있으면 그쪽이 같은 라인을 공유합니다. perf c2c로 실제 충돌 라인과 오프셋을 확인해야 합니다.
C++17 이전 표준으로 빌드했거나 -fno-aligned-new를 쓰면 new가 over-aligned 타입의 정렬을 보장하지 않습니다. 이때는 std::aligned_alloc(크기가 정렬 값의 배수여야 하며 MSVC에는 없음, 대신 _aligned_malloc)으로 직접 할당합니다.

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

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

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

흔한 원인은 세 가지입니다. 순차 접근에 프리페치를 넣으면 하드웨어 프리페처가 이미 하는 일을 반복하면서 명령 수와 로드 포트 사용만 늘어납니다. 거리가 맞지 않으면 데이터가 늦게 도착하거나 쓰기 전에 밀려납니다. 이미 캐시에 있는 작은 작업 집합을 프리페치하면 순수한 낭비가 됩니다.

// 순차 접근에는 소프트웨어 프리페치가 필요 없음
for (size_t i = 0; i < n; ++i) {
    __builtin_prefetch(&data[i + 1], 0, 3);  // 다음 원소는 대개 같은 캐시 라인
    process(data[i]);
}

소프트웨어 프리페치는 간접 접근이나 여러 독립 조회처럼 하드웨어가 예측하지 못하는 패턴에만 넣고, 넣은 뒤에는 반드시 전후를 측정해서 효과가 없으면 지우는 편이 좋습니다.

과도한 alignas로 구조체가 커짐

// 단일 스레드에서만 쓰는 구조체에 정렬을 남발한 예
struct Entity {
    alignas(64) float x, y, z;    // x, y, z 각각이 64바이트 경계에 놓임
    alignas(64) float vx, vy, vz;
};  // sizeof == 384

선언 앞의 alignas는 그 선언의 모든 변수에 적용되므로 여섯 필드가 각자 캐시 라인을 차지해 구조체가 384바이트가 됩니다. 원래 24바이트면 충분한 데이터라 같은 개수를 처리할 때 가져오는 라인 수가 크게 늘어납니다. 캐시 라인 정렬은 서로 다른 스레드가 수정하는 변수 사이에만 필요하고, 일반 구조체는 멤버 순서로 패딩을 줄이는 것으로 충분합니다.

vector<vector<int>>에서 행 우선으로 바꿨는데 기대만큼 빠르지 않음

std::vector<std::vector<int>>는 행마다 따로 힙에 할당되므로, 각 행 안은 연속이지만 행과 행 사이는 떨어져 있을 수 있고 행마다 포인터를 한 번 더 따라가야 합니다. 행이 길면 이 비용이 작지만, 행이 짧거나(예: 수십 원소) 행 경계를 넘는 접근이 많으면 눈에 띕니다. 또 컴파일러가 전체를 하나의 연속 블록으로 다룰 수 없어 최적화 여지가 줄어듭니다.

// 1차원 배열에 연속 저장하고 인덱스를 계산
std::vector<int> m(static_cast<size_t>(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씩 떨어지면 L1의 같은 세트(set)에 매핑되어, 캐시 전체 용량과 상관없이 연관도(보통 8~12웨이)만큼의 라인만 들어가고 서로를 계속 밀어냅니다. 이를 conflict miss라고 합니다. 행 우선 순회로 바꾸는 것이 우선이고, 전치처럼 열 순회가 불가피한 알고리즘이라면 행 길이에 약간의 패딩을 줘서(float m[1024][1024 + 16]) 주소가 같은 세트에 몰리지 않게 합니다. 행렬 크기를 1000에서 1024로 “보기 좋게” 바꿨더니 느려지는 경우가 이 유형입니다.

측정 방법

# 전체 캐시 미스 개요
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)를 여기저기 붙이다가 정작 문제인 필드를 놓치기 쉽기 때문입니다. 이벤트 이름은 CPU와 커널 버전에 따라 지원 여부가 다르므로 perf list로 먼저 확인합니다.

의사 결정 흐름

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) 또는 128"]
    G --> K["레이아웃 재설계 (51-6 참고)"]

결과를 읽는 법

AoS와 SoA를 비교하는 벤치마크 코드는 #51-6의 성능 벤치마크에 있습니다. False Sharing은 앞 절의 코드를 스레드 수 1, 2, 4, 8로 바꿔 가며 돌리면 추세를 볼 수 있습니다. 구체적인 ms 값은 CPU, 캐시 크기, 컴파일 옵션에 따라 크게 달라 여기 고정값을 적지 않았습니다.

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

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

x86-64는 64바이트가 사실상 표준이지만, Apple M 시리즈 같은 일부 ARM 칩은 128바이트입니다. alignas(64)로 분리한 두 카운터가 Apple Silicon에서는 여전히 한 라인을 공유할 수 있습니다. 여러 플랫폼을 지원한다면 std::hardware_destructive_interference_size(컴파일러가 대상 아키텍처 기준 값을 제공)를 쓰거나, 플랫폼별 상수를 두는 편이 안전합니다. 다만 이 상수는 컴파일러 옵션에 따라 값이 바뀔 수 있어 ABI에 영향을 줄 수 있고, GCC는 헤더에서 쓰면 -Winterference-size 경고를 내므로 라이브러리 공개 헤더보다는 구현 파일 안에서 쓰는 것이 무난합니다.

독립적인 조회 겹치기

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

// 키 배치를 한 번에 조회: 주소 계산 → 프리페치 → 실제 접근
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]);
    }
}

Table, Bucket, Value는 설명용 타입입니다. 버킷이 다시 체인 노드를 가리키는 구조라면 첫 단계만 겹쳐지고 그 뒤의 포인터 추적은 여전히 직렬이라는 점도 기억해 둘 만합니다. B-tree처럼 노드 하나가 여러 캐시 라인에 걸치는 경우에는, 노드에 도착한 직후 그 노드의 나머지 캐시 라인을 프리페치하는 것이 효과적입니다. 이는 다음 노드가 아니라 현재 노드 안의 순차 접근을 앞당기는 것입니다.

SoA 역효과, 인덱스 불일치, `vector<vector>`

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

SoA가 불리해지는 전형적인 경우는 원소 하나의 여러 필드를 임의 순서로 읽는 접근입니다.

// 선택된 엔티티들(임의의 인덱스)의 모든 필드를 함께 사용
for (size_t id : selected) {
    float d = x[id] * x[id] + y[id] * y[id] + z[id] * z[id];
    if (d < radius2) {
        vx[id] = -vx[id]; vy[id] = -vy[id]; vz[id] = -vz[id];
    }
}

AoS라면 원소 하나의 필드가 한 캐시 라인에 모여 있어 원소당 캐시 미스가 한 번이지만, SoA에서는 필드 배열마다 다른 캐시 라인을 읽어야 해 원소당 캐시 미스가 최대 여섯 번이 됩니다. 순차 순회라면 필드 배열이 여러 개여도 프리페처가 각 스트림을 따라가므로 문제가 덜하지만, 한 루프에서 동시에 읽는 배열이 수십 개로 늘어나면 하드웨어가 추적할 수 있는 스트림 수와 TLB 항목을 넘어서 효율이 떨어질 수 있습니다.

해결은 접근 패턴에 맞춰 묶는 것입니다. 항상 함께 쓰는 필드(예: 위치 x, y, z)는 작은 구조체로 묶어 배열로 두고, 따로 쓰는 필드끼리만 분리하는 하이브리드 배치가 흔한 절충입니다. SIMD 폭에 맞춰 원소를 4개·8개씩 묶는 AoSoA(예: struct { float x[8], y[8], z[8]; }의 배열)도 같은 목적의 배치입니다. 어느 쪽이든 바꾸기 전후를 실제 데이터로 측정해서 판단해야 합니다.

핫/콜드 또는 SoA 배열 사이의 인덱스 어긋남

원소를 삭제할 때 마지막 원소를 그 자리로 옮기고 줄이는(swap-and-pop) 방식은 O(1)이라 자주 쓰이지만, 병렬 배열 중 하나만 이렇게 처리하면 그 뒤로 hot[i]와 cold[i]가 다른 엔티티를 가리킵니다. 컴파일 에러도 크래시도 없이 엉뚱한 이름이 표시되는 식으로 나타나 원인을 찾기 어렵습니다. 모든 배열의 추가·삭제를 한 곳에서 처리하는 래퍼를 두거나, 콜드 데이터는 id 기반으로 저장해 인덱스 의존 자체를 없앱니다.

struct ParticleSoA {
    std::vector<float> x, y, z, vx, vy, vz, life;

    void add(float x_, float y_, float z_, float vx_, float vy_, float vz_, float life_) {
        x.push_back(x_); y.push_back(y_); z.push_back(z_);
        vx.push_back(vx_); vy.push_back(vy_); vz.push_back(vz_);
        life.push_back(life_);
    }

    void remove(size_t i) {   // 모든 배열에 같은 swap-and-pop 적용
        auto swap_pop = [i](std::vector<float>& v) {
            v[i] = v.back();
            v.pop_back();
        };
        swap_pop(x); swap_pop(y); swap_pop(z);
        swap_pop(vx); swap_pop(vy); swap_pop(vz);
        swap_pop(life);
    }
};

새 필드를 추가할 때 add와 remove 양쪽에 빠짐없이 넣어야 한다는 점은 여전히 실수하기 쉬운 부분이므로, 디버그 빌드에서 모든 배열의 크기가 같은지 assert로 확인해 두면 좋습니다. swap-and-pop은 원소 순서를 바꾸므로, 순서가 의미 있는 데이터(그리기 순서 등)에는 맞지 않습니다.

2차원 배열을 `vector<vector>`로 저장

std::vector<std::vector<int>> m(N, std::vector<int>(N));   // 행마다 별도 힙 할당
std::vector<int> flat(N * N);                              // 한 덩어리

std::vector<std::vector<int>>는 행마다 따로 할당되므로 행과 행 사이가 메모리에서 이어지지 않고, 원소에 접근할 때마다 바깥 벡터에서 행 포인터를 한 번 더 읽습니다. 행 우선으로 순회하면 행 안에서는 연속이라 큰 차이가 나지 않을 수 있지만, 열 방향 접근이나 행 크기가 작은 경우에는 손해가 커지고, 할당 횟수도 행 수만큼 늘어납니다. 크기가 고정된 행렬은 1차원 배열 하나에 r * N + c로 접근하는 편이 낫습니다.

다른 분야의 적용 예

파티클 풀

struct ParticlePool {
    std::vector<float> x, y, z;
    std::vector<float> vx, vy, vz;
    std::vector<float> life;

    void update(float dt) {
        const size_t n = x.size();
        for (size_t i = 0; i < n; ++i) {
            x[i] += vx[i] * dt;
            y[i] += vy[i] * dt;
            z[i] += vz[i] * dt;
            life[i] -= dt;
        }
        // 수명이 끝난 파티클은 별도 패스에서 swap-and-pop으로 제거
    }
};

갱신 루프 안에서 바로 원소를 지우면 인덱스가 흔들리고 분기가 생겨 벡터화가 깨지므로, 갱신과 제거를 별도 패스로 나누는 것이 일반적입니다.

스레드별 통계와 거짓 공유

#include <atomic>
#include <cstdint>
#include <vector>

struct alignas(64) WorkerStats {
    std::atomic<uint64_t> requests{0};
    std::atomic<uint64_t> bytes{0};
};

std::vector<WorkerStats> stats(num_threads);   // 각 워커는 자기 원소만 갱신

데이터 지향 설계에서 레이아웃은 단일 스레드 캐시 효율만의 문제가 아닙니다. 스레드마다 자기 카운터만 갱신해도, 서로 다른 스레드의 카운터가 같은 캐시 라인에 있으면 한 스레드가 쓸 때마다 다른 코어의 캐시 라인이 무효화되는 거짓 공유(false sharing)가 생깁니다. alignas(64)로 원소마다 캐시 라인을 따로 쓰게 하면 이를 막을 수 있습니다. C++17의 std::hardware_destructive_interference_size가 이 값을 제공하지만, 컴파일러에 따라 지원 시점이 다르고 ABI 경고가 나기도 해 64를 직접 쓰는 코드도 많습니다. 정렬된 타입을 std::vector에 담으려면 C++17의 정렬 지원 new가 필요합니다.

로그 집계 (컬럼형)

struct LogBatch {
    std::vector<int64_t> timestamp;
    std::vector<int> level;
    std::vector<std::string> message;
    std::vector<int> user_id;

    size_t count_by_level(int lv) const {
        size_t count = 0;
        for (int l : level) count += (l == lv);   // level 배열만 순회
        return count;
    }
};

분석용 데이터베이스가 행 대신 열 단위로 저장하는 것(컬럼형 스토리지)도 같은 원리입니다. 레벨별 집계는 level 배열만 읽으므로, 메시지 문자열은 전혀 메모리로 올라오지 않습니다. 반대로 레코드 하나를 통째로 읽고 쓰는 일이 많은 트랜잭션 처리에는 행 단위 저장이 맞습니다.

AoS→SoA 파티클, 병렬 카운터 패딩, 행렬 전치 예제

예제 1: AoS → SoA 변환 (파티클 시스템)

#include <vector>
#include <chrono>
#include <iostream>
// Before: AoS
struct ParticleAoS {
    float x, y, z;
    float vx, vy, vz;
    float r, g, b, a;
    float life;
};
using ParticlesAoS = std::vector<ParticleAoS>;
void updateAoS(ParticlesAoS& particles, float dt) {
    for (auto& p : particles) {
        p.x += p.vx * dt;
        p.y += p.vy * dt;
        p.z += p.vz * dt;
        p.life -= dt;
    }
}
// After: SoA
struct ParticlesSoA {
    std::vector<float> x, y, z;
    std::vector<float> vx, vy, vz;
    std::vector<float> r, g, b, a;
    std::vector<float> life;
};
void updateSoA(ParticlesSoA& particles, float dt) {
    const size_t n = particles.x.size();
    for (size_t i = 0; i < n; ++i) {
        particles.x[i] += particles.vx[i] * dt;
        particles.y[i] += particles.vy[i] * dt;
        particles.z[i] += particles.vz[i] * dt;
        particles.life[i] -= dt;
    }
}
int main() {
    const size_t N = 100000;
    ParticlesAoS aos(N);
    ParticlesSoA soa;
    soa.x.resize(N); soa.y.resize(N); soa.z.resize(N);
    soa.vx.resize(N); soa.vy.resize(N); soa.vz.resize(N);
    soa.r.resize(N); soa.g.resize(N); soa.b.resize(N); soa.a.resize(N);
    soa.life.resize(N);
    // 초기화
    for (size_t i = 0; i < N; ++i) {
        aos[i].x = aos[i].y = aos[i].z = 0.f;
        aos[i].vx = aos[i].vy = aos[i].vz = 1.f;
        soa.x[i] = soa.y[i] = soa.z[i] = 0.f;
        soa.vx[i] = soa.vy[i] = soa.vz[i] = 1.f;
    }
    const int iterations = 1000;
    auto startAoS = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < iterations; ++i) updateAoS(aos, 0.016f);
    auto endAoS = std::chrono::high_resolution_clock::now();
    auto startSoA = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < iterations; ++i) updateSoA(soa, 0.016f);
    auto endSoA = std::chrono::high_resolution_clock::now();
    auto msAoS = std::chrono::duration_cast<std::chrono::milliseconds>(endAoS - startAoS).count();
    auto msSoA = std::chrono::duration_cast<std::chrono::milliseconds>(endSoA - startSoA).count();
    std::cout << "AoS: " << msAoS << "ms, SoA: " << msSoA << "ms\n";
    return 0;
}

예제 2: 거짓 공유 제거 (병렬 카운터)

#include <atomic>
#include <thread>
#include <vector>
#include <chrono>
#include <iostream>
constexpr size_t CACHE_LINE = 64;
// 잘못된 예: 같은 캐시 라인
void bench_bad() {
    std::atomic<int> counters[4];
    for (auto& c : counters) c.store(0);
    std::vector<std::thread> threads;
    for (int i = 0; i < 4; ++i) {
        threads.emplace_back([&, i]() {
            for (int j = 0; j < 10000000; ++j) {
                counters[i].fetch_add(1, std::memory_order_relaxed);
            }
        });
    }
    for (auto& t : threads) t.join();
}
// 개선한 예: 캐시 라인 분리
void bench_good() {
    struct Padded { alignas(CACHE_LINE) std::atomic<int> value; };
    std::vector<Padded> counters(4);
    for (auto& c : counters) c.value.store(0);
    std::vector<std::thread> threads;
    for (int i = 0; i < 4; ++i) {
        threads.emplace_back([&, i]() {
            for (int j = 0; j < 10000000; ++j) {
                counters[i].value.fetch_add(1, std::memory_order_relaxed);
            }
        });
    }
    for (auto& t : threads) t.join();
}
int main() {
    auto t1 = std::chrono::high_resolution_clock::now();
    bench_bad();
    auto t2 = std::chrono::high_resolution_clock::now();
    bench_good();
    auto t3 = std::chrono::high_resolution_clock::now();
    auto ms_bad = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
    auto ms_good = std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2).count();
    std::cout << "Bad (False Sharing): " << ms_bad << "ms\n";
    std::cout << "Good (Padded): " << ms_good << "ms\n";
    return 0;
}

예제 3: SoA + SIMD 친화적 루프 (개념)

// SoA에서는 컴파일러가 자동 벡터화하기 쉬움
void updatePositionsSIMDFriendly(float* x, float* y, float* z,
                                 const float* vx, const float* vy, const float* vz,
                                 size_t n, float dt) {
    // -O3 -march=native 로 컴파일 시 AVX/SSE 자동 벡터화
    for (size_t i = 0; i < n; ++i) {
        x[i] += vx[i] * dt;
        y[i] += vy[i] * dt;
        z[i] += vz[i] * dt;
    }
}

예제 4: 수동 프리페치 (간접 접근)

배열을 앞에서부터 순차로 읽는 루프는 CPU의 하드웨어 프리페처가 이미 다음 라인을 미리 가져오므로, 수동 프리페치를 넣어도 대개 이득이 없습니다. 수동 프리페치가 의미 있는 경우는 하드웨어가 다음 주소를 예측할 수 없는 간접 접근입니다.

#include <xmmintrin.h>  // _mm_prefetch (x86)
// idx가 가리키는 위치는 예측 불가 → 몇 번 뒤에 접근할 원소를 미리 요청
void updateIndirect(float* x, const float* vx, const unsigned* idx, size_t n, float dt) {
    constexpr size_t D = 16;   // 몇 번 앞을 미리 가져올지: 메모리 지연과 루프 비용으로 정함
    for (size_t i = 0; i < n; ++i) {
        if (i + D < n) {
            _mm_prefetch(reinterpret_cast<const char*>(&x[idx[i + D]]), _MM_HINT_T0);
        }
        x[idx[i]] += vx[idx[i]] * dt;
    }
}

프리페치 거리가 너무 짧으면 데이터가 도착하기 전에 접근해 효과가 없고, 너무 길면 쓰기 전에 다른 데이터에 밀려나 버립니다. 적정 거리는 CPU와 루프마다 다르므로 반드시 측정하며 조정해야 하고, 효과가 없으면 지우는 것이 맞습니다. GCC·Clang에서는 이식성 있는 __builtin_prefetch도 쓸 수 있습니다.

예제 5: 행 우선 순회와 열 우선 순회

// 2차원 배열을 행 우선으로 순회하면 캐시 히트
void sumMatrixRowMajor(const std::vector<std::vector<float>>& matrix, float& sum) {
    sum = 0;
    for (size_t row = 0; row < matrix.size(); ++row) {
        for (size_t col = 0; col < matrix[row].size(); ++col) {
            sum += matrix[row][col];  // 연속 접근
        }
    }
}
// 열 우선 순회는 캐시 미스 다발
void sumMatrixColMajor(const std::vector<std::vector<float>>& matrix, float& sum) {
    sum = 0;
    for (size_t col = 0; col < matrix[0].size(); ++col) {
        for (size_t row = 0; row < matrix.size(); ++row) {
            sum += matrix[row][col];  // 캐시 미스 많음
        }
    }
}

vector<vector<float>>는 행마다 따로 할당되므로 행끼리도 메모리상 떨어져 있습니다. 큰 행렬은 vector<float> 하나에 row * cols + col로 접근하는 1차원 배열로 두는 편이 캐시와 프리페처에 더 유리합니다.

AoS vs SoA, 패딩 전후 측정과 perf 확인

AoS vs SoA (10만 파티클, 위치 갱신)

구성	캐시에 올라오는 데이터 중 실제 사용 비율	기대 효과
AoS (`Entity` 28바이트)	위치 갱신에 쓰는 24바이트 / 28바이트	기준
SoA (연속 배열)	필요한 배열만 읽으므로 거의 전부	대역폭 낭비 감소 + SIMD 벡터화가 쉬움

SoA의 이득은 루프가 구조체 필드 중 일부만 쓸 때 커집니다. 위 Entity로 위치를 갱신하면 7개 필드 중 6개를 쓰므로 AoS도 캐시 라인의 대부분을 활용하고, 차이는 주로 컴파일러가 SoA 루프를 더 쉽게 벡터화하는 데서 나옵니다. 반대로 x만 읽는 루프라면 AoS는 28바이트 중 4바이트만 쓰는 셈이라 차이가 훨씬 커집니다. 10만 개 × 28바이트는 약 2.8MB로 L2보다 크고 L3에는 들어갈 수 있는 크기라, 데이터가 캐시에 다 들어가는지 여부에 따라서도 결과가 달라집니다.

거짓 공유 패딩 전/후 (4스레드, 1천만 회 카운터 증가)

구성	기대되는 경향
패딩 없음 (False Sharing)	네 카운터가 한 캐시 라인에 있어, 쓰기마다 다른 코어의 사본이 무효화되어 스레드를 늘려도 빨라지지 않음
alignas(64) 패딩 적용	각 카운터가 자기 캐시 라인을 가져 스레드 수에 가까운 확장성

실제 배수는 CPU의 코어 간 구조, 메모리 대역폭, 컴파일러 최적화에 따라 크게 다르므로 아래 perf stat으로 직접 비교하세요.

perf로 캐시 미스 확인

# AoS vs SoA 비교
perf stat -e cache-misses,cache-references,L1-dcache-load-misses ./bench_aos
perf stat -e cache-misses,cache-references,L1-dcache-load-misses ./bench_soa
# cache-misses / cache-references 비율이 낮을수록 캐시 효율 좋음

벤치마크 시 주의사항

최적화 빌드(-O2/-O3)로 측정하고, SIMD 효과를 보려면 -march=native를 함께 씁니다. 첫 실행은 페이지 폴트와 캐시 워밍업 비용이 섞이므로 워밍업 반복을 버리고, 여러 번 실행해 평균과 편차를 함께 봅니다.

캐시 계층별 크기와 의미

(대략적인 범위이며 CPU 세대마다 다름)
L1 데이터 캐시: 코어당 수십 KB (32~48KB가 흔하고, Apple M 시리즈 성능 코어는 128KB)
  → 수 KB 단위 데이터를 반복 접근할 때 L1에 유지되면 최고 속도
L2 캐시: 코어당 수백 KB~수 MB
  → 수만~수십만 float 배열이 L2에 들어가면 SoA 순회 시 유리
L3 캐시: 여러 코어가 공유, 수 MB~수십 MB
  → 수백만 엔티티는 L3에도 안 들어가므로 메모리 대역폭이 병목
  → 이 경우 배치 크기를 L2/L3에 맞게 나누는 블로킹이 효과적

컴파일 옵션 예시

# GCC/Clang: 최대 최적화 + 네이티브 SIMD
g++ -std=c++17 -O3 -march=native -o bench bench.cpp
# 디버그 빌드에서는 캐시 최적화 효과가 상대적으로 작을 수 있음
# Release 빌드로 벤치마크 수행

참고 자료

What Every Programmer Should Know About Memory (Ulrich Drepper)

자주 묻는 질문 (FAQ)

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

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

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

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

메모리 계층

메모리 계층 시각화

캐시 히트 vs 미스

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

시간적 지역성 (Temporal Locality)

공간적 지역성 (Spatial Locality)

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

패턴 1: 연속 메모리 사용

패턴 2: 행 우선 순회

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

패딩 최소화

핫/콜드 데이터 분리

AoS와 SoA 비교 예제

메모리 배치 비교

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

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

AoS vs SoA 선택 가이드

False Sharing (가짜 공유)

False Sharing 발생 원리

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

해결: 캐시 라인 정렬

atomic 카운터로 측정하기

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

기본 사용법

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

인덱스 배열 따라가기

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

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

패턴 2: 루프 융합

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

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

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

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

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

정렬·프리페치가 기대대로 동작하지 않을 때

alignas(64)를 했는데도 False Sharing이 남음

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

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

과도한 alignas로 구조체가 커짐

vector<vector<int>>에서 행 우선으로 바꿨는데 기대만큼 빠르지 않음

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

측정 방법

의사 결정 흐름

결과를 읽는 법

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

독립적인 조회 겹치기

SoA 역효과, 인덱스 불일치, vector<vector>

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

핫/콜드 또는 SoA 배열 사이의 인덱스 어긋남

2차원 배열을 vector<vector>로 저장

다른 분야의 적용 예

파티클 풀

스레드별 통계와 거짓 공유

로그 집계 (컬럼형)

AoS→SoA 파티클, 병렬 카운터 패딩, 행렬 전치 예제

예제 1: AoS → SoA 변환 (파티클 시스템)

예제 2: 거짓 공유 제거 (병렬 카운터)

예제 3: SoA + SIMD 친화적 루프 (개념)

예제 4: 수동 프리페치 (간접 접근)

예제 5: 행 우선 순회와 열 우선 순회

AoS vs SoA, 패딩 전후 측정과 perf 확인

AoS vs SoA (10만 파티클, 위치 갱신)

거짓 공유 패딩 전/후 (4스레드, 1천만 회 카운터 증가)

perf로 캐시 미스 확인

벤치마크 시 주의사항

캐시 계층별 크기와 의미

컴파일 옵션 예시

참고 자료

자주 묻는 질문 (FAQ)

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

관련 글

SoA 역효과, 인덱스 불일치, `vector<vector>`

2차원 배열을 `vector<vector>`로 저장