17. 최적화 패턴 - 데이터 지역성

데이터 지역성 패턴은 CPU 캐시를 최대한 활용할 수 있도록 데이터를 배치해 메모리 접근 속도를 높인다.

 

현대 칩의 속도(CPU)는 계속해서 빨라져왔지만 그것은 데이터 연산의 속도가 빨라진 것이지, 데이터를 RAM에서 가져오는 속도는 그다지 빨라지지 않았다.

 

CPU 캐시 - CPU안의 작은 메모리(RAM보다 빠르게 CPU에 데이터를 전달할 수 있음)

칩이 RAM으로부터 데이터를 한 바이트라도 가져와야 할 경우 RAM은 연속된 메모리(캐시 라인)를 선택해 캐시에 복사한다.

 

캐시에서 원하는 데이터를 찾는 것을 캐시 히트(cache hit), 데이터를 찾지 못해 주 메모리(RAM)에서 가져오는 것을 캐시 미스(cache miss)라고 한다. 캐시 미스가 발생하면 CPU는 멈춘다. (RAM에서 데이터를 가져올 때까지 다른 작업을 해야 한다.)

 

자료구조를 잘 만들어서 처리하려는 값들이 메모리 내에서 서로 가까이 붙어 있도록 만드는 것이 캐시 라인에 있는 값들을 

재사용 할 수 있도록 만들기 때문에 전체적인 메모리 접근 속도를 높일 수 있다.

 

17.4 언제 쓸 것인가?

성능 문제가 있을 때 써야 한다. (프로파일링을 해야 한다)

코드 두 지점 사이에 얼마나 시간이 지났는지를 타이머 코드를 넣어서 확인하거나 캐시 사용량을 확인할 수 있는 프로파일러를 사용하여 분석해야 한다.

 

17.5 주의사항

C++에서 인터페이스를 사용하려면 포인터나 레퍼런스를 통해 객체에 접근해야 한다. 포인터를 쓰게 되면 메모리를 여기저기 찾아가야 하기 때문에 데이터 지역성 패턴을 통해서 피하고자 했던 캐시 미스가 발생한다. (가상 함수 호출시 객체의 vtable에서 실제 호출할 함수의 포인터를 찾는다.)

 

데이터 지역성 패턴을 위해서는 디커플링, 추상화의 장점을 포기해야 한다.

 

17.6 예제

컴포넌트 배열 예제

왼쪽 그림의 경우 (데이터 지역성 패턴을 사용하지 않은 경우)

1. 게임 개체가 배열에 포인터로 저장되어 있어서 개체 배열값에 접근할 때마다 포인터를 따라가면서 캐시 미스가 발생한다

2. 게임 개체는 컴포넌트를 포인터로 들고 있어서 다시 한 번 캐시 미스가 발생한다.

update() { // 게임 루프
    for (int i = 0; i < numEntities; i++) {
        entities[i]->ai()->update();
    }
}

 

 

오른쪽 그림의 경우 (데이터 지역성 패턴을 사용한 경우)

1. 게임 개체 배열을 거쳐가지 않아도 모든 개체가 가지고 있는 컴포넌트들에 접근할 수 있다. (각 컴포넌트의 배열 주소를 전역에서 접근할 수 있다면)

// 컴포넌트 자료형 별로 큰 배열에 컴포넌트 객체가 들어간다.
AIComponent* aiComponents = new AIComponent[MAX_ENTITIES];

update() { // 게임 루프
    for (int i = 0; i < numEntities; i++) {
        aiComponents[i].update();
    }
}

 

파티클 시스템 예제

class Particle {
public:
    void update() {}
};

class ParticleSystem { // Particle 객체를 위해 별도로 만든 객체 풀(19장)
public:
    ParticleSystem() : numParticles_(0) {}
    void update();
    
private:
    static const int MAX_PARTICLES = 100000;
    int numParticles_;
    Particle particles_[MAX_PARTICLES];
};

파티클 객체 중 일부가 비활성화되어 처리를 할 필요가 없다면 update를 안해줘도 된다.

for (int i = 0; i < numParticles_; i++) {
    if (particles_[i].isActive()) {
        particles_[i].update();
    }
}

루프가 플래그 값(isActive())를 캐시에 로딩하면서 나머지 파티클 데이터도 같이 캐시에 올리기 때문에 이 파티클이 비활성 상태라면 쓸모없는 값이 캐시에 올라가게 되는 것이다.

아무리 객체를 연속적인 배열에 둔다고 해도, 활성화된 객체가 연속적으로 배열에 있는 것이 아니라면 캐시로 이득을 볼 수가 없다. 활성 객체들을 배열의 맨 앞으로 모으고 비활성 객체는 그 뒤쪽으로 모으는 방법을 사용하면 해결할 수 있다.

