Unreal Engine에서 C++ STL 컨테이너가 쓰이지 않는 이유

 

https://forums.unrealengine.com/t/why-doesnt-ue-utilize-stl-containers/34551/4

Why doesn't UE utilize STL containers?

 

언리얼 포럼을 찾아보다 팀 스위니가 직접 답변을 단걸 처음봤다.

언리얼 개발을 해봤다면 언리얼에서 STL을 사용하지 않는 것을 누구나 알지만 그 이유는 성능상의 문제겠거니 하고 정확히 모르는 경우가 많다.

 

팀 스위니 말에 따르면

언리얼 엔진을 도입하던 시기에 C++ STL은 메모리 연속성의 보장, 플랫폼간 일관성이 보장되지 않음, 성능 문제 등의 이유로 형편 없었기 때문에 도입하지 않았지만 현재의 표준 컨테이너는 안정적이라 호환 가능하도록 발전시키는 것이 그렇게 어렵지 않을 것이라 답변단지가 2015년인데 아직도 안해준걸 보면 그냥 안하려는거같다.

 

내가 알고있는 문제점은

1. 플랫폼별 가상 메모리 시스템이 다르다. 따라서 메모리 단편화 이슈에서 자유롭지 못했다. 현재는 XBOX, PS같은 콘솔도 가상 메모리를 제대로 지원하기 시작했지만 모바일에서는 메모리가 여전히 제한적이다.

2. 게임에서 사용하기 느리다. 이러한 문제 때문에 EA에서는 STL 규격을 지키면서 자체 STL을 만들었다.

 

사실 언리얼에서 주로 사용하는 자료구조라 해봐야 Array, Map, Set 이정도밖에 없다. 따라서 우리는 이 자료구조에 대해서 정확히 알고 사용하면 된다.

 

 

Container	Time complexity
	Indexing	Search	Insertion	Deletion
TArray	O(1)	O(n)	O(n)	O(n)
TSet	O(1)	O(1)	O(1)	O(1)
TMap	O(1)	O(1)	O(1)	O(1)

TArray

장점

1. 가변 배열의 자료 구조로 STL std::vector와 유사하게 작동한다. 
2. 데이터가 순차적으로 모여있으므로 Cache hit rate 높다.
3. 임의 데이터 접근이 빠르고 고속으로 순회할 수 있다.

단점

1. vector와 마찬가지로 중간에 요소를 추가하거나 삭제하는 비용은 여전히 크다.
2. 데이터가 많아질 수록 검색, 삭제, 수정 작업이 느려진다.

특징

1. TArray는 value 유형이므로 new/delete 연산으로 생성/소멸 시키지 말 것.
2. 주의사항으로 Emtpy()는 비어있는지 체크하는게 아니라 실제 배열을 비우는 함수로 std::vector처럼 막 사용하다 뒤통수를 맞을 수 있음.
3. Add()는 추가할 데이터를 밖에서 생성한 뒤 복사하고 TArray에 집어넣는다. 이것이 싫다면 Emplace()를 사용할 것.
4. Append()는 다수의 엘리먼트를 한번에 추가할 때 주로 사용할 것. 두 Array를 연결할 때에는 operator +=를 사용 가능하다. Arr1 += Arr2;
5. AddUnique()를 자주 써야한다면 해당 데이터를 TSet으로 바꿀 수 있는지 생각해볼 것.

 

Slack

TArray는 가변 배열이므로 요청한 메모리에 더해 Slack이라고 불리는 넉넉한 메모리만큼을 추가로 제공하여 메모리 재할당이 자주 일어나는 것을 방지한다. GetSlack()을 통해 슬랙 크기를 알 수 있고 Shrink()을 통해 슬랙을 제거할 수 있음. 재할당 이후 슬랙의 양은 얼로케이터에 의해 결정되므로 남아있는 슬랙의 양이 일정하다는 보장이 없다.

TArray Sort

1. Sort: C++과 마찬가지로 Quick Sort, Heap Sort, Insertion Sort를 섞은 Introsort를 사용한다. Unstable Sort 방식이다.
2. HeapSort: TArray를 힙으로 만들 수 있으므로 힙 정렬도 지원하는데 마찬가지로 같은 요소의 순서를 보장하지 않는 Unstable Sort이다
3. StableSort: 같은 키 값을 가지는 중복된 요소들의 순서를 보장한다.

