데이터 지역성

https://tsyang.tistory.com/68

Data-oriented Design (데이터 지향 설계, DoD)

 

데이터 지역성을 활용해야 하는 이유와 아이디어는 위 글에 써있다. 이 글에서는 구현에 대해 다룬다.

 

 

 

데이터 지역성 패턴

---

데이터 지역성 패턴은 성능 문제가 있을 때 써야한다. 필요 없는 곳에 적용해봐야 코드만 복잡해지고 유연성만 떨어진다. 특히 데이터 지역성 패턴은 성능 문제가 캐시 미스 때문인지 확인해야 한다.

 

구현

컴포넌트로 구성된 Entity가 있다.

class GameEntity
{
public:
	AIComponent* ai() { return ai_; }
	PhysicsComponent* physics() { return physics_; }
	RenderComponent* render() { return render_; }
	
private:
	AIComponent* ai_;
	PhysicsComponent* physics_;
	RenderComponent* render_;
};

 

게임 월드는 Entity 의 배열이 아니라 자료형별로 큰 배열을 저장한다.

AIComponent* aiComponents = new AIComponent[MAX_ENTITIES];
PhysicsComponent* physicsComponents = new PhysicsComponent[MAX_ENTITIES];
RenderComponent* renderComponents = new RenderComponent[MAX_ENTITIES];

 

게임 루프는 각 컴포넌트를 대략 다음과 같이 업데이트한다.

while(playing)
{
	for (int i = 0; i < numEntities; ++i)
		aiComponents[i].update();

	for (int i = 0; i < numEntities; ++i)
		physicsComponent[i].update();

	for (int i = 0; i < numEntities; ++i)
		renderComponent[i].update();
}

 

이렇게 되면 Entity들을 순회할때보다 훨씬 빨라진다. 캡슐화가 많이 깨지지도 않았다. GameEntity 클래스는 배열에 있는 객체를 가리킨다. 

 

 

주의사항

데이터 지역성 패턴을 위해서는 추상화 일부를 희생해야 한다. 왜냐하면 상속이나 인터페이스를 쓰기 위해서는 포인터나 레퍼런스를 사용하게 되는데 이렇게 포인터를 따라가는 것은 캐시 미스를 유발하기 때문이다.

 

 

---

 

데이터 정렬하기

---

게임 내에서 파티클을 관리하는 코드인 ParticleSystem을 보자. ParticleSystem은 객체 풀을 이용해 파티클을 하나의 연속적인 배열에 둔다.

 

class ParticleSystem
{
public:
	ParticleSystem() : numParticles_(0){}
	void update();

private:
	static constexpr int MAX_PARTICLES = 100;
	int numParticles_;
	Particle particles_[MAX_PARTICLES];
};

 

파티클 시스템의 update()에서는 활성화된 파티클들을 업데이트 해준다.

void ParticleSystem::update()
{
	for (int i = 0; i < numParticles_; ++i)
		if (particles_[i].isActive())	//활성화된 객체만 업데이트
			particles_[i].update();
}

 

그러나 이런 방식은 비활성 파티클이 많은 경우 캐시 효율이 떨어진다. 게다가 isActive()를 통해 활성화 여부를 체크하는 행위는 CPU가 분기 예측 실패(branch misprediction)을 겪으면서 성능이 떨어진다.

 

따라서 조건문을 사용하지 않으면서, 활성화된 객체가 연속적으로 존재하는 배열을 만든다면 좋을 것이다. 이를 위해서 데이터를 정렬하여 활성화된 객체만 앞으로 모아두면 된다.

void ParticleSystem::update()
{
	//numActive : 활성화된 객체 수
	for (int i = 0; i < numActive_; ++i)
		particles_[i].update();
}

 

그런데 어떻게 모아줄까? 처음에는 모든 파티클이 비활성 상태일 것이다. 배열의 정렬 상태는 어떤 파티클이 활성상태가 바뀔때만 흐트러진다. 따라서 파티클의 활성 상태를 바꿀 때마다 비활성 파티클 중 맨 앞에 있는 것과 바꿔서 정렬한다.

void ParticleSystem::activateParticle(int idx)
{
	//이미 활성화된 경우
	if (idx >= numActive_) return;

	//비활성 파티클 중 맨 앞에있는것과 바꿔준다.
	//그 후 numActive를 1 늘려주면 활성 파티클이 된다.
	swap(particles_[numActive_], particles_[idx]);
	numActive_++;
}

void ParticleSystem::deactivateParticle(int idx)
{
	//이미 비활성임
	if (idx < numActive_) return;

	//비활성 파티클중 맨앞으로 오도록 한다.
	numActive_--;
	swap(particles_[numActive_], particles_[idx]);
}

 

그러나 이런 방식은 파티클 객체끼리 메모리 복사가 일어나기 때문에 포인터 교체에 비해 무겁다. 그러나 캐시를 활성화된 객체로 채워넣을 수 있다면 이 방법이 더 빠를 수 있다. 단, 꼭 프로파일링을 해보자.

 

