게임을 위한 자료구조 - 빠른 순회, 빠른 삽입, 빠른 삭제, 빠른 탐색

GameObjectManager (가칭)

전체 순회, 삽입, 삭제, 탐색 속도가 매우 빠른 컨테이너입니다.
제목은 GameObjectManager 라고 지었는데, GameObject를 관리하기 위한 컨테이너 쯤으로 불러도 괜찮습니다.
이름에서 볼 수 있듯 게임 오브젝트를 관리하기 위해서 만든 특별한 자료구조입니다.

게임에서 가장 빈번히 일어나는 작업 중 하나는 컨터이너의 순회입니다. 보통 게임 오브젝트들은 매 틱마다 자신의 고유의 일을 수행하기 위해 Update 혹은 Tick 이라는 함수를 수행합니다. 그러기 위해서는 컨테이너에 수많은 오브젝트들을 저장하여 전체 순회를 통해서 상태를 갱신하는 설게를 사용할 수 있습니다. 그러므로 컨테이너의 순회는 1초에 최소 60번은 발생하며, 순회의 속도는 게임의 성능을 판가름하는 요소가 될 수 있습니다. 순회의 복잡도는 일관적으로 O(N)의 복잡도를 보인다만, Cache Hit를 고려하면 실제로 연속된 공간에 저장되어있는 배열 (혹은 std::vector, std::array 등)이 오브젝트를 저장하는데 가장 적합한 자료구조일 것입니다.

일반적으로 자료구조의 성능을 판단하는 기준은 삽입, 삭제, 탐색의 시간복잡도입니다.
저는 여기에 순회를 추가하여 자료구조의 성능을 평가하도록 하겠습니다.

C++ 환경에서 가장 빈번하게 사용되는 배열 컨테이너인 std::vector의 성능은 다음과 같습니다.

[std::vector]

순회: 일관적으로 O(N)
삽입: 배열의 맨 뒤에 추가할 경우 O(1)
삭제: 원하는 요소를 삭제하고 재배열시 O(N) + O(N) = O(N)
탐색: 원하는 요소를 찾을 경우 최악의 경우 O(N)

가장 기본 형태의 배열은 데이터가 연속된 공간에 저장되어 있기에 순회 속도가 매우 빠릅니다.
그러나, 삭제와 탐색에 있어서 아쉬운 성능을 보입니다.
게임에서는 삭제와 탐색 또한 빈번하게 발생할 수 있기 때문에 O(N)이라는 복잡도는 살짝 부담스러울 수 있습니다.

그러면 이진 탐색을 사용할 수 있는 정렬된 벡터를 사용하여 최적화를 도모할 수 있습니다.
참고로 정렬된 벡터를 유지하기 위해서는 '키'가 필요한데
일반적으로 사용할 수 있는 것은 '오브젝트 고유 문자열의 해시값' 혹은 '오브젝트의 정수형 ID' 가 있습니다.

두 방식에는 각각 장단점이 있는데, 저는 문자열의 해시값을 키로 사용할 경우 해싱 비용이 부담된다고 판단하여 오브젝트의 정수형 ID를 키로 사용하는 방식을 선택했습니다. 그러나 이 방식은 디버깅이 어려울 수 있어, 상황에 따라 선호에 맞춰 선택하는 것이 좋습니다.

[정렬된 상태를 유지하는 std::vector]

순회: 일관적으로 O(N)
삽입: 정렬 상태를 유지할 수 있는 위치를 탐색 후 삽입 최악의 경우 O(logN) + O(N) = O(N)
삭제: 원하는 요소를 삭제하고 재배열시 최악의 경우 O(logN) + O(N) = O(N)
탐색: 원하는 요소를 찾을 경우 최악의 경우 O(logN)

정렬된 배열을 사용하면 삭제의 성능은 약간 향상되고, 탐색의 경우 유의미하게 빨라집니다.
그러나 삽입의 성능은 매우 떨어집니다.
정렬된 배열과 함께 오브젝트를 관리하는 경우 오브젝트 풀링 기법을 사용하면 꽤나 괜찮은 성능 향상을 얻어낼 수 있습니다.
오브젝트 풀링이란 빈번하게 생성, 삭제되는 객체들을 미리 일정 크기만큼 생성하고 후에 한꺼번에 삭제하는 것을 의미합니다.
게임에서 빈번한게 생성, 삭제되는 투사체, 적, 아이템 등을 맵 입장시 미리 생성하고 맵을 퇴장할 때 한 번에 삭제하는 설계를 사용한다면, 삽입과 삭제에 대한 성능 저하는 큰 병목이 아니게 될 것입니다.
탐색의 경우 확연하게 빠르기 때문에 오브젝트 풀링 기법과 정렬된 배열로 오브젝트를 관리하는 기법은 꽤나 유효합니다.

앞서 살펴봤듯, 오브젝트 풀링 기법을 사용하면 생성과 삭제의 복잡도가 게임 성능에 치명적인 영향을 미치지 않음을 알 수 있습니다. 이것은 컨테이너의 성능이 탐색 속도에 달려있다는 것을 의미하기도 합니다. 그러면 탐색 속도를 더 높일 방법을 모색하도록 합니다.

일반적으로 탐색이 가장 빠른 컨테이너는 해쉬 테이블입니다. C++ 에서는 std::unordered_map 이라는 형태로 해쉬 테이블을 제공합니다. 해시맵(HashMap)은 키와 값을 쌍으로 저장하는 자료구조로, 내부적으로 매우 큰 배열을 유지하며, 키를 해시 함수를 통해 배열의 인덱스로 변환하여 빠르게 접근하는 구조입니다. 해쉬맵은 성능은 다음과 같습니다.

[std::unordered_map]

