Continuing from last time, today we’ll greatly expand on the fledgling NativeLinkedList<T> that we started last time. By the end of the article, we’ll have a useful native collection available to us!

Previously

When we left off last time, we had a very basic NativeLinkedList<T> type with these features:

  • Iterate the list forward and backward
  • Get and set node values at a given iterator
  • Push nodes to the beginning or end of the list with dynamic resizing
  • Remove nodes from the list
  • Copy the list’s nodes to a managed array or NativeArray<T>

Those are good basics to build on. Today, we add on a lot of features.

List as Pointer

NativeLinkedList<T> is now a pointer to its contents, similar to NativeArray<T>. Previously, it directly contained fields like the list's head and tail indices. This meant that each copy of the list would have its own view of the list's state. Since the list is a struct and is usable in the C# job system, copying would happen all the time.

With today's update, the list now contains only one field when safety checks are disabled: a pointer to a NativeLinkedListState struct in unmanaged memory. This struct contains all the fields that used to be directly in the list. By adding this bit of indirection, every copy of the list shares the same pointer and therefore the same state. They can now be copied at will. However, this also means that we can no longer use NativeArray<T> to hold the node values, next pointers, and previous pointers because it's technically a managed type and we can't have a pointer to any struct containing one. So we'll go ahead and use UnsafeUtility functions like Malloc, Free, ReadArrayElement, WriteArrayElement, MemCpy, and MemCpyStride to create and access unmanaged arrays on our own.

There's one caveat to this: safety checks. These are enabled by Unity using a preprocessor symbol: ENABLE_UNITY_COLLECTIONS_CHECKS. Additionally, NativeLinkedList<T> has the [NativeContainerSupportsMinMaxWriteRestriction] attribute so that it can be used in a ParallelFor job. This requires the following fields with exact names, types, and ordering:

private int m_Length;
private int m_MinIndex;
private int m_MaxIndex;

Adding these seems to undo the previous progress toward sharing the list's state, but it actually helps. This is because the list can be used in several different ways and these values provide the necessary context for the list to enforce safety checks. Here are the ways the list can be used:

  • Outside of a C# job
  • In a Single C# job like IJob
  • In a ParallelFor C# job like IJobParallelFor where the chunk of the list that Execute(int index) is being called on encompasses the entire list
  • In a ParallelFor C# job like IJobParallelFor where the chunk of the list that Execute(int index) is being called on is a sub-region of the list

The first three cases can largely be considered the same for the purposes of the list's code. In conjunction with the job system's dependency management, all of them guarantee that the list code has exclusive access to the entire list. The list code can determine this by checking that m_MinIndex == 0 && m_MaxIndex == m_Length - 1. In these cases, it's safe to make any change to the list as there's no way concurrent code could be accessing it.

In the fourth case, however, concurrent code may be accessing the list. To avoid data contention issues, we have to restrict the set of operations that are available in this case. We can't allow any operation that would change the list's head pointer, tail pointer, length, or cause reallocation because this data is shared between all concurrent Execute functions of ParallelFor jobs operating on the list. We can, however, allow modification of node values within the acceptable range as defined by [m_MinIndex, m_MaxIndex]. So while many operations like PushBack aren't allowed, we can still allow getting and moving enumerators as well as getting and setting node values.

In the end, we can now treat lists like pointers and make as many copies as we want with the assurance that changes to one will be reflected to the others:

void ChangeHeadTo100(NativeLinkedList<int> list)
{
    list.Head.Value = 100;
}
 
NativeLinkedList<int> list = new NativeLinkedList<int>(4, Allocator.Temp);
list.PushBack(10);
ChangeHeadTo100(list); // make a copy and pass it to the function
Debug.Log(list.Head.Value); // prints: 100
Enumerable and Enumerator

NativeLinkedListIterator is now NativeLinkedList<T>.Enumerator and implements the IEnumerator and IEnumerator<T> interfaces. NativeLinkedList<T> also implements the IEnumerable and IEnumerable<T> interfaces. Together, this means there's support for standard iteration over the collection, much like we get with NativeArray<T>. For example, we can now use a foreach loop:

// Create the list and automatically call Dispose() when exiting the block
using (NativeLinkedList<int> list = new NativeLinkedList<int>(4, Allocator.Temp))
{
    // Push some nodes to the back of the list
    list.PushBack(10);
    list.PushBack(20);
    list.PushBack(30);
    list.PushBack(40);
 
    // Iterate over the list
    foreach (int val in list)
    {
        Debug.LogFormat("Node value is: {0}", val);
    }
}

More specifically, lists now have IEnumerator GetEnumerator() and IEnumerator<T> GetEnumerator() methods to get an enumerator that moves next to the head. Lists also have Head and Tail properties to get enumerators for those nodes.

This helps NativeLinkedList<T> fit in to the .NET world and even enables the use of LINQ:

IEnumerable<int> query = from val in list
    where val > 10 && val < 40
    select val * 100;

Enumerators' values can be accessed by the new Value properties for either reading or writing. To comply with the IEnumerator and IEnumerator<T> interfaces, Current properties are provided for read-only access to a plain object or a T. The enumerators can be moved forward or backward with MoveNext() and MovePrev() or newly-created enumerators can be returned by the Next and Prev properties.

These enumerators are sometimes invalidated, such as when removing a node from the list. Previously, this wasn't very strongly enforced. Now, the list keeps a version number and assigns it to all enumerators it creates. This allows for a check to make sure that the version number still matches when using an enumerator. If the version numbers differ, the operation is invalid and an error is reported.

// Create a list
NativeLinkedList<int> list = new NativeLinkedList<int>(4, Allocator.Temp);
list.PushBack(10);
list.PushBack(20);
 
// Get an enumerator to one of its nodes
NativeLinkedList<int>.Enumerator e = list.Head;
 
// Perform an operation that invalidates the enumerator by incrementing the
// list's version number
list.Remove(list.Tail);
 
// Try to use the enumerator. This results in an error because the enumerator's
// version number doesn't match the list's version number.
e.Value = 100;

Enumerators may now also be compared with ==, !=, Equals(object), and Equals(Enumerator). These checks take into account the enumerators' validity, the index of the node they refer to in the list, and whether the lists they are for, which is now stored within the enumerator as a field, point to the same shared state. This results in being able to use them as logical comparisons for whether the two enumerators refer to the same node:

NativeLinkedList<int> listA = new NativeLinkedList<int>(4, Allocator.Temp);
listA.PushBack(10);
NativeLinkedList<int> listB = new NativeLinkedList<int>(4, Allocator.Temp);
listA.PushBack(10);
if (listA.Head != listB.Head)
{
    Debug.Log("this happens because the enumerators are for different lists");
}

Lastly, enumerators can be reset to the head of the list. This is a convenient way to restart iteration over the list just by calling the Reset function.

Cache Friendliness

As mentioned in the previous article, the list's nodes may now be sorted by memory address by calling the SortNodeMemoryAddresses function. If you know the canonical name for this operation, please let me know in the comments. Regardless, this doesn't change the order of the nodes in the list. This only changes the order of the nodes in memory. Since nodes can be rearranged in memory by various operations like inserting and removing, the resulting traversal order is quite unfriendly to CPU caches that want data to be accessed in a nice, linear fashion. This rearrangement is even quicker than a generalized sorting algorithm as it's performed in O(N) rather than O(log(N)).

After the nodes have been rearranged this way, the head of the list will be at the first element of the three parallel arrays discussed in the previous article. The next node after the head will be at the second element of the arrays. This continues all the way to the tail. Once the list has been rearranged like this, its values are laid out in memory exactly like those of a NativeArray<T> or managed T[]. This is one of the reasons that we used three parallel arrays in the previous article. The node values of the list can now be read and written using a newly-added indexer without ever needing to fill up CPU cache lines by reading the next and previous pointers. The indexer also provides fast random access and compatibility with ParallelFor jobs since they only receive an int index parameter:

// Sort the nodes so they're laid out sequentially in memory
list.SortNodeMemoryAddresses();
 
// Double the head and tail nodes' values
list[0] *= 2; // head
list[list.Length - 1] *= 2; // tail
Pushing and Inserting