TArray Heap

TArray에서는 힙 데이터 구조체를 지원하는 함수가 있다. Arr.Heapify()를 사용하면 기존 배열을 힙으로 변환 시킬 수 있다. 

HeapPush() 함수로 힙에 새로운 엘리먼트를 추가할 수 있음. 가능하다는 것을 알아두고 필요하면 세세한 함수들은 공식 문서를 참고할 것

 

 

TSet

순서가 중요하지 않은 상황에서 고유 엘리먼트를 저장하는데 사용된다. 내부 데이터 구조로 희소 배열(Sparse Array)를 사용하므로 빈 공간이 발생할 수 있다. 중간 중간 데이터가 끊겨 있을 수 있는 동적 배열이라고 생각하면 좋다.

 

TMap, TMultiMap과 비슷하지만 TSet은 독립된 키로 데이터 값을 연결하기 보다 데이터 값 자체를 키로 사용한다는 차이점이 있다. 

Set은 STL Set과 차이점이 있으므로 차이점을 먼저 알고 사용하는 것이 좋다.

C++ STL Set	Unreal TSet
Binary Tree	동적 배열과 Hash Table 형태의 키 구성
요소가 삭제될 때 트리 재구축이 일어날 수 있음	요소가 삭제되면 빈 공간을 Invalid로 처리하는 희소 배열을 사용
데이터 삭제시 트리 균형을 위해 데이터가 재구축 될 수 있음	데이터가 삭제되도 데이터를 재구축 하지 않음
데이터 순회에 적합하지 않음	데이터 순회에 적합함

TSet의 특징

1. 해시 테이블 구조이므로 상수 시간에 특정 키 값을 탐색할 수 있음
2. 데이터 삭제/삽입 시 기존에 삭제로 발생한 Invalid 공간이 있다면 우선적으로 재사용된다. 이때 마지막 Invalid 공간부터 사용한다.
3. Compact를 사용하여 Invalid를 없앨 수 있음
4. TArray와 마찬가지로 Add 대신 Emplace를 사용하면 삽입시 임시 생성을 막을 수 있음
5. TArray와 마찬가지로 Set은 Value 타입. Set의 복사는 깊은 복사로 이루어 짐
6. 정렬 가능함
7. RemoveAll 함수가 없음

TSet은 operator==로 요소를 직접 비교하고 GetTypeHash로 해싱한다. 새로운 형태의 구조체를 사용하여 TSet을 만들고자 한다면 GetTypeHash함수를 직접 구현해야한다.

 

검색

Set에 키 값이 있는지 확실하지 않은 경우 Contains나 operator[]을 사용하여 검사할 수 있으나 같은 키에 두번 조회하게 되므로 Find() 함수로 검색하는 것이 바람직하다.

 

제거

Remove 함수에 인덱스를 붙여 제거할 수 있지만 반복자 처리 도중에만 사용하길 권장하고 있음.

 

Slack

TArray와 마찬가지로 요소 제거시 메모리를 해제하는 것이 아니라 Invalid 처리를 해주는 것이므로 슬랙을 제거하려면 Shrink() 함수를 사용해야한다. TArray와 다르게 현재 슬랙이 얼마인지 확인할 수 없고 Shrink()는 컨테이너 끝부분부터 

모든 슬랙을 제거하지만 중간이나 시작 부분의 빈 요소가 있다면 제거하지 않는다.

 

TMap

Key-Value Pair가 필요한 자료구조에 광범위하게 사용 가능하다.

 

Binary Tree를 사용하는 std::map과 다르게 Hash Table을 사용하는 std::unordered_map과 유사한 구조를 가지지만 주요한 차이점은 Key가 해시되지 않고 Key-Value가 pair로 해시된다는 것이다.

 

TSet과 차이점은 TPair<Key, Value> 데이터로 구성되어있다는 점이고 나머진 동일하다. 

TSet은 값 자체가 키로 동작하는 반면 TMap은 키와 값이 쌍으로 존재한다는 차이점만 존재한다.

TMap은 키를 통해 값을 빠르게 찾는데 목적을 두는 반면 TSet은 값의 존재 여부를 확인하는데 중점을 둔다고 볼 수 있다.

TMap, TMultiMap 두가지 존재한다. TMultiMap은 다수의 동일한 Key 저장을 지원한다.