C++ Cache Optimization | 캐시 친화적 코드·False Sharing 방지 완벽 정리

· 32분 읽기 · 수정 고급 튜토리얼
C++ Cache Optimization | 캐시 친화적 코드·False Sharing 방지 완벽 정리

이 글의 핵심

C++ 캐시 최적화: 공간 지역성, 시간 지역성, False Sharing 방지, AoS vs SoA, 프리페칭, 블록 처리를 실전 예제와 함께 정리합니다.

들어가며

CPU 캐시는 메모리와 CPU 사이의 속도 차이를 메우는 핵심 요소입니다. 캐시 친화적인 코드를 작성하면 캐시 히트율을 높여 성능을 크게 개선할 수 있습니다.

이 글을 읽으면

  • 공간 지역성, 시간 지역성으로 캐시 히트율을 높입니다
  • False Sharing을 방지해 멀티스레드 성능을 개선합니다
  • AoS vs SoA, 블록 처리, 프리페칭 등 고급 패턴을 익힙니다
  • 실무에서 자주 쓰이는 캐시 최적화 기법을 구현합니다

목차

  1. 캐시 기본 개념
  2. 실전 구현
  3. 고급 활용
  4. 성능 비교
  5. 실무 사례
  6. 트러블슈팅
  7. 마무리

캐시 기본 개념

캐시 계층 구조

캐시크기지연 시간대역폭
L132-64 KB1-2 cycles가장 빠름
L2256-512 KB10-20 cycles빠름
L38-32 MB40-75 cycles중간
메모리8-64 GB200+ cycles느림

지역성 원리

  1. 공간 지역성 (Spatial Locality)

    • 인접한 메모리를 연속으로 접근
    • 예: 배열 순차 순회

  2. 시간 지역성 (Temporal Locality)

    • 최근에 접근한 메모리를 다시 접근
    • 예: 루프 안의 변수

캐시 라인

  • 일반적으로 64 bytes
  • 캐시는 라인 단위로 로드
  • 연속된 데이터는 한 번에 로드됨

실전 구현

1) 공간 지역성 - 행렬 순회

나쁜 예: 열 우선 (비연속)

#include <vector>
#include <chrono>
#include <iostream>

int main() {
    const int rows = 1000;
    const int cols = 1000;
    std::vector<std::vector<int>> matrix(rows, std::vector<int>(cols, 1));
    
    auto start = std::chrono::high_resolution_clock::now();
    
    int sum = 0;
    for (int j = 0; j < cols; ++j) {
        for (int i = 0; i < rows; ++i) {
            sum += matrix[i][j];  // 열 우선 (캐시 미스)
        }
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    
    std::cout << "열 우선: " << duration << "ms" << std::endl;
    // 약 50ms
    
    return 0;
}

좋은 예: 행 우선 (연속)

int main() {
    const int rows = 1000;
    const int cols = 1000;
    std::vector<std::vector<int>> matrix(rows, std::vector<int>(cols, 1));
    
    auto start = std::chrono::high_resolution_clock::now();
    
    int sum = 0;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            sum += matrix[i][j];  // 행 우선 (캐시 히트)
        }
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    
    std::cout << "행 우선: " << duration << "ms" << std::endl;
    // 약 10ms (5배 빠름)
    
    return 0;
}

2) False Sharing 방지

문제 코드

#include <atomic>
#include <thread>
#include <vector>
#include <chrono>
#include <iostream>

struct Counters {
    std::atomic<int> counter1;  // 0-3 bytes
    std::atomic<int> counter2;  // 4-7 bytes
};  // 같은 캐시 라인

int main() {
    Counters counters;
    
    auto start = std::chrono::high_resolution_clock::now();
    
    std::thread t1([&]() {
        for (int i = 0; i < 10000000; ++i) {
            counters.counter1++;
        }
    });
    
    std::thread t2([&]() {
        for (int i = 0; i < 10000000; ++i) {
            counters.counter2++;
        }
    });
    
    t1.join();
    t2.join();
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    
    std::cout << "False Sharing: " << duration << "ms" << std::endl;
    // 약 500ms
    
    return 0;
}

해결 코드

struct CountersAligned {
    alignas(64) std::atomic<int> counter1;
    alignas(64) std::atomic<int> counter2;
};  // 다른 캐시 라인

int main() {
    CountersAligned counters;
    
    auto start = std::chrono::high_resolution_clock::now();
    
    std::thread t1([&]() {
        for (int i = 0; i < 10000000; ++i) {
            counters.counter1++;
        }
    });
    
    std::thread t2([&]() {
        for (int i = 0; i < 10000000; ++i) {
            counters.counter2++;
        }
    });
    
    t1.join();
    t2.join();
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    
    std::cout << "No False Sharing: " << duration << "ms" << std::endl;
    // 약 150ms (3배 개선)
    
    return 0;
}

