TIL_057: 데이터 지향적 설계와 최적화

김펭귄·2025년 11월 3일
C++TILunreal

Today What I Learned (TIL)

목록 보기
57/142

오늘 학습 키워드

  • 데이터 지향적 설계

  • ECS

  • 최적화

  • 가상메모리

1. 캐시 hit와 miss

  • 코드를 구현할 때, 객체지향적 코드도 좋지만, 데이터 지향적인 코드도 고려하면서 짜면 좋음

  • 컴퓨터 구조 전공에서 배웠듯이 캐시 hit가 높고 캐시 miss가 낮아야 코드 동작 시간이 짧아짐

  • 캐시가 공간적 지역성과 시간적 지역성이라는 성질을 이용하여 만들어졌으므로, 최대한 캐시 Hit를 높이는 방향으로 코드를 구현

    • 공간적 지역성 : 연속된 메모리 위치에 다시 접근할 가능성이 높음 (arr[0], arr[1]..)
    • 시간적 지역성 : 최근에 접근한 데이터에 다시 접근할 가능성 높음

  • 따라서 데이터를 사용할 때 가능한 한 번에 모든 처리를 하고, 연속적인 데이터를 같이 사용하는 것이 성능적 측면에서 우수

// 행 우선 접근. 연속된 데이터에 순차적으로 접근하므로 성능 괜찮음
for (int i = 0; i < arr.size(); i++) {
	for (int j = 0; j < arr[i].size(); j++) {
    	sum += arr[i][j];
    }
}

// 열 우선 접근. 열 개수만큼의 데이터를 건너뛰어 접근하므로 캐시 miss 많이 발생함
for (int j = 0; j < arr[0].size(); j++) {
	for (int i = 0; i < arr.size(); i++) {
    	sum += arr[i][j];
    }
}

2. 객체 지향의 성능적 한계

  • 객체 지향 설계는 코드의 가독성과 유지보수성에는 뛰어나지만, 성능 측면에서는 한계가 있음
class GameObject {
public:
    virtual void Update(float deltaTime) = 0;  // 가상 함수
    virtual void Render() = 0;

protected:
    Transform transform;
    std::string name;           // 사용하지 않을 수도 있는 데이터
    bool isActive;
    // ... 많은 다른 멤버들
};

class Enemy : public GameObject {
    AI* aiComponent;            // 포인터 -> 캐시 미스 가능성
    Renderer* renderer;
    Physics* physics;

public:
    void Update(float deltaTime) override {
        // 여러 컴포넌트에 접근 -> 메모리 점프
        aiComponent->Update(deltaTime);
        physics->Update(deltaTime);
    }
};

Enemy* enemy1 = new Enemy(); // 1000
Enemy* enemy2 = new Enemy(); // 5000
Enemy* enemy3 = new Enemy();

// 사용
std::vector<std::unique_ptr<GameObject>> gameObjects;
for (auto& obj : gameObjects) {
    obj->Update(deltaTime);  // 가상 함수 호출, 예측 불가능한 메모리 접근
}

가상 함수 호출 비용

  • 일반적인 함수 호출의 경우, 이미 컴파일 타임에 함수의 위치가 정해져있으므로, 바로 호출이 가능

  • CPU는 다음에 접근할 메모리의 위치를 예측하는 기능도 있어 미리 예측하여 최적화

  • 가상함수의 경우, 호출하게 되면 가상함수 테이블을 가리키는 포인터를 읽음

  • 가상 함수 테이블에 접근하여 해당 가상함수를 override한 함수 포인터를 또 읽음

  • 그리고 해당 함수로 접근하며, 런타임에 2번의 메모리 접근이 추가적으로 발생

  • CPU의 다음 메모리 접근도 예측할 수 없어 성능이 많이 떨어짐

동적할당 비용

  • new를 이용하여 Heap에 동적으로 적 객체를 생성하였음

  • 이때 동적할당의 경우 연속적으로 할당되는 것이 아니라, 메모리 블록들이 흩어져서 할당됨

  • 따라서 CPU가 멀리 Jump를 해야하며, 너무 멀기 때문에 캐시도 의미 없어짐

  • new[]를 이용하여 연속적으로 할당하는 것이 효율적

  • 애초에 stack에 할당되는 지역변수는 연속적으로 할당됨

포인터 체이싱

  • enemy->aiComponent->Update(deltaTime) 와 같이 여러 포인터를 따라가는 상황

  • 불연속적인 메모리에 Jump하므로 캐시 miss확률이 높아짐

  • 별개로, 리스트와 트리 구조도 연속적인 메모리 구조가 아니기에 Traverse할 때 포인터 체이싱이 발생

