Data Oriented Design (DOD)는 Object-Oriented Design(OOD)와 다른 편에 서 있는 Language Design 개념이다. 말그대로 객체 지향이 아닌, 데이터 지향적인 프로그래밍 설계 방법이다.

대게 OOD에서는 몬스터 클래스를 만들면 아래와 같이 설계한다.

그런데 DOD에서는 아래와 같이 한다.

즉, monster의 객체를 따로 정의하고 생성된 몬스터를 리스트에 집어 넣어서 객체별로 따로 움직임을 주는 것이 아닌, 몬스터의 객체를 없애고 각 Property 데이터들을 처리하는 일을 더 수월하게 구조를 잡는 형태이다. 이렇게 하는 여러가지 이유가 있으나, 특별히 게임 엔진이나 물리 엔진 등에서 Cache Miss를 줄여서 퍼포먼스를 올리기 위해 사용한다.

간단히 디바이스의 내부 구조를 쉽게 표현하면 이렇다. CPU의 옆동네에 메모리가 살고 있다. 그리고 CPU의 바로 옆집에 메모리의 사촌 동생인 Cache, 즉 캐시 메모리가 살고 있다. L1, L2, L3… 등으로 구분하긴하는데, L 다음에 숫자가 올라갈 수록 메인 메모리를 닮아간다. 즉 커지고, 느려지며 CPU랑 멀어진다. 여튼 그 종류들을 다 묶어 Cache라는 사촌 동생이 있다고 하자. CPU는 옆동네의 메모리에게 데이터 한개를 얻어와서 열심히 계산하는 일을 하고, 끝나면 다시 메모리가 사는 옆동네로 가서 데이터를 하나 받아와서 계산하고 하는 작업을 했다. 그런데, 너무 자주 옆동네를 들락날락하다 보니 일의 효율이 없었다. 그래서 고민 끝에 저장할 곳이 없는 자기 집 말고, 사촌 동생이자 바로 옆집에 살고 있는 Cache에게 메모리에서 가져온 데이터들을 저장해 뒀다가 캐시로 부터 데이터를 읽고 계산을 하니 옆동네 메모리에게 가서 데이터를 얻어오는 작업 빈도를 줄어들어 훨씬 빨리 일을 할 수 있게 되었다.

이 때, CPU가 캐시 메모리에 계산을 위한 유효한 데이터가 쌓여 있는지 체크를 하게 되는데 이 때 사용 가능한 유효한 데이터가 존재하지 않는 상태를 Cache Miss라고 한다. Cache Miss의 경우에 메인 메모리로부터 다시 캐시 메모리를 채우는 작업을 하게되는데, 이 때 시간이 소모되고 그 순간 CPU가 놀게(CPU Idle) 된다. 자연히 총 작업 시간이 늘어나게 된다.

Android developer blog에 올라와 있는 아래 예제를 보자.

1)

2)

1번과 2번은 동일하게 100만번 루틴을 돌면서 sum을 하고 있으므로 동일한 작업 시간이 나와야 한다. 그러나 아래 결과 그래프를 보면 알 수 있듯이 1번이 2번에 비해 다양한 디바이스에서 모두 테스트를 해봐도 평균 5배 가량 빠르다고 한다.

[Graph in logarithmic scale]

이유는 당연히 캐시 미스가 발생하기 때문인데, 디테일은 이렇다.

캐시 사이즈가 16byte이고 캐시 라인(캐시가 한번에 읽어오고 다루는 chunk byte size) 역시 16byte라고 가정하고, 16번 Loop을 돈다고 하자. 1번의 경우 2번의 캐시 미스가 발생하여 메모리로부터 두번 데이터를 읽어와서 채우게 된다. 반면에 2번의 경우 16byte씩 점프하기 때문에, 1회 계산당 캐시 미스가 매번 발생하게 된다. 그래서 총 16번 계산에 16번 캐시 미스가 발생하므로 자연히 2번이 느리게 된다. 이는 캐싱의 사이즈가 늘어나더라도, 메모리로부터 읽어오는 캐시 사이즈 자체의 Size 오버헤드로 인해서 역시 마찬가지 결과를 가져온다. 참고로, Nexus 5의 경우 L0 데이터 캐시가 4KB이고 64Byte의 캐시 라인을 가지고 있다.

그럼, 다시 처음에 제시한 몬스터 클래스를 살펴보자.

위의 데이터 구조는 Array of Structures, 즉 AOS 형태가 된다. 반면, 아래의 구조는 Structure of Arrays (SOA) 구조이다.

몬스터를 이동 시키는 Method를 만든다고 하면, AOS, SOA 구조 각각 아래와 같이 만들 수 있다.

첫번째 AOS의 구조에서는 Monster가 캐시에 올려져 있다할 지라도, 앞쪽 Vector3(float 3개 12 Byte)가 두개, 즉 24Byte만 연산에 쓰인다. 따라서 64byte의 캐시 라인을 가진 Nexus 5의 경우엔 매번 루프를 돌 때마다, 캐시 미스가 발생하여 새로운 Monster를 캐시에 올리는 동작을 반복하게 된다.

반면, 두번째 AOS의 구조에선 4Kbyte의 캐시 사이즈에 64Byte 캐시 라인을 가진 넥서스 5의 경우라면 일단 position과 velocity 두번의Cache Miss가 호출 즉시 발생하여 각각의 캐시 라인에 올려지게 되고, 그 이후엔 Loop 마다 각각 12byte씩 64byte 캐시 라인에 있는 데이터를 다 계산에 쓸때까지 즉, 약 5.334번을 캐시 미스 없이 추가 계산할 수 있다.

이런 Cache Miss는 C++에서 STL을 사용할 때도 유의해야 한다. 가령, 단순 Linear Search에서 Vector가 List보다 압도적으로 빠른 이유는 List가 메모리를 랜덤으로 엑세스하여 찾는데 반하여 Vector는 Chunk를 캐싱하여 찾기 때문에Cache Miss가 확연히 줄고 당연히 훨씬 빠를 수 밖에 없다. 관련하여 C++ 비야네 할아버지 강의 참고(Link)

현실적으로 100만번 반복되는 것에서 약간 차이나는 정도의 시간을 벌기 위해서 굳이 읽기 어려운 코드를 만드는 것도 Code Smell이다. 다만 티끌모아 태산이라고, 게임 같은 애플리케이션에서는 종종 퍼포먼스가 다른 모든 것들보다 더 중요한 부분일 때가 있다. 그러한 때에 좋은 개발자라면 구조 설계를 할 때 단순히 OOD 적인 접근만 하려는 것보다는 극한의 반복 코드들, 극도의 퍼포먼스가 요구되는 부분에 이런 DOD적인 설계를 얹을 수 있다는 점을 고려해야 한다.

References : 
http://android-developers.blogspot.se/2015/07/game-performance-data-oriented.html
https://www.youtube.com/watch?v=WDIkqP4JbkE
http://gamedevelopment.tutsplus.com/articles/what-is-data-oriented-game-engine-design–cms-21052
http://gamedev.stackexchange.com/questions/8024/how-to-apply-data-oriented-design-with-object-oriented-programming
http://www.randygaul.net/2014/06/25/cache-aware-components/
https://www.youtube.com/watch?v=YQs6IC-vgmo

출처 : http://rapapa.net/?p=2792