3) AoS vs SoA

AoS (Array of Structures)

struct Particle {
    float x, y, z;
    float vx, vy, vz;
};

std::vector<Particle> particles(10000);

// 위치 업데이트
for (auto& p : particles) {
    p.x += p.vx;  // x와 vx가 멀리 떨어짐 (캐시 미스)
}

SoA (Structure of Arrays)

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

Particles particles;
particles.x.resize(10000);
particles.vx.resize(10000);

// 위치 업데이트
for (size_t i = 0; i < particles.x.size(); ++i) {
    particles.x[i] += particles.vx[i];  // 연속 접근 (캐시 히트)
}

성능: SoA가 2-3배 빠름

4) 블록 처리 (Tiling)

행렬 곱셈

#include <vector>
#include <algorithm>
#include <chrono>
#include <iostream>

void matmul_naive(const std::vector<std::vector<int>>& A,
                  const std::vector<std::vector<int>>& B,
                  std::vector<std::vector<int>>& C,
                  int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                C[i][j] += A[i][k] * B[k][j];  // B 열 접근 (캐시 미스)
            }
        }
    }
}

void matmul_blocked(const std::vector<std::vector<int>>& A,
                    const std::vector<std::vector<int>>& B,
                    std::vector<std::vector<int>>& C,
                    int n, int blockSize) {
    for (int i = 0; i < n; i += blockSize) {
        for (int j = 0; j < n; j += blockSize) {
            for (int k = 0; k < n; k += blockSize) {
                for (int ii = i; ii < std::min(i + blockSize, n); ++ii) {
                    for (int jj = j; jj < std::min(j + blockSize, n); ++jj) {
                        for (int kk = k; kk < std::min(k + blockSize, n); ++kk) {
                            C[ii][jj] += A[ii][kk] * B[kk][jj];
                        }
                    }
                }
            }
        }
    }
}

int main() {
    const int n = 512;
    std::vector<std::vector<int>> A(n, std::vector<int>(n, 1));
    std::vector<std::vector<int>> B(n, std::vector<int>(n, 1));
    std::vector<std::vector<int>> C1(n, std::vector<int>(n, 0));
    std::vector<std::vector<int>> C2(n, std::vector<int>(n, 0));
    
    auto start1 = std::chrono::high_resolution_clock::now();
    matmul_naive(A, B, C1, n);
    auto end1 = std::chrono::high_resolution_clock::now();
    auto time1 = std::chrono::duration_cast<std::chrono::milliseconds>(end1 - start1).count();
    
    auto start2 = std::chrono::high_resolution_clock::now();
    matmul_blocked(A, B, C2, n, 64);
    auto end2 = std::chrono::high_resolution_clock::now();
    auto time2 = std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2).count();
    
    std::cout << "Naive: " << time1 << "ms" << std::endl;
    std::cout << "Blocked: " << time2 << "ms" << std::endl;
    
    return 0;
}

5) 프리페칭

#include <xmmintrin.h>
#include <vector>
#include <chrono>
#include <iostream>

void processWithoutPrefetch(std::vector<int>& data) {
    for (size_t i = 0; i < data.size(); ++i) {
        data[i] = data[i] * 2;
    }
}

void processWithPrefetch(std::vector<int>& data) {
    constexpr int prefetchDistance = 64;
    
    for (size_t i = 0; i < data.size(); ++i) {
        if (i + prefetchDistance < data.size()) {
            _mm_prefetch(&data[i + prefetchDistance], _MM_HINT_T0);
        }
        
        data[i] = data[i] * 2;
    }
}

int main() {
    std::vector<int> data1(10000000, 1);
    std::vector<int> data2(10000000, 1);
    
    auto start1 = std::chrono::high_resolution_clock::now();
    processWithoutPrefetch(data1);
    auto end1 = std::chrono::high_resolution_clock::now();
    auto time1 = std::chrono::duration_cast<std::chrono::milliseconds>(end1 - start1).count();
    
    auto start2 = std::chrono::high_resolution_clock::now();
    processWithPrefetch(data2);
    auto end2 = std::chrono::high_resolution_clock::now();
    auto time2 = std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2).count();
    
    std::cout << "Without Prefetch: " << time1 << "ms" << std::endl;
    std::cout << "With Prefetch: " << time2 << "ms" << std::endl;
    
    return 0;
}

고급 활용

1) 캐시 라인 정렬

#include <iostream>

constexpr size_t CACHE_LINE_SIZE = 64;

// 캐시 라인 정렬
alignas(CACHE_LINE_SIZE) int data[16];

int main() {
    std::cout << "주소: " << (uintptr_t)data << std::endl;
    // 64의 배수
    
    return 0;
}

2) 구조체 최적화

