Enumerables Without the Garbage: Part 8
NativeArray<T> is great, but very limited in functionality. We can fix this surprisingly easily! Today we revive a two year old series that created the iterator project. Iterators are like a no-GC version of
IEnumerable<T> and LINQ which have a lot of power but only support managed arrays (
List<T>. Today we’ll add support for
NativeArray<T> and inherit support for the same functionality. We’ll also spruce up the project with proper unit tests, assembly definitions, and runtime tests to confirm that zero garbage is created. Read on to see how this was done and how to use iterators with
When we left off two years ago, we had a more-or-less complete implementation of C++’s
<algorithm> (like LINQ) header files. This provided the
ListIterator<T> types for managed arrays (
List<T>. These types were each accompanied by a huge array of functionality from basics like getting and advancing iterators to advanced functions like random shuffling and sorting. All of this lived in the global namespace and was in one
Iterator.cs file at the root level of the project.
This functionality was accompanied by a
MonoBehaviour that ran two tests. The first test used all the functions in the library in a
GcTest function so that Unity’s profiler could be used to determine whether any GC allocations occur in the library. The second test also used all the functions in the library, but printed a sort of report that could be eyeballed to confirm the correctness of the library.
There’s a lot of room for improvement, so let’s get to that.
The motivation behind today’s upgrades is support for
NativeArray<T>. Supporting this is really quite easy since it behaves almost exactly like a managed array (
T). All that’s necessary is to copy and paste all the code for
Iterator<T>, rename to
NativeArrayIterator<T>, search-and-replace all instances of
NativeArray<T>, and add
where T : struct clauses.
While we’re at it, let’s rename
ArrayIterator<T> for consistency with
NativeArrayIterator<T>. Then let’s split the gigantic
Iterator.cs file into three parts:
To allow for the whole repo to be simply copied into non-Unity projects and Unity projects before 2018.1, the whole
NativeArrayIterator.cs file is wrapped in a
#if UNITY_2018_1_OR_NEWER so that the compiler will remove it when not supported.
Finally, all of this code lived in the global namespace which could cause conflicts with other code using the same names or adding the same extension methods. Fixing this is easy: just wrap everything in a
JacksonDunstanIterator namespace which is unlikely to be used by any other project.
Real Unit Tests
The project included a primitive version of correctness testing where all the functionality was used to print a textual report of results. This could be read by a developer to manually check for correctness. This is far inferior to real unit tests for many reasons. First, it takes a good deal of time to carefully read through the whole report and verify the output. This leads to a lot of time being spent and a reluctance to read the report. Second, it’s easy to make mistakes while reading the report which negates the point of creating one in the first place. Third, a human is required to validate correctness so there’s no way to automate the validation via continuous integration type of system.
To remedy this, the monolithic
Test function has been broken up into individual functions for each bit of functionality. These are all marked with the
[Test] attribute so they become unit tests. Instead of logging a report, asserts are used to check for results. Then this whole file is copied, pasted, and modified with mostly a search-and-replace to produce versions that also test
NativeArrayIterator<T>. At this point the tests can be run via Unity’s
Window > General > Test Runner > EditMode > Run All to quickly and consistently verify the library’s correctness.
In the process, the GC tests have been moved out into their own script which operates just as it did before.
Just as with the NativeCollections project, the
iterator project has been updated to use Unity 2017.3’s assembly definition feature. Here’s how the directory structure looks:
Assets |- JacksonDunstanIterator/ |- JacksonDunstanIterator.asmdef |- ArrayIterator.cs |- ListIterator.cs |- NativeArrayIterator.cs |- JacksonDunstanIteratorTests/ |- JacksonDunstanIteratorTests.asmdef |- ArrayIterator.cs |- ListIterator.cs |- NativeArrayIterator.cs
This splits the library into two parts: runtime and editor tests. The runtime—
JacksonDunstanIterator—contains the library itself and the editor tests—
JacksonDunstanIteratorTests—contains the unit tests. The editor tests have a dependency on the runtime and are marked with
Editor as their only platform. The runtime has no dependencies, supports all platforms, and allows “unsafe” code since this is necessary to implement the equality operator of
This directory structure also allows for
JacksonDunstanIterator to simply be copied into any Unity or non-Unity project. Old versions of Unity and non-Unity projects will simply ignore the assembly definition files.
All three iterator types have the same API, so usage with
NativeArray<T> is just like with managed arrays and
// Get an array NativeArray<int> array = new NativeArray<int>(4, Allocator.Temp); array = 30; array = 10; array = 20; array = 40; // Get an iterator to the beginning of the array NativeArrayIterator<int> begin = array.Begin(); // Get the value of the iterator int val = begin.GetCurrent(); // Move to the next element NativeArrayIterator<int> second = begin.GetNext(); // Get an iterator to one past the end of the array NativeArrayIterator<int> end = array.End(); // Reverse [ 10, 20, 40] so the array is [ 30, 40, 20, 10 ] second.Reverse(end); // Search for an element satisfying a condition // Note: Creating this non-closure lambda delegate creates garbage the first // time it is used. NativeArrayIterator<int> it20 = begin.FindIf(end, e => e < 25);
All of the functionality, regardless of how basic or advanced, is available just as it is for managed arrays and
With these relatively easy changes we now have a lot of additional functionality available to us when working with
NativeArray<T>. We can sort, reverse, find, shuffle, permute, compare, replace, rotate, transform, and perform all kinds of other operations. We also get a proper namespace, assembly definitions, and unit tests as project upgrades. If you’re interested in using the project or just seeing how it’s built, check out the GitHub repo.
#1 by Bartek on September 6th, 2018 ·
Wow, I ve just found your blog, so many cool posts. You should really advertise it more! Keep up great work!
#2 by Mirko on March 27th, 2021 ·
hi test are failing for random shuffle for array and list iterator and all tests for native array iterator. i am using 2018.4, can you verify?
#3 by jackson on March 27th, 2021 ·
I verified with 2019.4. Apparently the implementation of
System.Randomchanged so even with a fixed seed the random number sequence differed from the version I wrote the tests with. I just pushed a commit (SHA
77da15219d36138797fec6ba9f0fe0028c47ca54) to implement and use a
MonotonicRandomclass within the unit tests directory so they can rely on a specific sequence of random numbers. The tests now pass.
Thanks for letting me know about the issue!