Previously, we could only push a single node to the beginning or end of the list. This isn't very efficient as it involves a lot of pointer rearrangement to loop the pushed node into the list. Now, we can push whole lists to the beginning or end of the list and only hook up the pointers one time:

// Make some lists
NativeLinkedList<int> listA = new NativeLinkedList<int>(4, Allocator.Temp);
listA.PushBack(10);
listA.PushBack(20);
NativeLinkedList<int> listB = new NativeLinkedList<int>(4, Allocator.Temp);
listB.PushBack(30);
listB.PushBack(40);
listB.PushBack(50);
 
// Push listB to the end of listA and get an enumerator to the node where
// listB's head was pushed
NativeLinkedList<int>.Enumerator pushedHead = listA.PushBack(listB);
Debug.Log(pushedHead.Prev.Value); // 20
Debug.Log(pushedHead.Value); // 30
Debug.Log(pushedHead.Next.Value); // 40

We also now have the ability to insert single values or whole lists before or after a node. All we need is an enumerator to use as the reference point and the value or values to insert:

// Create a list
NativeLinkedList<int> list = new NativeLinkedList<int>(4, Allocator.Temp);
list.PushBack(10);
NativeLinkedList<int>.Enumerator e20 = list.PushBack(20);
list.PushBack(40);
 
// Push a value into the middle of it
list.InsertAfter(e20, 30);
 
// The list is now: 10 <-> 20 <-> 30 <-> 40

Finally, we can now create a list that's not empty. Instead, it'll have as many nodes as we want and all of them will have their default values. This is much faster than calling PushBack over and over, each time doing the work of hooking up pointers. Instead, we use UnsafeUtility.MemClear to wipe all the node values to zero and simply set all the nodes' next and previous pointers to the next and previous element of the list in cache-friendly linear memory traversals.

// Create a list with capacity for 10 nodes and 5 actual nodes with default values
NativeLinkedList<int> list = new NativeLinkedList<int>(10, 5, Allocator.Temp);
 
// The list is now this: 0 <-> 0 <-> 0 <-> 0 <-> 0
Miscellany

A couple of minor changes were made along the way. Count is now Length to conform to the naming convention set by NativeList<T> and NativeHashMap<T> from the Unity.Collections package. This moves away from the naming convention used by .NET collections such as List<T> and Dictionary<TKey, TValue>, but there were no interfaces requiring a Count property so it is easy dropped and the new Length property just as easily understood since it matches with managed arrays and Unity's native containers.

The list's nodes can now also be copied to a managed array or NativeArray<T> in reverse:

// Create a list
NativeLinkedList<int> list = new NativeLinkedList<int>(4, Allocator.Temp);
list.PushBack(10);
list.PushBack(20);
list.PushBack(20);
 
// Copy it to a managed array
int[] array = new int[list.Length];
list.ToArrayReverse(array);
// array is now: [ 30, 20, 10 ]
 
// Copy it to a manged array
NativeArray<int> nativeArray = new NativeArray<int>(list.Length, Allocator.Temp);
list.CopyToNativeArrayReverse(nativeArray);
// nativeArray is now: [ 30, 20, 10 ]

For a bit of house-keeping, the project's directories, assembly definition files, and namespaces were updated to include a JacksonDunstan prefix to them. The name NativeCollections is quite generic and it was likely that there would have been a naming collision at some point with another native collection library.

Finally, in addition to the now 91 unit tests, some basic performance tests have been added. So far they only compare the speed at which NativeArray<T>, NativeList<T>, and NativeLinkedList<T> can be iterated over by Single and ParallelFor jobs. The NativeLinkedList<T> was accessed via its indexer rather than following each node's next pointer. The preliminary results on a 2016 MacBook Pro are essentially the same regardless of which collection is used. This makes sense since the functionality these tests are using is implemented very similarly for all three collection types. It's a good sign for NativeLinkedList<T> that it can compete with NativeArray<T>!

Conclusion

With these changes we have a much more usable NativeLinkedList<T> type. It has most of what's needed by most programmers from a linked list implementation, so it should be usable now. Check out the GitHub project if you want to read through the source code or try it out for yourself.

Continue to part three.