void ParticleSystem::activateParticle(int index) {
    assert(index >= numActive_); // 접근한 객체는 비활성 상태여야 함
    
    Particle temp = particles_[numActive_];
    particles_[numActive_] = particles_[index];
    particles_[index] = temp;
    
    numActive_++;
}

Particle 객체 관리를 위한 ParticleSystem에 활성 객체 정렬 관리를 위한 activateParticle함수와 numActive_ 변수가 추가되었다. 임시 Particle 객체에 객체를 복사하고 정렬을 구현한다.

메모리에서 객체를 복사하는 비용과 포인터를 추적하는 비용을 프로파일링을 통해 비교하여 더 나은 방법을 선택하면 될 것이다.

 

빈번한 코드와 한산한 코드 나누기

매 프레임마다 필요한 빈번한(hot) 데이터와 한산한(cold) 데이터를 두 개로 분리하자

 

AI 컴포넌트를 정렬된 연속 배열을 따라가면서 업데이트 한다고 할 때, AI 컴포넌트 내부에 아이템 드랍 정보(한산한 데이터)가 들어 있어서 한 번에 캐시 라인에 들어갈 컴포넌트 개수가 줄어들어 캐시 미스가 더 자주 발생하게 된다.

 

컴포넌트의 데이터 중 자주 빈번한 데이터는 그대로 두고 한산한 부분은 옆으로 치워놓되 필요할 때를 위해 빈번한 부분에서 포인터로 가리키게 한다.

 

class AIComponent {
public:
    void update() {}

private:
    // 빈번한 데이터
    Animation* animation_;
    double energy_;
    Vector goalPos_;
    
    // 한산한 데이터
    LootType drop_;
    int minDrops_;
    int maxDrops_;
    double changeOfDrop_;
};
    
//////////////////////////////
// 두 부분으로 분리한 코드

class AIComponent {
public:
    void update() { }
    
private:
	// 빈번한 데이터는 그대로
    Animation* animation_;
    double energy_;
    Vector goalPos_;
    LootDrop* loot_; // 한산한 데이터는 빈번한 부분에서 포인터로 가리키기
};

class LootDrop {
    friend class AIComponent;
    LootType drop_;
    int minDrops_;
    int maxDrops_;
    double chanceOfDrop_;
};

17.7 디자인 결정

예제에서는 정렬된 단일 자료형 객체 배열에 객체가 들어 있다고 가정했다.

다형성은 어떻게 할 것인가?

사용하지 않는다

ㄴ 상속을 사용하는 경우 동적 디스패치(실행시점에 어떤 메소드를 실행할 지 결정)를 하려면 vtable에서 메서드를 차아본 다음에 포인터를 통해서 실제 코드를 찾아가야 하는데 이는 성능 비용이 든다. 상속을 사용하지 않으면 이를 신경쓰지 않아도 된다.

 

종류별로 다른 배열에 넣는다

ㄴ 종류별로 객체를 나눠놨기 때문에 다형성을 쓰지 않고 일반적인 비가상함수를 호출할 수 있다.

게임 개체는 어떻게 정의할 것인가?

게임 개체 클래스가 자기 컴포넌트를 포인터로 들고 있을 때

ㄴ 게임 개체는 컴포넌트가 실제로 어디에 있는지 신경 쓰지 않기 때문에, 컴포넌트들을 정렬된 배열에 둬서 순회 작업을 최적화할 수 있다.

ㄴ 개체로부터 개체 컴포넌트를 쉽게 얻을 수 있다.

ㄴ 컴포넌트를 메모리에서 옮기기가 어렵다. (활성 컴포넌트가 앞에 모여 있도록 유지하려면 개체가 가리키는 포인터도 바꿔줘야 한다.)

 

게임 개체 클래스가 컴포넌트를 ID로 들고 있을 때

ㄴ 컴포넌트 배열에서 컴포넌트의 위치가 바뀌어도 개체로부터 개체 컴포넌트를 찾을 수 있도록 컴포넌트별로 유일한 ID를 발급한 뒤에 배열에서 찾아도 되고, 컴포넌트 배열에서의 현재 위치를 ID와 매핑하는 해시 테이블로 관리해도 된다.

 

게임 개체가 단순히 ID일 때

ㄴ 개체의 동작과 상태를 개체 클래스로부터 전부 컴포넌트로 옮김

ㄴ 컴포넌트끼리 상호작용하기 위해 모든 컴포넌트는 자신을 소유하는 개체의 ID를 기억하고, 자기와 같은 개체 ID를 가진 컴포넌트에 접근해야 한다.

ㄴ 개체는 단순한 값이 된다.