3. 데이터 지향 설계

  • 객체지향적 설계의 성능적 한계로 인해 이제는 데이터를 중심으로 코드를 구현

  • 각 객체마다 자신의 데이터와 기능을 가진것과는 달리, 각 객체의 데이터들을 비슷한 것끼리 묶어서 저장

// 모든 객체의 데이터들을 하나로 묶어 저장
struct TransformData {
    std::vector<Vector3> positions;
    std::vector<Vector3> velocities;
    size_t count;
};

struct RenderData {
    std::vector<Matrix4> worldMatrices;
    std::vector<MaterialID> materials;
    std::vector<MeshID> meshes;
    size_t count;
};

void UpdatePhysics(TransformData& transforms, float deltaTime) {
    for (size_t i = 0; i < transforms.count; ++i) {
        transforms.velocities[i] += transforms.accelerations[i] * deltaTime;
        transforms.positions[i] += transforms.velocities[i] * deltaTime;
    }
}

  • 객체지향은 도시락통이라면, 데이터지향은 샐러드코너, 양식코너 같이 코너가 있는 뷔페

  • 데이터가 연속적으로 존재하기에 캐시 Hit가 매우 높음

  • 객체지향이었으면, 하나의 캐시라인에 필요 없는 다른 데이터도 들어가지만, 이 데이터는 연속적으로 존재하므로 낭비가 없음

  • CPU의 메모리 접근 예측도 성공해서 Pipeline이 끊기지 않고 아주 빠름

설계 핵심 원칙

  1. 데이터가 코드를 이끈다 : 데이터 레이아웃을 먼저 고려

    • 어떻게 데이터가 저장되고 조직되는지(메모리 레이아웃)를 중심으로 생각하며 구현

    • 데이터가 CPU 캐시에 효율적으로 적재되고 빠르게 접근될 수 있도록 데이터의 메모리 구조를 우선 고려하는 방식

  2. 변환 중심 사고 : Input → Process → Output

    • 프로그래밍을 데이터 변환 과정으로 바라보기

    • 입력 데이터를 받아 필요한 처리를 수행하고 결과를 출력하는 형태로 설계

    • 병렬 처리에 유리한 구조여서 효율적

  3. 캐시 친화성 : 함께 사용되는 데이터는 연속적으로 배치하여 캐시 Hit 높이기

  4. 배치 처리 : 같은 연산을 여러 데이터에 일괄 적용

    • 같은 유형의 연산(작업)을 다수의 데이터에 한꺼번에 묶어서 수행하는 기법

    • 적 캐릭터 위치를 업데이트하는 작업을 하나씩 호출하는 대신, 모든 위치 데이터를 연속적으로 모아 한 번에 업데이트

    • 데이터를 모아 일괄 처리하면 캐시 효율이 증가하고, 분기(branch)나 함수 호출 오버헤드가 줄어들며, 벡터화(SIMD)와 병렬 처리 활용에도 유리함

4. AoS vs SoA

AoS (Array of Structures)

  • 구조체를 배열로 사용
struct Particle {
    Vector3 position;    // 12 bytes
    Vector3 velocity;    // 12 bytes
    float life;          // 4 bytes
    Color color;         // 16 bytes 
};                       // 44 bytes per particle

std::vector<Particle> particles(1000);	// AoS

// 위치만 업데이트
for (auto& particle : particles) {
    particle.position += particle.velocity * deltaTime;
}
  • 위치만 업데이트하려해도, 주변포함해서 캐시라인으로 가져오므로, 필요없는 life와 color도 같이 가져오게 됨

SoA (Sturctures of Array)

  • 배열들을 구조체로 만든 것
struct ParticleSystem {
    std::vector<Vector3> positions;   // 연속적으로 데이터 존재
    std::vector<Vector3> velocities;  
    std::vector<float> lives;         
    std::vector<Color> colors;        
    size_t count;
};

ParticleSystem particles;

// 위치만 업데이트하는 경우
for (size_t i = 0; i < particles.count; ++i) {
    particles.positions[i] += particles.velocities[i] * deltaTime;
}

  • 필요한 위치데이터가 벡터로 연속적으로 존재

  • 캐시라인으로 64byte가져왔을 때 옆에 있는 다른 위치데이터도 같이 가져옴

  • 다음 계산에 사용하므로 캐시 Hit발생하여 성능 좋아짐

각 방식의 장점

  • AoS

    1. 위 예시와 달리, 객체 내의 모든 데이터를 다 사용할 때는 오히려 다 가져오니까 Hit가 높아짐
    2. 코드의 가독성과 직관성이 높음

  • SoA

    1. 위 사례처럼 특정 데이터에만 자주 접근할 때
    2. SIMD 벡터화 같은 병렬 처리에 좋음

