NativeLinkedList<T>: Part 2
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 likeIJob
- In a
ParallelFor
C# job likeIJobParallelFor
where the chunk of the list thatExecute(int index)
is being called on encompasses the entire list - In a
ParallelFor
C# job likeIJobParallelFor
where the chunk of the list thatExecute(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.