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

CppCon 2014 - Mike Acton의 "Data-Oriented Design and C++"을 주로 참고해서 씀.

https://www.youtube.com/watch?v=rX0ItVEVjHc

 

인트로

1. 소프트웨어는 플랫폼이다.

2. 코드는 실제 세계의 모델을 중심으로 설계되어야 한다.

3. 코드는 데이터보다 중요하다.

 

저 위의 3가지 명제를 보면 그럴 듯 하다. 특히 2번의 경우에는, 게임 클라 개발자로써 많이 의식하는 명제인 것 같다. 누가 저렇게 하라고 시키지는 않았지만 많은 예제코드에서 저런 식으로 코드를 짜니까. (ex. 몬스터 클래스가 있고 그 안에 transform, status, animation... 등을 포함)

 

강연자인 Mike Acton은 저 위의 3가지 명제를 거짓말이라고 한다. 

 

1번의 경우, 진정한 플랫폼은 하드웨어이다. 우리는 하드웨어에 가장 많은 제약을 받으며 하드웨어가 다르면 솔루션도 달라진다. (모바일 디바이스, pc, 서버)

 

2번의 경우, '진짜 문제'가 무엇인지 생각해봐야 한다. 실제 세계의 모델을 참고하는 것은 문제를 이상적으로 바꾸려는 시도인데, 이게 '진짜 문제'일까? '진짜 문제'는 실제 세계의 모델을 참고해서 문제를 푸는 것이 아니라 내가 개발하는 '하드웨어'를 포함한다. 실제 세계의 모델을 참고하는 것은 그냥 프로그래머의 심리적인 요인 때문이다.

 

3번의 경우, 모든 코드의 목적은 데이터를 가공하기 위함이다. (ex. 인풋을 화면에 뿌려지는 렌더링 데이터로 전환)

 

 

메모리 캐싱과 명령어의 Latency

https://www.agner.org/optimize/instruction_tables.pdf 

위 링크에서 AMD instruction의 latency를 확인해볼 수 있다. 여기서 제곱근을 구하는 명령어 (SQRT)의 latency는 약 15(cycle)이다. 꽤 무거운 명령어인 삼각함수의 경우에는 100~300(cycle)정도를 왔다갔다 한다.

 

그렇다면 메모리에 접근하는 속도는 몇일까? 물론 하드웨어마다 다르겠지만 보통 L1 캐시는 3 cycle, L2~3 캐시는 10~30 cycle, 메모리는 200cycle(s) 이 필요하다고 가정하자.

 

출처 : https://www.gameenginebook.com/resources/SINFO.pdf

 

class GameObject
{
	float m_Pos[2];
	float m_Velocity[2];
	char m_name[32];
	Model * m_Model;
	//... 다른 멤버들 ...
	float m_Foo;

	void UpdateFoo(float deltaTime)
	{
		float mag = sqrtf(
			m_Velocity[0] * m_Velocity[0] +
			m_Velocity[1] * m_Velocity[1]);

		m_Foo += mag * deltaTime;
	}
};

 

위와 같은 코드가 있다. GameObject의 UpdateFoo(float) 메서드를 봤을 때, 우리는 제곱근을 구하는 sqrtf가 성능에 가장 중요한 부분이겠구나~ 라고 착각할 수 있다. 근데 정말 그럴까?

 

UpdateFoo에서 sqrtf 와 곱셈 덧셈 연산을 다 합쳐도 40cycle 정도의 latency가 발생할 것이다. 반면에 m_Velocity라는 멤버에 접근하는 속도는 어떨까? 메모리에서 m_Velocity를 로드하는 속도는 200cycle이다. 더 나쁜건 m_Foo를 읽어와서 값을 쓰는데도 200cycle의 지연이 발생할 것이라는 점이다. 

 

그러니까 수학 연산하는데는 40cycle 정도밖에 안 드는데, 메모리에서 값을 읽어오는데만 400cycle이나 써버렸다. 즉, 수학 연산하는데 드는 시간은 전체 계산시간의 10%밖에 안 된다.

 

그렇다고 메모리에서 값을 안 읽을수도 없는데 어떻게 해야 할까?

 

