JacksonDunstan.com

Native Collection Safety

Unity's native collection system is brand new, poorly documented, and virtually never used by anyone outside of Unity. This is the major motivation of this series of articles. By implementing a relatively simple data structure as a native collection, we can focus on learning the native collection system rather than learning the data structure. This week we address a serious error in how we implemented safety checks in last week's article.

Recall that NativeLinkedList<T> is a struct that contains just one field: NativeLinkedListState* m_State. When Unity's native collection safety checks are enabled with the ENABLE_UNITY_COLLECTIONS_CHECKS preprocessor symbol, the struct also has int m_Length, int m_MinIndex, int m_MaxIndex, AtomicSafetyHandle m_Safety, and DisposeSentinel m_DisposeSentinel fields. Now consider how an innocent-looking function like the Length property was defined last week:

public int Length
{
    get
    {
        RequireValidState();
        return m_State->m_Length;
    }
}

RequireValidState looked like this:

[Conditional("ENABLE_UNITY_COLLECTIONS_CHECKS")]
[BurstDiscard]
private unsafe void RequireValidState()
{
#if ENABLE_UNITY_COLLECTIONS_CHECKS
    if (m_State == null)
    {
        throw new InvalidOperationException(
            "NativeList was either not initialized via a " +
            "non-default constructor or was used after calling " +
            "Dispose().");
    }
#endif
}

So the only check that occurred before using the m_State pointer was to see if it was null. Now let's consider the following scenario:

// Create a list of ten zeroes
NativeLinkedList<int> a = new NativeLinkedList<int>(10, 10, Allocator.Temp);
 
// Copy the list. m_State is now shared among both 'a' and 'b'.
NativeLinkedList<int> b = a;
 
// Dispose the first copy of the list
// This frees the memory pointed to by the shared m_State
// It sets a.m_State to null, but not b.m_State
a.Dispose();
 
// Access b.m_State, which has been freed
// This may crash the app or corrupt memory
b[0] = 100;

The issue is that calling Dispose on one list doesn't invalidate all the copies of that list. We'll face dire consequences by using those copies and have very little safety net to help us debug. Thankfully, Unity has provided a better way to check if the list is safe to use.

Rather than simply checking if m_State is null before using it, we should instead check based on how we intend to use the list: reading or writing. We already had these two checks, but simply weren't using them outside of actual reading and writing of the node data. We need to also use them when accessing anything in m_State:

[Conditional("ENABLE_UNITY_COLLECTIONS_CHECKS")]
[BurstDiscard]
private unsafe void RequireReadAccess()
{
#if ENABLE_UNITY_COLLECTIONS_CHECKS
    AtomicSafetyHandle.CheckReadAndThrow(m_Safety);
#endif
}
 
[Conditional("ENABLE_UNITY_COLLECTIONS_CHECKS")]
[BurstDiscard]
private unsafe void RequireWriteAccess()
{
#if ENABLE_UNITY_COLLECTIONS_CHECKS
    AtomicSafetyHandle.CheckWriteAndThrow(m_Safety);
#endif
}

So the new Length property looks like this:

public int Length
{
    get
    {
        RequireReadAccess();
        return m_State->m_Length;
    }
}

It seems like a simple change, but it was a widespread issue that could cause serious problems. So in this week's version of NativeLinkedList<T>, every function except the constructor has a call to either RequireReadAccess, RequireWriteAccess, or both. The result is that the above scenario simply causes an exception to be thrown.

Culling Permutations

Last week we added support to pass a NativeLinkedList<T> to PushBack, PushFront, InsertAfter, and InsertBefore. We already had support for passing a single value to each of these functions. This meant we had four functions and two types to pass to them for a total of eight permutations of functions to write, document, and test.

This week I wanted to add support for two new types: NativeArray<T> and the managed array T[]. This would mean four functions and four types for a total of 16 permutations. I know that in the future I'm going to want to add support for ranges of iterators, Unity's NativeList<T>, and more. I also want to include support for adding full collections and partial collections. The permutations are quickly getting out of hand resulting in a maintenance headache and bloated binary executable size.

To this end, I've removed the PushBack and PushFront functions. They were largely redundant with InsertAfter() when passed the tail enumerator and InsertBefore when passed the head enumerator. The only part they couldn't cover was inserting into an empty list because there was no valid enumerator to insert before or after. By adding this special case, these insert methods are now able to effectively and efficiently replace the push methods.

As a result, we now have support for NativeArray<T> and T[] in InsertAfter and InsertBefore. There's a total of two functions and four types which again leads to last week's eight permutations. This isn't a permanent solution, but it will at least cut the scope in half.

// Build a native array
NativeArray<int> array = new NativeArray<int>(3, Allocator.Temp);
array[0] = 40;
array[1] = 50;
array[2] = 60;
 
// Insert the native array at the end, like the old PushBack
list.InsertAfter(list.Tail, array);
 
// Insert a managed array at the beginning, like the old PushFront
list.InsertBefore(list.Head, new [] { 10, 20, 30 });
 
// list is now: 10 - 20 - 30 - 40 - 50 - 60

Enumerator Upgrades

The NativeLinkedList<T>.Enumerator type gets a few upgrades this week. We now have overloads of MoveNext and MovePrev that take an int numSteps parameter. These overloads perform a loop and seek forward or backward until either hitting the end of the list or the desired number of steps. This is an easy and efficient way to skip multiple nodes of the list:

