JacksonDunstan.com

Feature Additions

Last week we removed the PushFront and PushBack functions in favor of improved InsertBefore and InsertAfter functions that could perform the same operations. This culled the number of permutations of overloads, allowing us to add more overloads of InsertBefore and InsertAfter. This week that decision pays off by allowing us to add support for inserting ranges of NativeLinkedList<T>, NativeArray<T>, and T[]. This only adds six permutations—three types times two functions—rather than if we still had PushFront and PushBack and needed to add 12 permutations: three types times four functions. Here's how to insert ranges:

// Create an empty list to insert into
NativeLinkedList<int> list = new NativeLinkedList<int>(5, Allocator.Temp);
 
// Create a list to insert
NativeLinkedList<int> insertList = new NativeLinkedList<int>(4, Allocator.Temp);
insertList.InsertAfter(insertList.Tail, 10);
insertList.InsertAfter(insertList.Tail, 20);
insertList.InsertAfter(insertList.Tail, 30);
insertList.InsertAfter(insertList.Tail, 40);
 
// Insert the (20 - 30) range of the list
list.InsertAfter(list.Head, insertList.Head.Next, insertList.Tail.Prev);
 
// Create a native array to insert
NativeArray<int> insertNativeArray = new NativeArray<int>(4, Allocator.Temp);
insertNativeArray[0] = 100;
insertNativeArray[1] = 200;
insertNativeArray[2] = 300;
insertNativeArray[3] = 400;
 
// Insert the [200, 300] range of the native array
list.InsertAfter(list.Tail, insertNativeArray, 1, 2);
 
// Create a managed array to insert
int[] insertManagedArray = new [] { 1000, 2000, 3000, 4000, 5000 };
 
// Insert the [2000, 3000] range of the managed array
list.InsertAfter(list.Tail, insertManagedArray, 1, 2);
 
// Dispose the native collections
list.Dispose();
insertList.Dispose();
insertNativeArray.Dispose();

The only other feature addition this week is a new Enumerator function: GetDistance. This function takes an enumerator that's either the same or toward the tail relative to the this enumerator. It walks the list's next pointers until it either finds the enumerator or the end of the list. Then it returns the number of next pointers it needed to follow to get to the enumerator, or -1 if the tail was found. This is useful internally to determine if the enumerator range passed to InsertBefore or InsertAfter is valid and how much capacity needs to be available to insert that range of nodes. Users of Enumerator may also find it useful for various purposes.

// for a list that is (10 - 20 - 30 - 40 - 50)
list.Head.GetDistance(list.Head); // 0
list.Head.GetDistance(list.Head.Next); // 1
list.Head.GetDistance(list.Tail); // 4

Finally, while not strictly a new feature, RemoveAll has been renamed Clear to match the naming convention of Unity's NativeList<T> type.

Correctness

Native collections must operate on blittable types, but NativeLinkedList<T> wasn't explicitly requiring this like NativeArray<T> was. It only used the weaker where T : struct clause, but not all structs are blittable. For example, a struct with a string field isn't blittable because string is a managed type. There's now a check in the constructors that uses UnsafeUtility.IsBlittable<T> to determine whether the type parameter is blittable or not. It's unfortunate that there's no where T : blittable clause available in C# to provide us with a compile-time check, but at least Unity has provided a runtime check. Note that this check is performed every time a NativeLinkedList<T> is constructed, not just when safety checks are enabled. This matches the behavior of NativeArray<T>.

Next, functions taking a NativeArray<T> in NativeLinkedList<T> were checking whether the array's IsCreated returned false and throwing an exception if it did. As discussed last week, this isn't a very useful check to make because calling Dispose on one copy of a NativeArray<T> doesn't make IsCreated return false on other copies. The more complete check was already being implicitly performed by simply using the NativeArray<T>. So these checks have been removed as they were redundant, incomplete, and perhaps even leading to a false sense of security.

On the other hand, managed arrays are now checked for null before being used. Unlike the IsCreated check that was removed, testing for null is sufficient with a managed array. It's a small addition, but it should lead to better error messages when accidentally passing a null array.

Finally, many functions require exclusive access to the list and aren't suitable for usage from ParallelFor jobs. The check for this exclusive access was incorrect. Here's the change:

// Old
if (m_MinIndex > 0 || m_MaxIndex >= m_Length)
 
// New
if (m_MinIndex > 0 || m_MaxIndex < m_Length - 1)

Unit Tests

Of course unit tests have been added for all of the new functionality described above, but additional unit tests have been added for existing functionality too. One such type of unit test is to check for error handling when the user of the list attempts to access outside of the ParallelFor safety bounds: from m_MinIndex to m_MaxIndex. Since these fields are private and Unity's C# job system sets them automatically when running jobs, we need a way to set them in the testing environment. Actually running a ParallelFor job is verbose and not predictable enough for a unit testing environment, so that's not an appealing option. Instead, we'll add a public function for testing purposes only:

[Conditional("ENABLE_UNITY_COLLECTIONS_CHECKS")]
[BurstDiscard]
public void TestUseOnlySetParallelForSafetyCheckRange(
    int minIndex,
    int maxIndex)
{
#if ENABLE_UNITY_COLLECTIONS_CHECKS
    m_MinIndex = minIndex;
    m_MaxIndex = maxIndex;
#endif
}

It's unfortunate that we can't expose just this one function to just the unit test code, so it has to be public. That means that real user code could set the safety check range, but hopefully they're dissuaded from this by starting the method's name with TestUseOnly. Regardless, now we can test for accesses out of the safety check bounds like so:

