컴퓨터 구조 — 캐시 메모리와 지역성 원리

개요 — 캐시가 게임 성능을 결정하는 이유

현대 CPU는 메모리보다 수백 배 빠릅니다. 그러나 실제 프로그램에서 CPU는 메모리를 기다리는 시간이 계산하는 시간보다 길 때가 많습니다.

ECS(Entity Component System)가 객체 지향 방식보다 빠른 핵심 이유
배열과 링크드 리스트의 순회 속도 차이가 이론 복잡도를 벗어나는 이유
오픈 월드 게임에서 레벨 스트리밍이 갑자기 느려지는 원인
데이터 지향 설계(Data-Oriented Design)가 성능을 극적으로 향상시키는 원리

캐시 메모리와 지역성 원리를 이해하면 이론적으로 동일한 알고리즘도 구현 방식에 따라 10배 이상 성능 차이를 만들 수 있음을 알게 됩니다.

1. 메모리 계층 구조

CPU와 메모리 간의 속도 차이를 극복하기 위해 여러 계층의 저장장치를 사용합니다.

메모리 계층 구조 (속도 빠름 -> 느림, 용량 작음 -> 큼):

┌─────────────┐
│  CPU 레지스터  │  ~0.3ns, 수십 바이트
├─────────────┤
│    L1 캐시   │  ~1ns, 32~64KB (코어당)
├─────────────┤
│    L2 캐시   │  ~4ns, 256KB~1MB (코어당)
├─────────────┤
│    L3 캐시   │  ~10ns, 8~64MB (모든 코어 공유)
├─────────────┤
│    주 메모리  │  ~100ns, 8~64GB (RAM)
├─────────────┤
│  NVMe SSD   │  ~0.1ms, 1~4TB
├─────────────┤
│    HDD      │  ~10ms, 수 TB
└─────────────┘

L1 캐시 vs RAM 접근 시간 비교:
L1 캐시 히트: 1ns
RAM 접근: 100ns
-> 100배 차이!

캐시 라인 (Cache Line)

캐시는 데이터를 바이트 단위가 아닌 캐시 라인(보통 64바이트) 단위로 로드합니다.

메모리에서 1바이트를 읽어도:
-> 해당 바이트가 포함된 64바이트 캐시 라인 전체가 캐시로 로드됨

예시: int arr[16] (int = 4바이트, 배열 전체 = 64바이트 = 캐시 라인 1개)
arr[0] 접근 -> 캐시 미스 발생, arr[0]~arr[15] 전체가 캐시로 로드
arr[1] 접근 -> 캐시 히트! 이미 캐시에 있음
arr[2]~arr[15] 접근 -> 모두 캐시 히트

-> 배열 순서 접근이 캐시에 매우 유리

2. 지역성 원리 (Principle of Locality)

프로그램이 메모리에 접근하는 패턴에는 두 가지 지역성이 있습니다.

시간 지역성 (Temporal Locality)

최근에 접근한 데이터는 곧 다시 접근할 가능성이 높습니다.

// 시간 지역성 예시: 루프 내 변수 반복 접근
int sum = 0;  // sum은 매 반복마다 접근 -> 캐시에 계속 유지

for (int i = 0; i < N; ++i)
{
    sum += arr[i];  // sum: 시간 지역성, arr[i]: 공간 지역성
}

// 게임 루프에서 DeltaTime, 카메라 위치 등이 매 프레임 접근됨
// -> 이러한 데이터를 hot data라 부르며 캐시에 유지됨

공간 지역성 (Spatial Locality)

최근에 접근한 데이터 근처의 메모리에도 곧 접근할 가능성이 높습니다.

// 좋은 공간 지역성: 연속된 배열 순차 접근
for (int i = 0; i < N; ++i)
{
    Process(arr[i]);  // arr[0], arr[1], arr[2]... 순서로 접근
}
// arr[i] 접근 시 64바이트 캐시 라인이 로드되어 다음 원소들도 캐시됨

// 나쁜 공간 지역성: 연결 리스트 순회
Node* cur = head;
while (cur != nullptr)
{
    Process(cur->value);
    cur = cur->next;  // next가 메모리 어디에 있는지 모름
}
// 각 노드가 메모리 곳곳에 산재 -> 매 노드마다 캐시 미스 발생 가능

3. 캐시 미스 유형

3C 모델

유형	이름	원인	해결책
Compulsory Miss	강제적 미스	데이터를 처음 접근할 때 (불가피)	프리페칭
Capacity Miss	용량 미스	작업 세트가 캐시보다 클 때	데이터 분할, 캐시 크기 고려
Conflict Miss	충돌 미스	캐시 셋에 너무 많은 데이터가 매핑될 때	데이터 배치 최적화

