Cache Locality

# Cache Locality

> 캐시 히트/미스, 메모리 접근 패턴 최적화

## 학습 목표

- CPU 캐시의 동작 원리와 계층 구조를 이해한다
- 캐시 히트/미스가 성능에 미치는 영향을 파악한다
- 메모리 접근 패턴을 최적화하여 캐시 효율을 높인다

## 내용

### CPU 캐시 계층 구조

```
CPU 레지스터  ~1 사이클
L1 캐시        ~4 사이클   (32~64 KB)
L2 캐시       ~12 사이클   (256 KB ~ 1 MB)
L3 캐시       ~30 사이클   (수 MB ~ 수십 MB)
RAM          ~100 사이클   (수 GB)
```

### 캐시 미스 예시 (열 우선 접근 - 나쁜 예)

```c
// ❌ 캐시 비효율: C는 행 우선(row-major) 저장
int matrix[N][N];
for (int j = 0; j < N; j++)        // 열 우선 순회
    for (int i = 0; i < N; i++)
        sum += matrix[i][j];        // 캐시 미스 빈발
```

### 캐시 히트 최적화 (행 우선 접근 - 좋은 예)

```c
// ✅ 캐시 효율적: 연속된 메모리 접근
for (int i = 0; i < N; i++)        // 행 우선 순회
    for (int j = 0; j < N; j++)
        sum += matrix[i][j];        // 캐시 히트
```

### 구조체 배열 vs 배열 구조체 (AoS vs SoA)

```c
// AoS (Array of Structures) - 특정 필드만 처리할 때 비효율
typedef struct { float x, y, z, w; } Vec4;
Vec4 particles[N];

// SoA (Structure of Arrays) - SIMD/벡터화에 유리
struct { float x[N], y[N], z[N], w[N]; } particles;
// x만 처리할 때 연속 메모리 접근 → 캐시 친화적
```

### 프리페칭 힌트

```c
// GCC 내장 프리페치
for (int i = 0; i < N; i++) {
    __builtin_prefetch(&arr[i + 16], 0, 1); // 미리 캐시에 로드
    process(arr[i]);
}
```

## 참고

- 캐시 라인 크기는 보통 64바이트이므로 구조체 크기를 64바이트 배수로 맞추면 유리하다
- `valgrind --tool=cachegrind`로 캐시 미스를 분석할 수 있다

// COMMENTS

ON THIS PAGE