// ❌ 캐시 라인 분할
struct Bad {
    char a;      // 1 byte
    // 3 bytes padding
    int b;       // 4 bytes
    // 4 bytes padding
    long d;      // 8 bytes
};  // 24 bytes

// ✅ 정렬
struct Good {
    long d;      // 8 bytes
    int b;       // 4 bytes
    char a;      // 1 byte
    // 3 bytes padding
};  // 16 bytes

int main() {
    std::cout << "Bad: " << sizeof(Bad) << std::endl;   // 24
    std::cout << "Good: " << sizeof(Good) << std::endl; // 16
    
    return 0;
}

3) 캐시 친화적 순회

#include <vector>
#include <chrono>
#include <iostream>

int main() {
    const int n = 10000;
    std::vector<int> data(n, 1);
    
    // ✅ 순차 접근
    auto start1 = std::chrono::high_resolution_clock::now();
    int sum1 = 0;
    for (int i = 0; i < n; ++i) {
        sum1 += data[i];
    }
    auto end1 = std::chrono::high_resolution_clock::now();
    auto time1 = std::chrono::duration_cast<std::chrono::microseconds>(end1 - start1).count();
    
    // ❌ 큰 스트라이드
    auto start2 = std::chrono::high_resolution_clock::now();
    int sum2 = 0;
    for (int i = 0; i < n; i += 100) {
        sum2 += data[i];
    }
    auto end2 = std::chrono::high_resolution_clock::now();
    auto time2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - start2).count();
    
    std::cout << "순차: " << time1 << "us" << std::endl;
    std::cout << "스트라이드: " << time2 << "us" << std::endl;
    
    return 0;
}

성능 비교

행렬 순회 비교

테스트: 1000x1000 행렬

순회 방식시간배속
행 우선 (연속)10ms5x
열 우선 (비연속)50ms1x

결론: 행 우선이 5배 빠름

False Sharing 비교

테스트: 2개 스레드, 각 1천만 번 증가

구조시간배속
False Sharing500ms1x
캐시 라인 분리150ms3.3x

결론: 캐시 라인 분리로 3배 개선

AoS vs SoA 비교

테스트: 10,000개 파티클 위치 업데이트

구조시간배속
AoS150us1x
SoA50us3x

결론: SoA가 3배 빠름

실무 사례

사례 1: 게임 엔진 - 파티클 시스템

#include <vector>
#include <chrono>
#include <iostream>

// SoA 구조
struct ParticleSystem {
    std::vector<float> x, y, z;
    std::vector<float> vx, vy, vz;
    std::vector<float> lifetime;
    
    void update(float dt) {
        for (size_t i = 0; i < x.size(); ++i) {
            x[i] += vx[i] * dt;
            y[i] += vy[i] * dt;
            z[i] += vz[i] * dt;
            lifetime[i] -= dt;
        }
    }
};

int main() {
    ParticleSystem ps;
    ps.x.resize(100000, 0.0f);
    ps.y.resize(100000, 0.0f);
    ps.z.resize(100000, 0.0f);
    ps.vx.resize(100000, 1.0f);
    ps.vy.resize(100000, 1.0f);
    ps.vz.resize(100000, 1.0f);
    ps.lifetime.resize(100000, 10.0f);
    
    auto start = std::chrono::high_resolution_clock::now();
    ps.update(0.016f);
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    
    std::cout << "업데이트: " << duration << "us" << std::endl;
    
    return 0;
}

사례 2: 데이터베이스 - 인덱스 스캔

#include <vector>
#include <algorithm>
#include <chrono>
#include <iostream>

struct Record {
    int id;
    int value;
};

// ❌ 전체 레코드 로드
void scanFull(const std::vector<Record>& records) {
    int sum = 0;
    for (const auto& rec : records) {
        if (rec.value > 100) {
            sum += rec.value;
        }
    }
}

// ✅ 인덱스만 스캔
void scanIndex(const std::vector<int>& values, const std::vector<int>& ids) {
    int sum = 0;
    for (size_t i = 0; i < values.size(); ++i) {
        if (values[i] > 100) {
            sum += values[i];
        }
    }
}

int main() {
    const int n = 1000000;
    std::vector<Record> records(n);
    std::vector<int> values(n);
    std::vector<int> ids(n);
    
    for (int i = 0; i < n; ++i) {
        records[i] = {i, i % 200};
        values[i] = i % 200;
        ids[i] = i;
    }
    
    auto start1 = std::chrono::high_resolution_clock::now();
    scanFull(records);
    auto end1 = std::chrono::high_resolution_clock::now();
    auto time1 = std::chrono::duration_cast<std::chrono::milliseconds>(end1 - start1).count();
    
    auto start2 = std::chrono::high_resolution_clock::now();
    scanIndex(values, ids);
    auto end2 = std::chrono::high_resolution_clock::now();
    auto time2 = std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2).count();
    
    std::cout << "Full: " << time1 << "ms" << std::endl;
    std::cout << "Index: " << time2 << "ms" << std::endl;
    
    return 0;
}

