Avoiding array reallocations in Unreal Engine

In Unreal Engine, TArray is a dynamically sized array of elements. TArray grows and reallocates memory according to an allocation policy as elements are added to it. With each reallocation, it must copy all the elements to the new memory and delete the old memory. Depending on how hot the code path is, this can have a performance impact on your project.

Using TArray efficiently

Controlling reallocations during adding and deleting elements

One way to avoid memory reallocations during adding new elements is to reserve all the needed memory upfront. You can do it using the TArray::Reserve method.

TArray also reallocates its elements as you remove elements from anywhere but from the end of the array. To avoid shifting all consecutive elements after removing an element there’s a TArray::RemoveAtSwap method.

Inline allocator

TArray default mode of operation is allocating memory for its elements in the heap. Although fine for most applications, this can be not ideal in some cases. Luckily we can specify a custom allocator during TArray construction, and TInlineAllocator is just what is needed. The inline allocator allocates up to a specified number of elements in the same allocation as the container, for example on the stack, and has a safe mode for allocations beyond that limit, moving all the elements to an indirect allocation. TInlineAllocator takes two template parameters: the number of elements and a secondary allocator, defaulting to heap allocator. Usage is quite simple:

// Allocating an inline array with up to 16 elements
TArray<FExampleStruct, TInlineAllocator<16>> ExampleInlineArray;

Using additional array-like containers

Unreal Engine containers library provides a host of both general-purpose and highly specialized containers. This is a game engine after all. To keep the scope of this post narrow, I will only list containers that address reallocation particularly.

TIndirectArray

TIndirectArray is a container similar to TArray with the only difference in that the former stores pointers to its elements. In the case of reallocation, an indirect array reallocates only its internal element pointers storage, leaving actual elements as is.

TChunkedArray

TChunkedArray is a bit more interesting. As you might expect from a chunked array, it stores its elements in chunks of memory. This has two consequences. Firstly, as new elements are added to a chunked array, only new chunks are added, and old ones are never reallocated. Secondly, with chunks of size small enough you can mitigate possible allocation failures due to memory fragmentation.

Conclusion

If the results of your profiling sessions suggest that your code may spend a significant amount of time reallocating arrays, there are quite a few ways to get around it. Unreal Engine provides a wide selection of tools to efficiently use memory and CPU time.