2015-4-21

TArray 퍼포먼스 최적화

By * Zak Middleton

언리얼 엔진에서 TArray 엘리먼트 유형별 크기가 동적으로 변하는 배열입니다. TArray 는 프로그래머에게 매우 편리하며, 코드베이스에 *많이* 사용됩니다. 하지만 미묘한 퍼포먼스 문제가 생길 수 있는데, 최적의 퍼포먼스를 위해서는 내부적으로 돌아가는 부분을 확실히 이해할 필요가 있습니다.

현명한 선택 내리기: TArray 가 적당한가?

퍼포먼스에 대해 이야기할 때는 늘상 그렇듯이, 코드를 프로파일링해서 문제를 제대로 파악하고 있는지 확인해야 합니다. 문제가 생길 수 있는 부분을 피하기 위해서는 처음부터 현명한 방법을 선택하는 것도 좋습니다.

컨테이너 유형의 경우 (TArray, TSet, TMap 등), 핵심 경로의 코드 연산에서 올바른 컨테이너를 사용중인지 고려해 보는 것이 가장 중요합니다. 예를 들어 고유한 요소 목록을 유지하고서 그에 대해 추가(add), 제거(remove), 검색 작업을 자주 하는 경우, TArray 를 쓸 수도 있지만 TSet 를 쓰는 것이 아마 더 나을 것입니다.

압축된 메모리 공간에서 엄청 빠른 엘리먼트 반복처리를 원하는 경우, TArray 가 좋은 선택입니다. 하지만 코드를 작성하면서 추가, 제거 등의 작업에 대한 영향을 주의할 필요가 있습니다. 여기서는 간단한 방법으로 TArray 사용이 현명한 것인지, 게임 발매 시점이 되어서야 귀중한 최적화 시간을 차지하지는 않을지 알아보도록 하겠습니다!

1. 기본적으로 TArray 는 할당 정책에 의거, 항목의 추가에 따라 메모리가 늘어나면서 재할당됩니다.

TArray 에 엘리먼트를 쉽게 추가할 수 있다는 것이, TArray 가 편리한 이유중 하나입니다. 내부적으로 추가되는 항목이 많아질 수록 할당되는 메모리도 주기적으로 늘어나며, 그럴 때마다 엘리먼트 사본을 새로운 공간으로 복사한 다음 예전 메모리를 해제시켜야 합니다. 이 작업의 비용은 비쌀 수 있으므로, 가급적 피하고자 합니다. 퍼포먼스 악영향을 피하기 위해 할 수 있는 작업이 몇 가지 있습니다:

1.1: 추가할 항목 수나 대충의 상한선을 이미 알고있는 경우 미리 공간을 확보해 둡니다.

예를 들어 "Reserve" 호출 코드 한 줄 추가해 두면 이 함수 내 최대 하나의 할당이 보장됩니다:

// 배열 끝에 캐릭터의 사본을 N 개 추가합니다.
void AppendCharacterCopies(char CharToCopy, int32 N, TArray<char>& Result)
{
	if (N > 0)
	{
		Result.Reserve(Result.Num() + N);
		for (int32 Index=0; Index < N; Index++)
		{
			Result.Add(CharToCopy);
		}
	}
}

보통 엘리먼트를 하나씩 추가하는 것을 N 번 하면 배열이 주기적으로 확장되어 재할당이 일어나 복사가 일어날 수 있는데, 여기서는 엘리먼트 추가 시작 전 현재 엘리먼트 갯수를 받아서 Result 가 최소 N 개의 엘리먼트를 추가로 저장할 수 있도록 하여 할당이 최대 한 번만 일어나도록 하고 있습니다. 이미 공간이 충분하다면, 할당이 전혀 일어나지 않습니다!

1.2: 함수 파라미터로 사용될 때는 TArray 를 레퍼런스로 받습니다.

예제 1.1 에서 TArray 레퍼런스를 받도록 함수를 선언한 방식을 주목하세요. 다음과 같은 선언도 고려해 봅시다:

// 배열을 값으로 받습니다!
void AppendCharacterCopies(char Original, int32 N, TArray<char> Result)

값으로 전달하면, 함수 호출자는 배열을 AppendCharacterCopies() 에 전달하기 전 먼저 사본을 만듭니다. 이 작업은 메모리를 할당하고 모든 엘리먼트를 새로운 TArray 에 복사하므로 비쌉니다. 함수의 의도가 깨지는 것은 말할 것도 없이, 호출자의 배열 사본에 영향을 끼칩니다!