5. ECS (Entity Component System)

  • 객체 지향 설계는 상속하면서 필요한 기능을 추가해주었음
// 전통적인 상속 기반
class GameObject { ... };
class Character : public GameObject { ... };
class Player : public Character { ... };
class Enemy : public Character { ... };
class FlyingEnemy : public Enemy { ... };
  • 이젠 컴포넌트를 미리 만들어놓고, 각 엔티티가 필요하면 가져와 사용
// ECS 방식
struct Entity {
    uint32_t id;	// 엔티티 식별하는 고유 id
};

// 각 컴포넌트
struct Position { Vector3 value; };
struct Velocity { Vector3 value; };
struct Health { float current, max; };
struct Renderer { MeshID mesh; MaterialID material; };
struct AI { AIType type; float aggroRange; };

class World {
    // 컴포넌트별로 데이터를 분리 저장
    std::vector<Position> positions;
    std::vector<Velocity> velocities;
    std::vector<Health> healths;
    std::vector<Renderer> renderers;
    std::vector<AI> ais;

    // 엔티티마다 어떤 컴포넌트 가지는지 bitmask로 표현
    std::vector<std::bitset<32>> componentMasks;
};

// 시스템: 특정 컴포넌트 조합을 가진 엔티티들을 일괄 처리
void MovementSystem(World& world) {
    for (size_t i = 0; i < world.entities.size(); ++i) {
        if (world.HasComponents<Position, Velocity>(i)) {
            world.positions[i].value += world.velocities[i].value * deltaTime;
        }
    }
}

  • 엔티티는 그냥 뼈대로, 컴포넌트 추가/제거하면서 사용하므로 게임 도중 유연성이 정말 좋다

  • 같은 컴포넌트끼리 연속으로 묶여있으므로, movement 일괄 처리하고, 데미지 일괄 처리하는 등 캐시 Hit가 높아 성능이 엄청 좋음

  • 또 각 컴포넌트가 분리되어 있어, 이동 쓰레드, 데미지 쓰레드, 이런 식으로 쓰레드로 나뉠 때 동시에 실행 가능하며 서로 간섭도 안 함

  • 필요 없는 컴포넌트는 즉시 제거가 가능하므로 메모리 효율적임

  • 이러한 장점으로 AI 객체를 수만마리 만들어도 일괄 처리하면서 성능 좋음

6. 최적화 팁

같은 함수 반복 호출 금지

  • 함수 호출 자체가 overhead

  • 함수 호출마다 서로 다른 데이터에 접근하거나 메모리 지역성이 떨어지는 경우, CPU 캐시에서 데이터를 자주 불러와야 해 캐시 히트율이 낮아지고 메모리 접근 지연이 발생

  • CPU의 분기 예측 실패 및 파이프라인 스톨

알고리즘 개선

  • O(n²) → O(nlogn)

  • 모든 객체들 조사하지 말고, 월드를 구역으로 쪼개서 이벤트가 발생한 그 구역만 조사하는 방식으로

  • sqrt는 무거운 연산이어서, sqrt(a) == 5보다 a == 25로 사용

  • 나눗셈 역시 무거운 연산으로 곱셈 사용하기 a / 2 대신 a * 0.5

Batch 처리

  • 지금까지 배운 것처럼 한번에 일괄 처리하자
// 개별 처리 - 비효율적
for (auto& enemy : enemies) {
    enemy.Update();
    enemy.CheckCollision();
    enemy.UpdateAnimation();
}

// 배치 처리 - 효율적
UpdateAllEnemyPositions(enemies);    // 모든 위치를 한 번에
CheckAllCollisions(enemies);         // 모든 충돌을 한 번에
UpdateAllAnimations(enemies);        // 모든 애니메이션을 한 번에
  • 캐시 Hit높고, 멀티 쓰레딩, CPU 예측 등 성능이 좋아짐

SIMD (Single Instruction, Multiple Data)

  • 하나의 명령으로 많은 데이터 한 번에 처리하기

  • 딥러닝에서 벡터와 행렬로 수 많은 데이터를 한 번에 처리하는 것과 비슷

// 일반적인 벡터 덧셈
for (int i = 0; i < count; ++i) {
    result[i] = a[i] + b[i];
}	// count번 계산해야함