m_Velocity와 m_Foo를 읽는 과정을 생각해보자. 일반적으로 메모리와 L1,L2캐쉬에서 값을 불러오는 단위인 캐쉬 라인은 64바이트인데 m_Velocity와 m_Foo는 각각 8바이트, 4바이트밖에 안 된다. 그러니까 각각 56, 60바이트를 낭비하는 셈이다. 그렇다면 이걸 꽉꽉 채워서 사용하면 효율적이지 않을까?

 

struct FooUpdateIn
{
	float m_Velocity[2];
	float m_Foo;
};

struct FooUpdateOut
{
	float m_Foo;
};

void UpdateFoos(const FooUpdateIn * in, size_t count, FooUpdateOut * out, float deltaTime)
{
	for(size_t i=0; i<count; ++i)
	{
		float mag = sqrtf(
			in[i].m_Velocity[0] * in[i].m_Velocity[0] +
			in[i].m_Velocity[1] * in[i].m_Velocity[1]);
		out[i].m_Foo = in[i].m_Foo + mag * deltaTime;
	}
}

그렇다면 위 코드처럼 여러개의 GameObject를 같이 업데이트 해주면 어떨까? 

 

예를 들어, 32개의 게임오브젝트가 있고 m_Velocity를 이용해 m_Foo를 업데이트한다. 기존 방법의 경우에는 32개의 게임오브젝트가 각각 2번씩 캐시라인을 사용한다. 다 합치면 64개의 캐시라인이 사용되는 셈이다.

 

그렇다면 새로운 방법은? 32개의 m_Velocity는 256바이트니까 4개의 캐쉬라인을, m_Foo는 128바이트니까 2개의 캐쉬라인을 사용한다. 다 합치면 6개밖에 안 쓴다. 

 

속도는 엄청 차이날 수 밖에 없다. 기존 방법이 32개의 게임오브젝트를 업데이트 하는데에 32번의 수학 연산 1280cycle(32*40) + 64번의 캐시미스 12800cycle = 14080 cylce이 걸렸다면, 나중의 방법은 1280cycle + 1200cycle (200*6) = 2280cylce 밖에 안 걸린다. 무려 7배 가까이 차이가 난다. 그리고 Cache Prefetch 덕분에 사실 실제적인 속도는 더 빠를 것이다.

 

 

정리

전자의 방법이 실제 모델을 기반으로 짠 코드라면, 후자는 데이터 지향적으로 설계한 방법이다. 이런데도 실제 모델을 기반으로 코드를 설계해야한다는 환상을 가질 필요가 있을까? 강연자는 그렇게 생각한다면 그건 똥고집(dogma)라고 한다.

 

사실 후자와 같은 코드를 작성하는것은 더 어렵다. 데이터를 올바르게 나누기도 어렵고 수정도 어쩌면 더 힘들지 모른다. 그러나 데이터 지향적으로 설계한 방법은 테스트 용이성이 높다는 장점이 있다. 기존 실제 모델 기반의 방법은 여러 개의 GameObject 클래스를 적절히 초기화해주고 상태를 mocking 해줘야 한다. 반면에 데이터 지향 설계의 방법은 깔끔하게 input, output만 들어오고 나간다.

 

이부분은 또 다른 강연인 CppCon 2018: Stoyan Nikolov “OOP Is Dead, Long Live Data-oriented Design” (https://youtu.be/yy8jQgmhbAU) 참고

 

 

 

Bools in Struct

프로그래밍 하다보면 다양한 이유로 bool을 클래스나 구조체에 넣는다. 사실 bool은 그 자체로 1비트의 정보만 가지고 있지만 1바이트(8비트)나 사용한다. bool을 사용하는것 자체가 메모리 낭비일 수 있다. 그렇다고 쓰지 말라는건 아니고... bool때문에 1개의 캐시라인이 사용될 수 있는데 이런 경우 엄청난 낭비가 아닐 수 없다. 그래서 모아서 처리할 수 있으면 가능한 모아주는게 좋다. 결정을 내리는 경우라면 여러개의 결정을 내려버리든지 혹은 결정을 계속 미루다가 한 번에 처리하든지 하는 식으로.