순회: 일관적으로 O(N) 그러나 캐쉬 미스가 빈번하여 배열에 비해 느림.
삽입: 일반적으로 O(1), 최악의 경우 O(N)
삭제: 일반적으로 O(1), 최악의 경우 O(N)
탐색: 일반적으로 O(1), 최악의 경우 O(N)

해쉬맵은 순회가 느린대신 삽입, 삭제, 탐색에 있어서 매우 우수한 성능을 보여줍니다. 그래서 굳이 순회가 필요하지않다면 해쉬맵은 일반적으로 좋은 선택이며, 가장 널리 사용되는 컨테이너입니다. 그러나 가장 중요한 토픽은 컨테이너의 순회이므로 해쉬맵을 오브젝트를 관리하는 컨테이너로는 사용하기는 어렵습니다. 대신 순회용으로는 백터, 탐색용으로는 해쉬맵, 삽입과 삭제의 오버헤드는 오브젝트 풀링으로 해결하는 형태를 갖춘다면 빠른 순회, O(1)의 탐색을 기대할 수 있습니다.

이 방식의 단점은 실시간 생성과 삭제의 성능이 좋지 않다는 것, 배열과 해쉬 맵을 동기화해줘야 한다는 것, 메모리 사용량이 많다는 것입니다.
배열과 해쉬 맵의 동기화는 객체 지향 설계로 내부 로직을 은닉해버리면 해결할 수 있습니다.
그리고 실시간 삭제를 최적화하는 기법도 존재합니다. 오브젝트를 삭제한 후 즉시 배열을 재정렬하는 대신, dirty bit를 설정하여 해당 인덱스를 표시하고, 이후 순회 시 continue로 해당 인덱스를 건너뛰는 방식입니다. 그런 다음, 나중에 dirty bit가 설정되지 않은 요소들만을 기준으로 배열을 재정렬하는 방식으로 성능을 최적화할 수 있습니다.

최종적으로 소개할 것은 빠른 순회, O(1)의 삽입, 삭제, 탐색을 지원하는 컨테이너입니다.
자료구조는 앞서 사용한 방식과 동일하게 배열과 해쉬맵을 동시에 사용하는 방식입니다.

해쉬맵의 키는 오브젝트의 ID, 값은 배열인덱스와 오브젝트객체로 설정합니다.
여기서 배열인덱스는 순회용 배열에 오브젝트객체가 저장된 위치를 의미합니다.

그러면 탐색, 삽입, 삭제, 탐색 전략에 대해서 설명하겠습니다.

1. 탐색

탐색은 해쉬맵을 이용해서 평균 O(1)의 속도로 수행합니다.

2. 삽입

삽입은 로직은 다음과 같습니다.

1) 배열의 끝에 오브젝트를 추가한다. 그리고 해당 인덱스를 IdxA 라고 한다.
2) 오브젝트ID를 키로하여 해쉬에 (IdxA, 오브젝트) 쌍을 추가한다.

3. 삭제

주요 논점은 삭제 로직입니다.

1) 삭제하고자 하는 오브젝트A_ID를 키로하여 해쉬에서 (IdxA, 오브젝트A) 쌍을 얻어낸다.
2) 배열의 맨 끝에 있는 오브젝트를 오브젝트B라고 할 때, 배열[IdxA] 에 오브젝트B를 대입하고, 기존 오브젝트B의 인덱스에는 dirty bit를 설정한다.
3) 오브젝트B_ID를 키로하여 해쉬에서 (IdxB, 오브젝트B) 쌍을 얻어낸다.
4) 해당 쌍에서 IdxB를 IdxA로 수정한다.

여기서 핵심은 배열의 앞부분에는 유의미한 객체가 쌓이고, 배열의 나머지부분에는 의미없는 dirty bit들이 쌓인다는 것입니다.

해당 컨테이너의 로직을 원활하게 진행하기 위해서는 배열속 유의미한 객체의 개수나 유의미한 마지막 객체의 인덱스 등을 따로 저장하고 있어야 한다는 것입니다.
dirty bit는 굳이 삭제하지 않고, 삽입시 dirty bit를 객체가 덮어씌우는 느낌으로 로직을 구성할 수 있고,
정책에 따라 드물에 O(N) 만큼 연산하여 dirty bit들을 모두 없앨 수 있습니다.

4. 순회

순회는 배열을 이용하여 빠르게 수행하며, dirty bit가 등장하기 전까지만 수행합니다.

5. 성능

순회: 일관적으로 O(N) 더하여 캐쉬 히트 높음
삽입: 일반적으로 O(1), 최악의 경우 O(N)
삭제: 일반적으로 O(1), 최악의 경우 O(N)
탐색: 일반적으로 O(1), 최악의 경우 O(N)

6. 단점

1) 메모리 사용량이 높다.
현대 컴퓨터 시스템에서 이정도 메모리 사용량은 전혀 문제가 되지 않으며
관리자 컨테이너는 프로그램 당 단 하나 존재하기 때문에 복사에 대한 염려가 없어 성능 저하는 신경쓰지 않다도 된다.
설령 복사를 해야하더라도 std::move 를 사용하면 최적화를 수행할 수 있다.

 

2) 오브젝트의 ID를 반드시 알아야 한다.
그러므로 삭제할 오브젝트 자체가 오브젝트 매니저에게 자신을 삭제해달라고 요청하는 방식으로 설계되어야 한다.
오브젝트의 ID를 모를 경우 여전히 탐색에 시간이 많이 걸린다.
그러나 이런 탐색은 매우 드물게 수행되기에 특수한 상황이 아닌 이상 문제가 되지 않는다.

7. 구현

https://github.com/powercrabman/GameObjectManager.git