캐시 미스 비용 측정

// 캐시 미스 효과 실험

constexpr int N = 1024 * 1024;  // 4MB 배열 (L3 캐시 초과 가능)
int arr[N];

// 순차 접근 (캐시 친화적)
// 예상: 빠름 (공간 지역성 활용)
for (int i = 0; i < N; ++i)
    arr[i] *= 2;

// 랜덤 접근 (캐시 비친화적)
// 예상: 수십 배 느림 (매번 캐시 미스)
for (int i = 0; i < N; ++i)
    arr[rand() % N] *= 2;

// 실제 측정 결과 (i7-9700K 기준):
// 순차 접근: ~1.5GB/s
// 랜덤 접근: ~0.1GB/s (15배 차이)

4. 캐시 친화적 자료구조 설계

행 우선 순서 (Row-Major Order)

// 2D 배열 접근 — C/C++는 행 우선 저장
int matrix[1024][1024];

// 캐시 친화적: 행 우선 접근
for (int row = 0; row < 1024; ++row)
    for (int col = 0; col < 1024; ++col)
        sum += matrix[row][col];  // matrix[row][0], [row][1], [row][2]... 연속

// 캐시 비친화적: 열 우선 접근
for (int col = 0; col < 1024; ++col)
    for (int row = 0; row < 1024; ++row)
        sum += matrix[row][col];  // matrix[0][col], [1][col], [2][col]... 불연속
                                  // 매 접근마다 캐시 미스 발생

// 성능 차이: 수 배 ~ 수십 배

구조체 배열 vs 배열의 구조체

// AoS (Array of Structures): 일반적인 객체 지향 방식
struct Entity_AoS
{
    float x, y, z;    // 위치
    float vx, vy, vz; // 속도
    float hp;         // 체력
    bool  isActive;   // 활성 여부
    // ... 더 많은 필드
};
Entity_AoS entities_AoS[10000];

// 위치만 업데이트하는 경우:
for (int i = 0; i < 10000; ++i)
{
    if (entities_AoS[i].isActive)
    {
        entities_AoS[i].x += entities_AoS[i].vx;  // 캐시 라인: x,y,z,vx,vy,vz,hp,isActive 전부 로드
        entities_AoS[i].y += entities_AoS[i].vy;  // 실제 사용: x, y, vx, vy만 필요
        entities_AoS[i].z += entities_AoS[i].vz;  // 나머지는 캐시 공간 낭비
    }
}

// SoA (Structure of Arrays): 데이터 지향 방식
struct Entities_SoA
{
    float x[10000], y[10000], z[10000];    // 위치 배열
    float vx[10000], vy[10000], vz[10000]; // 속도 배열
    float hp[10000];                        // 체력 배열
    bool  isActive[10000];                  // 활성 여부 배열
};
Entities_SoA entities_SoA;

// 위치만 업데이트하는 경우:
for (int i = 0; i < 10000; ++i)
{
    if (entities_SoA.isActive[i])
    {
        entities_SoA.x[i] += entities_SoA.vx[i];  // x 배열에서 연속 접근
        entities_SoA.y[i] += entities_SoA.vy[i];  // y 배열에서 연속 접근
        entities_SoA.z[i] += entities_SoA.vz[i];  // z 배열에서 연속 접근
    }
}
// 캐시 라인 활용률: x[i]를 읽으면 x[i+1]~x[i+15]도 캐시됨
// 실제 필요한 데이터만 캐시에 로드됨

5. 데이터 지향 설계 (Data-Oriented Design, DOD)

DOD는 캐시 효율성을 극대화하기 위해 알고리즘보다 데이터 배치를 먼저 설계하는 패러다임입니다.

핫 데이터 / 콜드 데이터 분리

// 매 프레임 업데이트되는 데이터(hot)와
// 가끔 접근하는 데이터(cold)를 분리

// 나쁜 예: hot/cold 데이터 혼재
struct Enemy
{
    // Hot data (매 프레임 접근)
    float x, y, z;
    float vx, vy, vz;
    float hp;

    // Cold data (사망 시, 이벤트 발생 시만 접근)
    std::string name;           // 이름 (드물게 필요)
    std::string deathAnimation; // 사망 애니메이션 (가끔 필요)
    int         dropTable[100]; // 드롭 테이블 (죽을 때만 필요)
    // Cold data가 Hot data와 같은 캐시 라인에 로드되어 낭비
};

