NativeLinkedList<T>: Part 1
Unity 2018.1 shipped with just one true native container: NativeArray<T>
. Now Unity 2018.2 has been released and there is still just the one native container. We’ve seen how to implement more, but never wrote much more than a proof of concept. Today we’ll begin implementing NativeLinkedList<T>
as an example of a native container for a very well known, simple data type. The result is available on GitHub for any project to use.
Many programmers learn about the linked list data structure early on in their training. It’s also a very simple and common data structure. This makes it a great candidate to implement as an example and for practical use. Keep in mind that linked lists often have poor performance due to poor data locality, but we’ll address that issue partly in this article and further in the next article of this series.
The linked list we’ll implement today is a doubly-linked list, meaning each node has a pointer to both the previous node and the next node. Rather than allocating each node individually, which would place each node at an essentially random memory address, we’ll allocate an array of nodes and keep them tightly packed. We’ll use this to our advantage in the next article to dramatically improve data locality and therefore CPU cache usage. So, to begin we have three parallel arrays:
// Each node's data. Indices correspond with nextIndexes. private NativeArray<T> datas; // Each node's next node index. Indices correspond with datas. private NativeArray<int> nextIndexes; // Each node's previous node index. Indices correspond with datas. private NativeArray<int> prevIndexes;
In contrast to using a single array of structs that each contain the data, next index, and previous index, we’re usings the struct of arrays memory layout. Again, this will help us improve performance in the next article when we’re able to iterate over just the node data and not need to fill up our cache lines with useless “next” and “previous” indexes.
Also of note here is that we’re not using true pointers to the previous and next nodes, but instead just indices to those nodes. As int
is always four bytes, we’re using only half the memory that we would be with pointers on a 64-bit (8 byte) platform. We’ve seen that indexing into a NativeArray
is super fast, so there’s no performance downside to this choice.
Next, we’ll need to keep track of the head and tail nodes. That’s as easy as keeping a couple of “pointers” which are, again, just indexes:
// Index of the first node in the list or -1 if there are no nodes in // the list private int headIndex; // Index of the last node in the list or -1 if there are no nodes in // the list private int tailIndex;
Finally, we store the count of nodes:
// Number of nodes contained private int count;
Each of these arrays can be thought of in two parts. The first part ranges from 0
to count-1
and consists of all the nodes currently in the list. The second part ranges from count
to datas.Length
/nextIndexes.Length
/prevIndexes.Length
and consists of all the nodes that aren’t in the list.
When we want to add a node to the list, we first check if we have any available nodes. If not, we double the length of all three arrays just like List<T>
would do. Then we add the node at index count
and adjust the appropriate next and previous pointers to integrate it into the list. Likewise, when we want to remove a node from the list we overwrite it with the last node and adjust the appropriate next and previous pointers. Both operations keep the list’s nodes tightly packed at the front of the arrays. An insert function will be added in a followup article.
To iterate over the array, we have an iterator type:
public struct NativeLinkedListIterator { /// <summary> /// Index of the node /// </summary> internal readonly int Index; }
Notice that the iterator type is public
but its contents are internal
. This allows users of NativeLinkedList<T>
to use the iterator type but not view its contents. This is because the native collections library includes an assembly definition file that places it into its own assembly. The internal
keyword only allows access to functions in the same assembly such as NativeLinkedList<T>
.
It’s also worth noting that this iterator type is usable for any type of NativeLinkedList<T>
, so some caution is necessary. On the plus side, there is only ever one type of iterator so compile times and binary size will be kept down.
Now we can quite trivially implement the usual suite of iterator functions in NativeLinkedList<T>
to allow for iteration both forward and backward:
// Make a list NativeLinkedList<int> list = new NativeLinkedList<int>(3, Allocator.Temp); list.PushBack(10); list.PushBack(20); list.PushBack(30); // Iterate forward doubling each node for ( NativeLinkedListIterator it = list.GetHead(); list.IsValid(it); it = list.GetNext(it)) { list.SetData(it, list.GetData(it) * 2); } // Iterate backward halving each node for ( NativeLinkedListIterator it = list.GetTail(); list.IsValid(it); it = list.GetPrev(it)) { list.SetData(it, list.GetData(it) / 2); } // Dispose the list list.Dispose();
Rounding out the API are a pair of functions to copy the nodes to either a managed array or a NativeArray<T>
. The managed array version should be useful for interoperating with traditional C# APIs such as found in .NET and most of the Unity API. The native version should be useful for making a cache-friendly array for use in C# jobs. Here’s how to use them:
// Allocate a managed array int[] allocated = list.ToArray(); // Fill in a managed array int[] filled = new int[list.Count]; list.ToArray(filled); // Fill in a native array NativeArray<int> native = new NativeArray<int>(list.Count, Allocator.Temp); list.CopyToNativeArray(native);
The GitHub project is now available. To use it, just download or clone it somewhere in your Unity project’s Assets
directory. Unit tests and xml-doc documentation are included to hopefully make it easier to understand. There is a lot of boilerplate and error checking involved, but if you’re familiar with linked lists then it should be rather straightforward to follow along with.