// SIMD를 활용한 벡터 덧셈 (4개씩 동시 처리)
#include <immintrin.h>
for (int i = 0; i < count; i += 4) {
    __m128 va = _mm_load_ps(&a[i]);		// 4개 int 한 번에 가져와서
    __m128 vb = _mm_load_ps(&b[i]);
    __m128 vr = _mm_add_ps(va, vb);		// 4개 한 번에 더하기
    _mm_store_ps(&result[i], vr);
}

메모리 풀링

  • 동적할당(new)은 항상 오래 걸림

  • 심지어 힙 용량 부족하여, OS에 메모리 더 달라고 System Call로 요청하면 더 오래걸림

  • 새로 할당되고 또 제거되고 반복되면 메모리 단편화 발생

  • 단편화 없애려고 힙 메모리 정리되는 것도 성능 떨어뜨림

  • 앞에서 말했듯이, bullet1과 bullet2가 멀리 떨어져있게되므로 캐시가 무용지물됨

  • 운영체제에서 배운 Pooling을 이용해 처음부터 큰 메모리 할당받고 그걸 사용

class BulletPool {
private:
    std::vector<Bullet> bullets;      // 미리 할당된 총알들
    std::queue<size_t> available;     // 사용 가능한 인덱스들
    std::vector<bool> isActive;       // 각 총알의 활성화 상태

public:
    BulletPool(size_t maxCount) : bullets(maxCount), isActive(maxCount, false) {
        // 모든 인덱스를 사용 가능 목록에 추가
        for (size_t i = 0; i < maxCount; ++i) {
            available.push(i);
        }
    }

    Bullet* GetBullet() {
        if (available.empty()) {
            return nullptr;  // 풀이 가득 참
        }
        
        size_t index = available.front();
        available.pop();
        isActive[index] = true;
        
        return &bullets[index];  // 이미 할당된 메모리 재사용
    }

    void ReturnBullet(Bullet* bullet) {
        // 포인터로부터 인덱스 계산
        size_t index = bullet - &bullets[0];
        
        // 상태 초기화
        bullet->Reset();
        isActive[index] = false;
        
        // 풀에 반환
        available.push(index);
    }
    
    void UpdateAll(float deltaTime) {
        for (size_t i = 0; i < bullets.size(); ++i) {
            if (isActive[i]) {
            	// 데이터 지향 설계
                bullets[i].position += bullets[i].velocity * deltaTime;
                bullets[i].lifeTime -= deltaTime;
                
                if (bullets[i].lifeTime <= 0) {
                    ReturnBullet(&bullets[i]);
                }
            }
        }
    }
};

  • new, delete는 오래걸리지만, Pooling하면 큐에서 push,pop밖에 없으므로 성능 엄청 좋음

  • 아예 메모리 상한치를 잡아놓으니까 총알 8000발 쏜다해서 메모리 터지지도 않음

7. 데이터 지향 설계가 좋은 경우

  • 많은 객체에서 같은 데이터를 처리할 때

  • 파티클, AI, Physics 등 대량으로 일괄 처리해야할때

  • Profiling했을 때 성능 개선이 필요할 때

  • 데이터를 분리하여 멀티쓰레딩이 필요할 때

  • FPS같이 성능 필수일 때

8. 메모리-캐시와 Storage-메모리

  • 캐시에 대해 공부하다보니, 캐시 미스시 발생하는 동작과정이 Storage와 메모리의 동작과 비슷하다고 느껴 이 부분에 대해 다시 공부해보며 정리하였음

  • 가상 메모리는 운영체제가 프로그램마다 독립적인 가상 주소 공간을 제공하여, 마치 프로그램 전체가 메모리에 올라와 있는 것처럼 보이게 하는 기술

  • 실제로는 필요한 부분의 코드와 데이터만 물리 메모리에 적재하고, 나머지는 스토리지(디스크)에 있다가 필요할 때 불러옴

동작 원리

  • 가상 메모리는 운영체제와 CPU의 메모리 관리 장치(MMU)가 협력해 가상 주소를 물리 주소로 매핑하며, 프로그램에 필요한 페이지(보통 4KB)를 동적으로 메모리에 올림

  • 캐시는 CPU가 메모리에 접근할 때, 먼저 캐시에 해당 데이터가 있는지 검사하고, 없으면 메인 메모리에서 64바이트 단위인 캐시 라인을 가져와 캐시에 저장

  • 그래서 데이터가 캐시에 없으면 그 다음에 메모리로 가고, 메모리에도 없으면 Storage로 가서 4KB의 페이지를 메모리에 적재

profile
김펭귄
반갑습니다
이전 포스트

TIL_056: 리타겟팅, 총알 발사

다음 포스트

TIL_058: 언리얼 4대 Framework

0개의 댓글