기본적인 것 같아 보이지만, "&" 하나 빼먹었다고 심각한 비용이 발생할 수 있습니다.

2. 기본적으로 TArray 는 아이템이 제거되면 축소(shrink)되어 메모리 재할당이 일어나는데, 마찬가지로 할당 정책에 따른 것입니다.

TArray 는 엘리먼트를 압축된 선형 배열에 저장합니다. 목록의 끝이 아닌 곳에서 엘리먼트를 제거하면 그 위치 이후의 모든 엘리먼트 자리를 옮겨(shift) 빈 자리를 메우게 됩니다. 추가적으로 TArray 는 엘리먼트를 제거하면 메모리를 돌려받고자 한다 가정하므로, 가끔씩 엘리먼트를 제거할 때 메모리 재할당이 일어나 메모리 사용량이 줄어듭니다. 여기에는 엘리먼트를 새로운 메모리로 복사하고 예전 공간을 해제시키는 작업이 필요합니다.

다행히도 이러한 작업을 경감시키기 위한 옵션이 몇 가지 있습니다:

2.1: 엘리먼트 제거시 사본을 축소시킵니다.

한 가지 접근법은:

// 초기 배열:
// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

// 인덱스 3 위치의 엘리먼트 제거
Array.RemoveAt(3);

// 엘리먼트 제거중인 임시 상태
// 0, 1, 2, _, 4, 5, 6, 7, 8, 9
// 엘리먼트 4,5,6,7,8,9 전부 왼쪽 이동
// 0, 1, 2, 4, 5, 6, 7, 8, 9

엘리먼트 제거시 빈 곳을 메우기 위해 모든 엘리먼트를 옮기느라 발생하는 퍼포먼스 악영향을 피할 수 있는 방법이 있는데, 바로 RemoveAtSwap() 입니다. 요청된 인덱스의 엘리먼트를 제거한 뒤, 모든 엘리먼트를 하나씩 이동시키기 보다는 가능하면 배열의 마지막 엘리먼트로 대체시키는 것입니다.

더 빠른 접근법:

// 초기 배열:
// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

// (인덱스 3 위치의 엘리먼트를 제거하고, 마지막 엘리먼트와 맞바꿀 수 있도록 합니다)
Array.RemoveAtSwap(3);

// 엘리먼트 제거중인 임시 상태
// 0, 1, 2, _, 4, 5, 6, 7, 8, 9
// 엘리먼트 9 와 기존 3 이 있던 자리를 맞바꿉니다.
// 0, 1, 2, 9, 4, 5, 6, 7, 8

한 가지 간단히 바꾼 것으로 또다시 퍼포먼스를 향상시켰습니다. 참고로 이 방법은 배열 내 엘리먼트를 제거한 이후 순서는 상관이 없을 경우 통하는 방법입니다.

2.2: 메모리 청소 제어.

TArray 엘리먼트 제거는 "bAllowShrinking" 파라미터를 받습니다. 기본적으로 TArray 에서 엘리먼트 제거시 공간을 해제시킬 것인가를 제어하는 옵션입니다. 가끔은 오래 남아있는 배열에 메모리가 낭비되지 않도록 할 수 있는 좋은 생각이지만, 단명하는 배열의 경우 이로 인해 소중한 시간을 잡아먹고 캐시가 오염됩니다.

TArray::RemoveAtSwap 을 살펴봅시다:

void RemoveAtSwap(int32 Index, int32 Count = 1, bool bAllowShrinking = true)

이 예제에서는 (값이 홀수인) 특정 조건의 엘리먼트를 전부 제거하고, 항목 제거시 메모리 할당 크기를 변경하지 않도록 합니다.

void RemoveEvenValues(TArray<int32>& Numbers)
{
	for (int32 Index = 0; Index < Numbers.Num(); Index++)
	{
		if (Numbers[Index] % 2 == 0)
		{
			Numbers.RemoveAtSwap(Index, 1, false);
			Index--;   // since we need to process this index again!
		}
	}
	
	// 옵션: 값 제거 후 빈 공간을 되찾습니다.
	Numbers.Shrink();
}

TArray 에는 이미 비슷한 작업을 하는 RemoveAll, RemoveAllSwap, RemoveSingle, RemoveSingleSwap, 등의 내장 함수를 통해 배열에서 특정 엘리먼트를 제거할 수 있고, 이미 구현도 효율적으로 되어 있습니다.

3. TArray 의 기본 할당기는 동적인 (힙) 메모리 할당기입니다.

