2015年4月21日

パフォーマンスを高めるために TArray の使用を最適化する

プログラミング

機能

ニュース

作成 Zak Middleton

アンリアルエンジンでは、TArray は動的にサイズ調整される型付きの要素の配列です。 TArray はプログラマにとって非常に便利なものであり、エピックのコードベースでも *数多く* 使われています。ただし、生じうるパフォーマンス上の問題が少々あります。最適なパフォーマンスを得るためには、裏で何が起こっているかを理解する必要があります。

賢明な選択をする: 「TArray を使用することが適切でしょうか？」

常にパフォーマンスを語る場合、コードをプロファイリングして、問題がある適切なエリアに対処するようにします。初めから問題発生を回避する賢明な事前の対策を講じるのもよいでしょう。

コンテナタイプ(TArray、TSet、TMap など) では、考慮すべき最も重要なことは多くの場合、クリティカルパスでのコードのオペレーションを考えて適切なコンテナを使用しているかどうかということです。例えば、固有の要素のリストを維持し、それに対して追加、削除、検索などを頻繁に行う必要がある場合、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:関数パラメータとして使用される場合、TArrays を参照渡しにします。

1.1 の例で、TArray の参照を取るために関数がどのように宣言されているかに注意してください。代替の宣言を検討します。

// 配列を値渡しします!
void AppendCharacterCopies(char Original, int32 N, TArray<char> Result)

値渡しすることで、この関数の呼び出し元はまずその配列のコピーを作ってから、それをAppendCharacterCopies() に渡します。これはメモリを割り当て、すべての要素を新しい TArray にコピーするため、負荷が高くなります。言うまでもなく、これは、配列の呼び出し元のコピーに影響を与えるという関数の本来の目的から外れます。

基本的なことに思えるかもしれませんが、単に "&" がないだけでいくつかの重大なサイクルが犠牲になります。

2. また割り当てポリシーに従い、デフォルトでアイテムが削除され、 TArray は縮小し、メモリを再割り当てします。

TArray は要素をコンパクトな線形配列に格納します。リストの最後を除く任意の場所から要素を削除すると、その位置より後にあるすべての要素がギャップを埋めるためにシフトします。さらに、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--;   // このインデックスを再度処理する必要があるためです!
		}
	}
	
	// 任意: 値の削除後に空き領域を回収します。
	Numbers.Shrink();
}

TArray には同じような働きをする以下のような組み込み関数があります。RemoveAll、RemoveAllSwap、RemoveSingle、RemoveSingleSwap などはすべて配列から要素を削除できるようにする便利なツールであり、既に効率的な実装を持っています。

3.TArray のデフォルトのアロケータは、動的 (ヒープ) メモリアロケータです。

場合によっては、このアロケータが適切かつ必要とするものであり (特に配列が非常に大きくなりうる場合)、TArray を非常に便利なものにします。しかし、ヒープ割り当て: ロックには以下のように負荷がかかります。空きブロックを探す負荷と、より多くのアドレス領域にアクセスしているためキャッシュの汚染があります。

しかし、場合によっては、わずかな労力でパフォーマンスを向上できるオプションがあります。こうしたオプションのひとつは、デフォルトではなく別のアロケータを使用することです。一般的に、これは面倒そうですが、UE4 ではとても簡単にできます。

ここでご紹介するのは、TInlineAllocator という便利なアロケータです。これは、特にコンテナ用 (TArray など) に設計されたアロケータであり、以下の 2 つのテンプレートパラメータを取ります。

- インライン要素数

- セカンダリアロケータ (デフォルトでヒープアロケータになります)。

最初の引数 (インライン要素数) は非常に注目すべきもので、アロケータがインスタンス化される場所でただちにこのメモリ領域を確保します。領域がなくなったら、アロケータは要素をセカンダリアロケータによって作られたオーバーフロー領域に移動します。TArray では、スタックで宣言された配列は、その多くの要素のために直接スタック上に領域を確保します。クラスまたは構造体の一部として宣言された TArray は、インラインの割り当てをそのクラスまたは構造体の一部として格納し、配列の一部として追加された最初の N 要素に対して動的割り当てはしません。

これにはいくつかのメリットがあります。一般的なケースで配列に入れる予測最大数を把握していれば、すべてが TArrayの一部として作成された領域に入るためどのようなヒープ割り当ても 完全に回避 できます。さらに、要素が追加されるに従い、定期的に配列が大きくなり、その要素を新たに割り当てられた領域にコピーする必要はありません。

つまり、通常の TArray を使用して、以下のようにします。

TArray<Shape*> MyShapeArray;

そして以下のように簡単に変更します。

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

この例では、配列に加えられた最初の 16 要素の動的割り当てを回避します。これらは、TInlineAllocator の一部であるスタック上の領域にフィットするからです。17 要素以上では、すべての要素は格納のためにセカンダリアロケータ (すなわちヒープアロケータ) に移動します。

TInlineAllocator のサイズは、コンパイル時に決められなければなりません。配列の *あらゆる* インスタンスに対して、スピードアップと予め領域を確保することで生じうるトレードオフは各自の判断に委ねられます。TFixedAllocator も説明する価値があります。これは、TInlineAllocator と類似していますが、セカンダリバックアップアロケータを持ちません。固定メモリ部分で領域がなくなればコードでエラーが発生します。

4.型を簡単に使用できるものにする。

一般的に、配列の型を宣言する良い方法は (一部の入力の手間も省きます) 、typedef を使用することです。このやり方は、ハードコーディングされたインライン要素数をひとつの場所で更新し、それをすべてのインスタンスに簡単に伝搬するというメリットもあります。例：

// 型を宣言
typedef TArray<Shape*, TInlineAllocator<16>> ShapeArrayType;

// インスタンスを作成
ShapeArrayType MyShapeArray;

任意の型のTArrays をイタレーションする場合、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 型変換

異なるアロケータを持つ TArrays (または任意のコンテナ) は実際に異なる型であることに注意してください。そのため、別の 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);
	
	// *error*: TArray から変換できません。<Shape*, TInlineAllocator<16>>&
	// to 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);     
}

以上です！単純な追加で、さらに柔軟性を高め、どのアロケータ型のTArrays でも機能するようにしました。

最後に注意すべきこととしては、テンプレートの引数を大きな関数に加える場合に起こりうるコードの膨張に気を付けてください。コンパイラは、使用される各テンプレート型に対してコードのバージョンを生成するからです。他の選択肢としては、単にコード内で一貫性のある typedef を使用することです。これは単一の型だけを使用できますが、簡単に変更できます。