사례 3: 머신러닝 - 행렬 연산

#include <vector>
#include <chrono>
#include <iostream>

void matmul_blocked_optimized(const std::vector<std::vector<float>>& A,
                               const std::vector<std::vector<float>>& B,
                               std::vector<std::vector<float>>& C,
                               int n, int blockSize) {
    for (int i = 0; i < n; i += blockSize) {
        for (int j = 0; j < n; j += blockSize) {
            for (int k = 0; k < n; k += blockSize) {
                for (int ii = i; ii < std::min(i + blockSize, n); ++ii) {
                    for (int kk = k; kk < std::min(k + blockSize, n); ++kk) {
                        float a = A[ii][kk];
                        for (int jj = j; jj < std::min(j + blockSize, n); ++jj) {
                            C[ii][jj] += a * B[kk][jj];
                        }
                    }
                }
            }
        }
    }
}

int main() {
    const int n = 512;
    std::vector<std::vector<float>> A(n, std::vector<float>(n, 1.0f));
    std::vector<std::vector<float>> B(n, std::vector<float>(n, 1.0f));
    std::vector<std::vector<float>> C(n, std::vector<float>(n, 0.0f));
    
    auto start = std::chrono::high_resolution_clock::now();
    matmul_blocked_optimized(A, B, C, n, 64);
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    
    std::cout << "시간: " << duration << "ms" << std::endl;
    
    return 0;
}

트러블슈팅

문제 1: 캐시 미스 진단

증상: 성능이 예상보다 느림

# Linux: perf로 캐시 미스 측정
perf stat -e cache-misses,cache-references ./program

# 출력:
# 1,234,567 cache-misses
# 10,000,000 cache-references
# 12.3% cache miss rate

해결: 순차 접근, SoA 구조로 변경

문제 2: False Sharing 진단

증상: 멀티스레드 성능이 기대보다 낮음

# Linux: perf로 False Sharing 측정
perf c2c record ./program
perf c2c report

해결: alignas(64) 또는 패딩 추가

문제 3: 큰 스트라이드

증상: 배열 순회가 느림

// ❌ 큰 스트라이드
for (int i = 0; i < n; i += 1000) {
    process(data[i]);  // 캐시 미스
}

// ✅ 작은 스트라이드
for (int i = 0; i < n; ++i) {
    process(data[i]);  // 캐시 히트
}

문제 4: 포인터 체이싱

증상: 링크드 리스트 순회가 느림

// ❌ 포인터 체이싱 (캐시 미스)
struct Node {
    int value;
    Node* next;
};

int sum = 0;
Node* current = head;
while (current) {
    sum += current->value;
    current = current->next;  // 캐시 미스
}

// ✅ 배열 사용
std::vector<int> values;
int sum = std::accumulate(values.begin(), values.end(), 0);

마무리

C++ 캐시 최적화는 성능을 크게 개선할 수 있는 핵심 기법입니다.

핵심 요약

  1. 공간 지역성

    • 연속 메모리 순차 접근
    • 행 우선 순회

  2. 시간 지역성

    • 최근 접근한 데이터 재사용
    • 루프 안의 변수

  3. False Sharing 방지

    • alignas(64) 사용
    • 캐시 라인 분리

  4. AoS vs SoA

    • SoA가 캐시 친화적
    • 게임, 시뮬레이션에 유리

  5. 블록 처리

    • 행렬 연산 최적화
    • 캐시에 맞는 블록 크기

최적화 체크리스트

기법효과난이도
순차 접근5배낮음
False Sharing 방지3배중간
SoA 구조3배중간
블록 처리2-5배높음
프리페칭1.5배중간

코드 예제 치트시트

// 순차 접근
for (int i = 0; i < n; ++i) { /* ... */ }

// False Sharing 방지
alignas(64) std::atomic<int> counter;

// SoA
struct { std::vector<float> x, y, z; };

// 블록 처리
for (int i = 0; i < n; i += blockSize) { /* ... */ }

// 프리페칭
_mm_prefetch(&data[i + 64], _MM_HINT_T0);

다음 단계

  • 메모리 정렬: C++ 메모리 정렬
  • 캐시 친화적 코드: C++ 캐시 친화적 코드
  • 성능 최적화: C++ 성능 최적화

참고 자료

  • “What Every Programmer Should Know About Memory” - Ulrich Drepper
  • “Optimized C++” - Kurt Guntheroth
  • “Computer Architecture: A Quantitative Approach” - Hennessy, Patterson

한 줄 정리: 캐시 최적화는 공간 지역성, False Sharing 방지, SoA 구조로 성능을 3-5배 개선할 수 있다.