가끔은 (특히나 배열 크기가 꽤나 커질 수 있을 경우) 괜찮으면서 바람직하기도 하고, TArray 가 편리한 이유 중 하나이기도 합니다. 하지만 힙 할당에도 비용은 드는데, 고정(lock)이나, 빈 블록을 찾는 비용이나, 접근하는 주소 공간이 많아져 캐시가 지저분해 지는 것도 그렇습니다.

하지만 약간의 노력으로 퍼포먼스를 향상시킬 수 있는 경우가 있는데요. 그 중 한가지는 기본과는 다른 할당기를 사용하는 것입니다. 보통은 위협적으로 들립니다만, UE4 에서는 꽤나 쉽게 가능합니다.

지금 말씀드리려는 유용한 할당기 하나는 TInlineAllocator 입니다. (TArray 처럼) 템플릿 파라미터를 둘 받는 컨테이너를 위해 특별히 디자인된 할당기입니다:

- 인라인 엘리먼트의 수 와,

- 2차 할당기 (기본값은 힙 할당기) 입니다.

첫째 인수(인라인 엘리먼트 수)는 가장 관심이 있는 것으로, 이 할당기는 할당기가 인스턴싱된 곳에 즉시 메모리 공간을 예약합니다. 그 공간이 소진되면, 할당기는 엘리먼트를 2차 할당기에 생성된 오버플로우 공간으로 이동시킵니다. TArray 의 경우, 스택에 선언된 배열은 그만큼의 엘리먼트 스택에 직접 공간을 예약한다는 뜻입니다. 클래스나 구조체의 일부로 선언된 TArray 는 해당 클래스나 구조체의 일부로 인라인 할당을 저장하여, 그 배열의 일부로 추가된 처음 N 개의 엘리먼트에 대해서는 동적인 할당이 일어나지 않습니다.

여기에는 여러가지 장점이 있습니다. 흔한 경우 배열에 예상되는 최대 엘리먼트 갯수를 잘 알고 있는 경우, 힙 할당을 완벽히 피할수 있는데, TArray 의 일부로 생성된 공간에 모두 들어가기 때문입니다. 추가적으로 엘리먼트가 추가됨에 따라, 주기적으로 배열을 키우고 엘리먼트를 새로 할당된 공간에 복사할 필요가 없습니다.

이와 같이 보통의 TArray 를 받아서:

TArray<Shape*> MyShapeArray;

다음과 같이 쉽게 바꿀 수 있다는 뜻입니다:

TArray<Shape*, TInlineAllocator<16>> MyShapeArray;

이 예제에서는 배열에 처음 추가되는 16 개의 엘리먼트에 대해 동적인 할당이 되지 않는데, TInlineAllocator 의 일부인 스택상의 영역에 들어맞기 때문입니다. 엘리먼트가 17 개 되는 시점에서 모든 엘리먼트가 스토리지의 2차 할당기 (즉 힙 할당기)로 이동됩니다.

TInlineAllocator 의 크기는 컴파일 시간에 결정해야 합니다. 배열의 *모든* 인스턴스에 대해 공간을 미리 예약할 것이냐 잠재적인 속도 향상을 기대할 것이냐 사이의 선택은 여러분에게 달린 것입니다. TFixedAllocator 역시 언급할 가치가 있는데, 2차 백업 할당기가 없다는 점만 제외하면 TInlineAllocator 와 비슷합니다. 즉 고정된 메모리 부분의 공간이 다 되면, 코드에 오류가 나는 것입니다.

4. 유형을 사용하기 쉽게 만듭니다.

일반적으로 배열 유형 선언을 더욱 편하게 해주는 (그래서 타이핑 시간도 줄여주는!) 방법은 typedef 를 사용하는 것입니다. 인라인 엘리먼트의 하드코딩된 수를 한 곳에서 업데이트하여 모든 인스턴스에 쉽게 전파시킬 수 있다는 장점도 있습니다. 예:

// 유형 선언
typedef TArray<Shape*, TInlineAllocator<16>> ShapeArrayType;

// 인스턴스 생성
ShapeArrayType MyShapeArray;

어떤 유형의 TArray 반복처리 작업을 할 때, typedef 를 사용하면 TArray 유형 선언을 매번 입력하지 않아도 되어 편리할 뿐만 아니라, 나중에 변경을 할 때도 훨씬 쉬워집니다:

for (ShapeArrayType::TIterator Iter(MyShapeArray); Iter; ++Iter)
{
	Shape* MyShape = *Iter;
	MyShape->Draw();
}