[Test]
public void IndexerGetCannotReadOutOfParallelForSafetyBounds()
{
    // Create a list with capacity for three nodes
    using (var list = new NativeLinkedList<int>(3, Allocator.Temp))
    {
        // Add 10 - 20 - 30 to the list
        list.InsertAfter(list.Tail, 10);
        list.InsertAfter(list.Tail, 20);
        list.InsertAfter(list.Tail, 30);
 
        // Restrict the accessible range to just 10 and 20
        list.TestUseOnlySetParallelForSafetyCheckRange(0, 1);
 
        // Try to read 30 which is outside the safety check range
        // This should throw an IndexOutOfRangeException
        Assert.That(() => list[2], Throws.TypeOf<IndexOutOfRangeException>());
 
        // Reset bounds so the "using" block can call Dispose()
        list.TestUseOnlySetParallelForSafetyCheckRange(0, list.Length - 1);
    }
}

This function can also be used to add unit tests that attempt to use the list when exclusive access to it is required. All that's required to run this kind of test is to restrict the safety check range to anything but the full list and then attempt to call a method like Remove that requires exclusive access.

The last kind of unit test added this week exists to test each function's access requirements. Many functions require read, write, or read and write access to the list. It turns out that Unity provides a way to revoke both read and write access. We can expose this in another test-only function:

[Conditional("ENABLE_UNITY_COLLECTIONS_CHECKS")]
[BurstDiscard]
public void TestUseOnlySetAllowReadAndWriteAccess(bool allowReadOrWriteAccess)
{
#if ENABLE_UNITY_COLLECTIONS_CHECKS
    AtomicSafetyHandle.SetAllowReadOrWriteAccess(m_Safety, allowReadOrWriteAccess);
#endif
}

It's unfortunate that both read and write access need to be revoked rather than just read or write access, but there doesn't seem to be a way to revoke just one. Regardless, this function can be used to check for error-handling exceptions due to a lack of access permissions:

[Test]
public void IndexerGetWhenWriteOnlyThrowsException()
{
    // Create a list with capacity for three nodes
    using (var list = new NativeLinkedList<int>(3, Allocator.Temp))
    {
        // Add 10 - 20 - 30 to the list
        list.InsertAfter(list.Tail, 10);
        list.InsertAfter(list.Tail, 20);
        list.InsertAfter(list.Tail, 30);
 
        // Revoke read and write access
        list.TestUseOnlySetAllowReadAndWriteAccess(false);
 
        // Try to read without read access
        // This should throw an InvalidOperationException
        Assert.That(
            () => val = list[0],
            Throws.TypeOf<InvalidOperationException>());
 
        // Restore read and write access
        list.TestUseOnlySetAllowReadAndWriteAccess(true);
    }
}

Keep in mind that since each Enumerator has its own copy of the list, this means that these test-only functions need to also be added to the Enumerator struct so they can be used when testing functions like MoveNext.

Performance Tests

The performance tests so far haven't covered the key reasons to use a linked list in the first place: inserting and removing from the middle of the sequence. When these operations are performed on a NativeArray<T> or NativeList<T>, all the elements need to be shifted forward or backward by one in order to maintain a contiguous sequence of values in memory. This is an expensive operation as it scales with the number of elements in the sequence: O(N). With a doubly-linked list like NativeLinkedList<T>, the amount of work required is constant—O(1)—because just some next and previous pointers need to be modified and one element copied to or from the end of the arrays.

I ran the performance tests in this environment:

• 2.7 Ghz Intel Core i7-6820HQ
• macOS 10.13.6
• Unity 2018.2.0f2
• com.unity.entities package 0.0.12-preview.8
• macOS Standalone
• .NET 4.x scripting runtime version and API compatibility level
• IL2CPP
• Non-development
• 640×480, Fastest, Windowed

Here are the results I got:

Initialize: It's hard to say why NativeList<T> was so much faster than the others since calling Add should be slower than simply setting elements in the case of NativeArray<T>. A number along the lines of NativeLinkedList<T> and its InsertAfter calls seems more appropriate, so this result remains a mystery. Regardless, NativeLinkedList<T> was somewhat slower than NativeArray<T>, which does make sense since it's doing some additional work like checking whether the list's capacity needs to grow.

Iterate: All three collections have very similar times in the Single (IJob) mode. NativeList<T> is again, inexplicably, somewhat faster than the others. However, NativeList<T> cannot be used from a ParallelFor (IJobParallelFor) job, so it's left out of that test. NativeArray<T> and NativeLinkedList<T> perform similarly and both of them are faster than the fastest Single iteration time by a small margin.

Insert: Inserting at the beginning of the collection is one of the areas where a linked list should shine, and NativeLinkedList<T> does just that. It's 385x faster than NativeArray<T> and 575x faster than NativeList<T> at this operation.

Remove: Removing at the beginning of the collection is the other area where NativeLinkedList<T> should do well and it again delivers here. It's 219x faster than NativeArray<T> and 1022x faster than NativeList<T>.

Conclusion

This week we've added a little more functionality in the forms of range support for InsertBefore and InsertAfter as well as the new GetDistance enumerator method. We've improved correctness by enforcing that T is blittable, not checking NativeArray<T>.IsCreated, checking managed arrays for null, and fixing the ParallelFor detection. We've tested the error-handling code and brought the unit test count up another 84% to a total of 287. And we've tested the performance of NativeLinkedList<T> against its chief competitors and found that it does indeed deliver array-like performance in most areas and multiple orders of magnitude better performance when inserting or removing at the beginning of the collection.

At this point we have a featureful, safe, performant, easy-to-use, dependency-free, permissively-licensed, and well-documented native linked list type available to us. It should serve as a useful tool, especially while working with C# jobs and Unity's ECS. It should also be easy to read through and gain an improved understanding of how to build a native collection type in Unity. Check out the GitHub project if you're intested in the full code.