// Process two nodes per iteration (e.g. for key-value pairs)
for (NativeLinkedList<int>.Enumerator e = list.Head;
    e.IsValid;
    e.MoveNext(2))
{
    Debug.Log("Key: " + e.Value);
}

In addition to IsValid, enumerators can also be checked for their validity to a specific list:

if (e.IsValidFor(list))
{
    Debug.Log("can use 'e' this with 'list'");
}

This function is useful for users of NativeLinkedList<T> and for the internal implementation too, as all enumerators passed to its methods are checked using this new function.

More List Functionality

Some new methods have been added for lists this week. First, GetEnumeratorAtIndex allows for the quick creation of an enumerator at a given index. This is a raw index like when the indexer is used after a call to SortNodeMemoryAddresses, not a function that seeks from the head. This makes the function fast, just like using the indexer, rather than an expensive and possibly CPU cache-unfriendly pointer chase.

// Create a list of five zeroes
NativeLinkedList<int> list = new NativeLinkedList<int>(5, 5, Allocator.Temp);
 
// Get an enumerator at index 3
NativeLinkedList<int>.Enumerator e = list.GetEnumeratorAtIndex(3);
 
// Set the node at index 3
e.Value = 100;
 
// list is now: 0 - 0 - 0 - 100 - 0

Next, RemoveAll has been added to quickly clear the list by removing all nodes. None of the node values, next pointers, or previous pointers need to be set as the list can be quickly forgotten by invalidating the head and tail pointers, all enumerators by incrementing the version, and setting the length to zero. Removing all nodes is therefore really fast:

// Create a list of five zeroes
NativeLinkedList<int> list = new NativeLinkedList<int>(5, 5, Allocator.Temp);
 
// Clear the list
list.RemoveAll();
 
// list is now empty

Finally, the new Swap function takes two enumerators and swaps those nodes' values. By swapping values rather than next and previous pointers, we're more friendly to the CPU cache since we don't need to read and write what are likely eight different areas of memory: each node's next and previous node's next and previous pointers. Instead, we'll copy the value which is contiguous in memory due to the T type being blittable. We also gain the advantage of the node values swapping along with their indices so we can keep treating the list as though it was an array using the indexer and GetEnumeratorAtIndex:

// Make a list: 10 - 20 - 30 - 40 - 50
NativeLinkedList<int> list = new NativeLinkedList<int>(5, Allocator.Temp);
list.InsertAfter(list.Tail, 10);
list.InsertAfter(list.Tail, 20);
list.InsertAfter(list.Tail, 30);
list.InsertAfter(list.Tail, 40);
list.InsertAfter(list.Tail, 50);
 
// Swap the head (10) and tail (50)
list.Swap(list.Head, list.Tail);
 
// Print all the node values by index
for (int i = 0; i < list.Length; ++i)
{
    Debug.Log(list[i]); // prints: 50, 20, 30, 40, 10
}

Better List Copying

Previously, CopyToNativeArray allowed specifying a starting enumerator, number of nodes to copy, and starting index to copy to. ToArray, the managed array version, only supported copying the full list to the first index of the given array. The same was the case for CopyToNativeArrayReverse and ToArrayReverse. With this week, ToArray and ToArrayReverse now accept all these same parameters for greater flexibility in copying the list's values to managed arrays.

Speaking of CopyToNativeArray and CopyToNativeArrayReverse, they've been renamed to match their managed counterparts and are now called ToNativeArray and ToNativeArrayReverse.

Lastly, there are now versions of all four of these functions that copy the entire list with no parameters. These "full" versions are more efficient as there are fewer parameters to validate.

// Make a list: 10 - 20 - 30 - 40 - 50
NativeLinkedList<int> list = new NativeLinkedList<int>(5, Allocator.Temp);
list.InsertAfter(list.Tail, 10);
list.InsertAfter(list.Tail, 20);
list.InsertAfter(list.Tail, 30);
list.InsertAfter(list.Tail, 40);
list.InsertAfter(list.Tail, 50);
 
// Copy 3 nodes starting at the second node (20) to a managed array
// starting at index 2
int[] managedArray = new int[list.Length];
list.ToArray(managedArray, list.Head.Next, 2, 3);
// managedArray is now: [ 0, 0, 20, 30, 40 ]
 
// Copy the full list in reverse to a native array
NativeArray<int> nativeArray = new NativeArray<int>(list.Length, Allocator.Temp);
list.ToNativeArrayFullReverse(nativeArray);
// nativeArray is now: [ 50, 40, 30, 20, 10 ]

Testing and Documentation

Aside from raw functionality, the project includes unit tests, performance tests, and documentation. All three have been upgraded this week.

There are now 156 unit tests covering every one of the functions, at least to some degree. Further edge-case testing is required to gain maximum confidence, but for now the number of unit tests is up over 70%.

Each function now has xml-doc documentation on it stating its access requirements and time complexity. This will help to know whether the function needs read access or write access, exclusive access outside of a ParallelFor job, or access to particular nodes within a ParallelFor job. Likewise, the time complexity should help understand the cost of calling each function as it may not be apparent from the function signature.

Finally, a few more performance tests have been added to measure the time required to initialize the native collections from a C# job. NativeLinkedList<T>.Insert seems to perform about as well as NativeList<T>.Add in this capacity, but formal measurements are yet to be taken.

Conclusion

Today we've added some safety, functionality, and support to the NativeLinkedList<T> type. There's still more to do, but the type is much more correct and complete now. To use it in your own project or just to learn more about how it was implemented, including all the nitty gritty details of compliance with Unity's native collections system, check out the GitHub project.

Continue to part four.