다른 방법으로 C++11 "auto" 키워드를 사용하여 첫 줄을 다음과 같이 대체하면 됩니다:

for (auto Iter = MyShapeArray.CreateIterator(); Iter; ++Iter)

한 가지 깔끔한 방법은 범위기반 for 루프를 사용하는 것입니다 (자세한 정보는 이 블로그 게시물을 참고하세요). "auto" 키워드 사용시 한 가지 기억할 점은, 엘리먼트 유형을 캡처하고자 할 때 포인터나 레퍼런스로 해야 불필요한 사본 생성을 피할 수 있다는 점입니다:

for (auto* MyShape : MyShapeArray)
{
	MyShape->Draw();
}

5. TArray 유형 변환

할당기가 다른 TArray (또는 다른 컨테이너)는 사실상 다른 유형이라, 다른 TArray 유형으로 자동 변환되지 않는다는 점에 유의하세요. 예를 들어 위에서 MyShapeArray 를 일반 TArray<Shape*> 을 받는 함수에 전달할 수 없습니다.

int32 GetNumShapes(TArray<Shape*>& ShapeArray)
{
	return ShapeArray.Num();
}

void TestCompile()
{
	TArray<Shape*> HeapShapeArray;
	TArray<Shape*, TInlineAllocator<16>> InlineShapeArray;
	
	FillShapeArray(HeapShapeArray);
	FillShapeArray(InlineShapeArray);
	
	// 자, 유형은 TArray<Shape*, FDefaultAllocator>&
	const int32 A = GetNumShapes(HeapShapeArray);
	
	// *오류*: TArray<Shape*, TInlineAllocator<16>>& 에서
	// TArray<Shape*, FDefaultAllocator>& 으로 변환 불가
	const int32 B = GetNumShapes(InlineShapeArray);
}

하지만 간단한 템플릿 코드를 추가해 주면 정상 작동하도록 만들 수 있습니다:

template<typename AllocatorType>
int32 GetNumShapes(TArray<Shape*, AllocatorType>& ShapeArray)
{
	return ShapeArray.Num();
}

void TestCompile()
{
	TArray<Shape*> HeapShapeArray;
	TArray<Shape*, TInlineAllocator<16>> InlineShapeArray;
	
	FillShapeArray(HeapShapeArray);
	FillShapeArray(InlineShapeArray);
	
	// 네, 컴파일러가 할당기의 템플릿 유형을 FDefaultAllocator 로 추론합니다
	const int32 A = GetNumShapes(HeapShapeArray);
	
	// 네, 컴파일러가 할당기의 템플릿 유형을 TInlineAllocator<16> 으로 추론합니다
	const int32 B = GetNumShapes(InlineShapeArray);
	
	// 네, 템플릿 유형으로 명시되었는데, 꼭 필수는 아니며,
	// 하드 코딩된 "16" 으로 재사용성이 매우 높습니다
	const int32 C = GetNumShapes<TInlineAllocator<16>>(InlineShapeArray);     
}

이상입니다! 간단히 추가해 준 것으로 어떠한 할당기 유형의 TArray 에도 통하도록 유연성이 높아졌습니다.

마지막으로 한 가지 주의 말씀: 큰 함수에 템플릿 인수를 추가할 때는 코드가 불어날 수 있으니 주의하세요. 컴파일러가 사용되는 각 템플릿 유형에 대한 코드마다 버전을 따로 생성하기 때문입니다. 다른 옵션은 코드 내 일관된 typedef 를 사용해서, 하나의 유형만 사용하도록 하되 쉽게 변경할 수 있도록 하는 것입니다.

Recent Posts

리얼타임 기술의 잠재력을 선보인 Theia Interactive의 Harley Davidson AR

증강 현실은 리얼타임 프로젝트 샘플을 통해 비즈니스 고객들을 설득하는 중요한 도구로 자리잡았습니다. Theia Interactive가 ...

2018년 4월 NVIDIA Edge 프로그램 수상자

4월에도 NVIDIA Edge 프로그램에 멋진 작품들이 많이 제출되었으며, 그 중에서 세 개의 작품을 뽑아 수상작으로 선정하였습니다. ...

언리얼 엔진으로 BMW 차량 디자인에 혼합 현실 구현

리얼타임 기술과 VR이 자동차 제조의 새로운 시대를 열고 있는 가운데, 자동차 디자인 분야는 빠르게 변화하고 있습니다. BMW와 MIN...