API는 어떨까? ParticleSystem과 Particle이 강하게 결합되어있다. 그러나 파티클이라는 하나의 개념이 두 개의 클래스에 물리적으로 나뉘어 있다고 생각하면 괜찮아보인다. 즉 Particle은 ParticleSystem 안의 context에서만 의미가 있다.

 

 

 

---

 

자주 쓰이는 코드 분리

---

어떤 컴포넌트가 있다.

class SomeComponent
{
public:
	void update();

private:
	Transform transform_;
	DropInfo dropInfo_;
};

이 컴포넌트에는 객체의 (위치,각도,스케일)에 대한 정보 Transform과 객체가 사라질 때 떨어트리는 아이템의 정보인 DropInfo가 있다.

 

Transform은 매 프레임 사용되는 자주 쓰이는(Hot) 데이터이다. 반면 DropInfo는 객체가 사라질 때만 사용되는 자주 쓰이지 않는(Cold) 데이터이다. DropInfo와 같은 Cold 데이터가 캐시에 들어간다면 캐시의 효율이 떨어지게 된다. 따라서 이 둘을 분리하면(Hot/Cold Splitting) 좋다.

 

Hot데이터는 캐시에 모두 올려준다. 반면 Cold 데이터는 포인터를 이용해 저장한다. 캐시에는 포인터만 올라간다.

class SomeComponent
{
public:
	void update();

private:
	Transform transform_;
	DropInfo* dropInfo_; //Cold Data는 포인터로 참조
};

 

만약 Hot 데이터와 Cold 데이터를 두 개의 배열에 나란히 두면 포인터도 제거할 수 있다. (id로 참조)

 

 

 

---

 

디자인 결정

---

다형성은?

데이터 지역성을 위해 정렬된 단일 자료형 객체 배열을 사용했다. 그러나 이렇게 되면 배열에 들어 있는 객체 크기가 모두 같아야 하기에 상속을 사용하기 어려워진다. 그렇다면 다형성, 동적 디스패치는 어떻게 해야할까?

 

1. 안 써

가장 단순한 방법으로 그냥 상속을 사용하지 않는다. 이 방법은 안전하고, 쉽다. vtable에서 메서드를 찾아볼 필요도 없으므로 더 빠르다(탈가상화를 통해 정적 디스패치를 한다면 예외).  그러나 코드가 유연하지 않아진다.

 

2. 종류별로 다른 배열에

객체 종류별로 다른 배열에 나눠 담는다. 이렇게되면 정적 디스패치를 할 수 있다. 공용체를 쓸 필요도 없다. 그러나 여러 컬렉션을 관리해야 하고 전체 클래스 자료형과 커플링 된다.

 

 

 

게임 개체는 어케정의?

1. 게임 개체가 컴포넌트를 포인터로 참조

이렇게 되면 컴포넌트를 연속된 배열에 저장하고 순회 작업을 최적화할 수 있다. 또 컴포넌트를 쉽게 얻어올 수 있다. 그러나 컴포넌트 위치가 바뀔 때, 컴포넌트를 가리키는 포인터가 같이 바뀌도록 잘 신경써줘야 한다.

 

2. 컴포넌트 id를 들고있음

개체는 컴포넌트의 id만 가지고 있고 별도의 코드에서 id와 컴포넌트의 위치를 매핑해준다. 컴포넌트를 쉽게 찾을 수 있지만 복잡하고 느리며 별도의 컴포넌트 관리자코드를 만들어야 한다.

 

3. 게임 개체는 그냥 id

몇몇 게임에서 쓰는 최신 방식이다. 게임 개체의 동작과 상태를 모두 컴포넌트로 분리하고 나면 개체 클래스는 단순히 컴포넌트 집합일 뿐이다. 따라서 개체가 자기 컴포넌트를 아는게 아니라 컴포넌트가 자기 객체를 알게 만든다. AI컴포넌트가 자기 개체의 물리 컴포넌트에 접근하라면 같은 개체 id를 가진 물리 컴포넌트를 찾으면 된다.

 

이렇게 되면 개체가 단순해진다. 개체의 생명주기를 관리하지 않아도 된다. 

 

그러나 특정 개체의 컴포넌트를 찾는게 느릴 수 있다. 특정 개체의 컴포넌트를 얻기 위해 id로 찾는 과정을 겪어야 하는데 이 과정이 오래 걸릴 수 있다. 

 

이를 위한 해결 방법은 배열에서의 인덱스를 개체id로 삼는 것이다. 이렇게 되면 그냥 인덱스를 통해 다른 컴포넌트에 접근하면 되므로 굉장히 빠르다. 그러나 이렇게 되면 모든 컴포넌트 배열을 병렬오 유지해야 한다. 이 방법이 조금 까다로울 수 있다. 유니티에서 제공하는 ECS가 이 방식인듯.....?(아님 말고ㅎ)

 

---

참고 : 로버트 나이스트롬, 게임 프로그래밍 패턴, 한빛미디어, [321-344p]