JacksonDunstan.com

Today’s article is about a new native collection type: NativeChunkedList<T>. This type is great when you need a dynamically-resizable array that’s fast to add to and doesn’t waste a lot of memory. Read on to see how it’s implemented, see the performance report, and get the source code.

NativeList

NativeList<T> is Unity’s native version of the C# List<T> type: a dynamically-resizable array. It’s part of the com.unity.collections package that comes with Unity’s ECS, which is still in Preview as of Unity 2018.2. This type stores elements in a single native/unmanaged array, just like NativeArray<T> does. That array has a capacity which is equal to or greater than the number of elements stored, known as the length. When an element is added and there is spare capacity, it’s simply added to the end. If there’s no more spare capacity, a new array with twice the capacity is allocated, all the elements are copied over, the old array is freed, and the element is added to the end.

The performance characteristics of this approach are usually quite good. Accessing the list is just as fast as accessing a NativeArray<T> because it is represented exactly the same: just one array. However, growing the list is quite expensive as it requires copying the whole list to a new array. Likewise, the doubling of capacity can result in quite a lot of waste. For example, if an element is added to a full list with 1024 capacity then the new capacity will be 2048 even though room for only 1025 elements is needed.

Chunked List Approach

Today’s approach aims to solve these issues with NativeList<T>. Like how Unity’s ECS stores components, NativeChunkedList<T> stores its components in “chunks.” Each chunk is simply an array of elements. It then also stores an array of pointers to the chunks.

Here’s how the memory is laid out:

This layout allows us to traverse the list in a reasonably cache-friendly way. We’ll access sequential memory as we traverse a chunk, just like with NativeList<T> and NativeArray<T>. When we get to the end of a chunk, we might miss the CPU cache but then we’ll be accessing sequential memory again as we traverse the new chunk. The chunk pointers are also sequentially laid out in an array, so traversing them is cache-friendly too.

Random access is also easy and fast. All we need to do is compute the chunk pointer index (i / numElementsPerChunk) and then use it to index into the chunk (i % numElementsPerChunk).

Adding to a NativeChunkedList<T> is similar to NativeList<T>, but with a critical difference. If the last chunk has spare capacity, we just add the element at the end of it. If it doesn’t, we allocate a new chunk and add the element at the beginning of it. If there’s no spare capacity in the array of pointers, we allocate a new array, copy the old array over, and free the old array. This is just like the backing array of NativeList<T>, but much faster because each element is only a pointer and there are relatively few pointers since each one allows for a whole chunk of elements to be stored.

Several more operations are supported, but their implementations aren’t particularly noteworthy as nearly everything can be implemented just like with any array-backed type like NativeList<T> or even List<T>. In fact, NativeChunkedList<T> has many of the same methods and properties as NativeList<T> and List<T> so that it’s easy to use for those familiar with those types. Here’s the full API:

struct NativeChunkedList<T>
    : IEnumerable<T>
    , IEnumerable
    , IDisposable
    where T : struct
{
    NativeChunkedList(int numElementsPerChunk, int capacity, Allocator allocator);
    void Add(T element)
    void AddRange(NativeArray<T> array, int startIndex, int length);
    void AddRange(T[] array, int startIndex, int length);
    int Capacity { get; set; }
    void Clear();
    void CopyFrom(NativeArray<T> array, int startIndex, int length);
    void CopyFrom(T[] array, int startIndex, int length);
    void Dispose();
    Enumerator GetEnumerator();
    IEnumerator GetEnumerator();
    IEnumerator<T> IEnumerable<T>.GetEnumerator();
    void Insert(int index, T element);
    bool IsCreated { get; }
    int Length { get; }
    T this[int index] { get; set; }
    void RemoveAt(int index);
    void RemoveAtSwapBack(int index);
    T[] ToArray(
        T[] array = null,
        int startIndex = 0,
        int destIndex = 0,
        int length = -1);
    NativeArray<T> ToNativeArray(
        NativeArray<T> array = default(NativeArray<T>),
        int startIndex = 0,
        int destIndex = 0,
        int length = -1);
}

Performance Testing

Now let’s pit NativeChunkedList<T> against NativeArray<T>, NativeList<T>, and NativeLinkedList<T> to see how it performs on a variety of operations. These tests were conducted with 10000 int elements in each collection. NativeChunkedList<T> was configured with a chunk size of 1024 bytes which equals 256 elements per chunk of int values.

The following operations were tested for each collection that supports them:

• Add: Starting from an empty collection, append an element to the end
• Iterate (Single): Iterate over the full collection in an IJob
• Iterate (ParallelFor): Iterate over the full collection in an IJobParallelFor
• Insert: Starting from an empty collection, insert elements into the middle
• Remove: Starting from a full collection, remove elements from the middle

// Create an empty list with capacity for 4096 elements in 1024 element chunks
NativeChunkedList<int> list = new NativeChunkedList<int>(
    1024,
    4096,
    Allocator.Temp);
 
// Add some elements to the list
list.Add(10);
list.Add(20);
list.Add(30);
list.Add(40);
list.Add(50);
 
// Iterate over the list
foreach (int val in list)
{
    Debug.Log(val);
}
 
// Remove an element from the middle
list.RemoveAt(2);
 
// Insert an element into the middle
list.Insert(1, 15);
 
// Access the elements sequentially
for (int i = 0; i < list.Length; ++i)
{
    Debug.Log(list[i]);
}
 
// Dispose the list's native memory
list.Dispose();