// 좋은 예: hot/cold 데이터 분리
struct EnemyTransform  // Hot: 매 프레임 접근
{
    float x, y, z;
    float vx, vy, vz;
    float hp;
};

struct EnemyMeta  // Cold: 드물게 접근
{
    std::string name;
    std::string deathAnimation;
    int         dropTable[100];
};

EnemyTransform hotData[1000];   // 연속 메모리, 캐시 효율 높음
EnemyMeta      coldData[1000];  // 별도 관리

Unity DOTS와 Unreal의 Mass Entity

// Unity DOTS (Data-Oriented Technology Stack)
// ECS 방식으로 캐시 친화적 설계

// Component: 순수 데이터 (SoA 방식으로 자동 배치됨)
public struct Translation : IComponentData
{
    public float3 Value;
}

public struct Velocity : IComponentData
{
    public float3 Value;
}

// System: 같은 컴포넌트를 가진 엔티티들을 배치(Chunk) 단위로 처리
public class MovementSystem : SystemBase
{
    protected override void OnUpdate()
    {
        float deltaTime = Time.DeltaTime;

        // 모든 Translation, Velocity 컴포넌트를 연속 메모리에서 순차 처리
        // -> 캐시 미스 최소화
        Entities
            .ForEach((ref Translation translation, in Velocity velocity) =>
            {
                translation.Value += velocity.Value * deltaTime;
            })
            .ScheduleParallel();
    }
}

6. 프리페칭 (Prefetching)

캐시 미스를 숨기기 위해 데이터를 미리 캐시에 로드하는 기술입니다.

// 소프트웨어 프리페칭 (컴파일러 힌트)
for (int i = 0; i < N; ++i)
{
    // 미래에 접근할 데이터를 미리 캐시로 로드
    __builtin_prefetch(&arr[i + 16], 0, 1);  // GCC/Clang
    // _mm_prefetch((char*)&arr[i + 16], _MM_HINT_T0);  // Windows MSVC

    Process(arr[i]);
}

// 하드웨어 프리페치:
// CPU가 순차 접근 패턴을 감지하면 자동으로 다음 캐시 라인을 미리 로드
// -> 순차 접근 코드에서는 자동으로 적용됨
// -> 불규칙 접근 패턴에서는 효과 없음

7. 캐시 최적화 실전 체크리스트

게임 프로그래머를 위한 캐시 최적화 체크리스트:

데이터 배치:
[ ] 자주 같이 접근하는 데이터는 같은 구조체/배열에 모았는가?
[ ] hot data와 cold data를 분리했는가?
[ ] 배열 크기가 캐시 라인(64바이트)의 배수인가?

알고리즘:
[ ] 2D 배열 접근이 행 우선 순서인가?
[ ] 링크드 리스트 대신 연속 배열을 사용할 수 있는가?
[ ] 랜덤 접근을 순차 접근으로 변환할 수 있는가?

구조 설계:
[ ] AoS를 SoA로 변환하면 이득이 있는가?
[ ] 메모리 풀을 사용해 단편화를 줄였는가?
[ ] 가상 함수 테이블(vtable) 간접 참조가 병목인가?

측정:
[ ] Intel VTune, Perf, AMD uProf 등으로 캐시 미스율을 측정했는가?
[ ] 최적화 전후 성능을 실제로 측정했는가?

8. 면접 핵심 정리

캐시 메모리란? CPU와 주 메모리 사이의 속도 차이를 극복하기 위한 고속 소형 메모리입니다. L1/L2/L3 계층으로 구성되며, CPU에 가까울수록 빠르고 작습니다.

공간 지역성과 시간 지역성의 차이는? 공간 지역성은 접근한 메모리 근처에도 곧 접근할 가능성이 높다는 원리이고, 시간 지역성은 최근 접근한 데이터를 곧 다시 접근할 가능성이 높다는 원리입니다.

AoS와 SoA의 차이는? AoS(Array of Structures)는 각 객체의 모든 필드가 연속된 구조체로, SoA(Structure of Arrays)는 필드별로 별도 배열에 저장하는 방식입니다. 특정 필드만 처리하는 경우 SoA가 캐시 효율이 높습니다.

캐시 미스가 성능에 미치는 영향은? L1 캐시 히트는 ~1ns이지만 RAM 접근은 ~100ns로 100배 차이입니다. 캐시 미스율이 높으면 CPU가 대부분의 시간을 메모리 대기에 소비해 연산 능력이 크게 저하됩니다.