There are many common algorithms that we use constantly: searching, filtering, mapping, and so forth. Today we’ll write a few in the Burst-friendly way as examples of how to write Burst-friendly code that’s still reusable and efficient.

Overview

All of today’s algorithms are very easy to write and common to use. They’re patterned after the Burst-friendly generic algorithm style explored in depth in this article, but without the complication of the jobs system. They’re generic enough to swap in different types, but not so super generic that they allow any kind of collection. These should serve as examples for how to write this style of generic algorithm, not form the bedrock of a generic algorithm library on which a game is built.

With that in mind, let’s start looking at the algorithms…

IndexOf

First up, let’s write an algorithm that finds the index of an element in a NativeArray<T>:

public static class Algorithms
{
    public static int IndexOf<T>(this NativeArray<T> array, in T item)
        where T : struct, IEquatable<T>
    {
        for (int i = 0; i < array.Length; ++i)
        {
            if (array[i].Equals(item))
            {
                return i;
            }
        }
        return -1;
    }
}

Even with such a simple algorithm, there are a few things to note here. First, this is an extension method because it’s static and its first parameter is prefixed with this. This makes it appear as though NativeArray<T> had an IndexOf method built right into it, but it doesn’t because this method is actually declared here and only has access to the public API.

Second, the elements of type T might actually be large and expensive to copy types. We simply don’t know when we’re writing this function whether T is an int or a ReallyBigStruct. To be safe, we take the item to search for as an in parameter. This means a pointer is passed to it rather than a copy and IndexOf isn’t allowed to modify the T it points to.

Lastly, we insist that T implements IEquatable<T>. This means that T must have a bool Equals(T) method. All primitives have this and it’s easy to add to any custom struct types. Many already have it.

Now let’s go ahead and use this algorithm:

void UseIndexOf()
{
    NativeArray<int> array = new NativeArray<int>(3, Allocator.Temp);
    array[0] = 10;
    array[1] = 10;
    array[2] = 20;
 
    Debug.Log(array.IndexOf(10)); // 0
    Debug.Log(array.IndexOf(30)); // -1
}

Here we see that we can call array.IndexOf(10) instead of Algorithms.IndexOf(array, 10) because IndexOf is an extension method. We can use the latter form, but the former is more compact and allows some tricks that we’ll see later on.

It’s worth noting that there’s no call to array.Dispose. That’s because there’s no need to do this.

Filter

Now let’s make an algorithm that filters the elements of an input array into an output array. All the elements that pass a test are written to the output array. All the elements that don’t pass the test are simply skipped.

public static class Algorithms
{
    public interface IFilterPredicate<T>
        where T : struct
    {
        bool Check(in T item);
    }
 
    public static NativeArray<T> Filter<T, TFilterPredicate>(
        this NativeArray<T> input,
        NativeArray<T> output,
        in TFilterPredicate predicate,
        out int numFiltered)
        where T : struct
        where TFilterPredicate : IFilterPredicate<T>
    {
        int destIndex = 0;
        for (int i = 0; i < input.Length; ++i)
        {
            T cur = input[i];
            if (predicate.Check(cur))
            {
                output[destIndex] = cur;
                destIndex++;
            }
        }
        numFiltered = destIndex;
        return output;
    }
}

The core of the algorithm is very simple, but the surrounding structure is more complex. Let’s take it one bit at a time.

First, we define the IFilterPredicate<T> interface as a way of requiring a bool Check(in T) function. We can’t use the more standard .NET Predicate<T> type because it’s a delegate and delegates aren’t allowed in Burst-compiled code. This interface, on the other hand, can be implemented by any struct and that’s OK in Burst-compiled code.

Second, we define Filter with both T and TFilterPredicate type parameters. Filter actually takes a TFilterPredicate rather than an IFilterPredicate<T>. With just that, the TFilterPredicate would be useless to us, so we add the where TFilterPredicate : IFilterPredicate<T> generic constraint to ensure that TFilterPredicate can be used like any IFilterPredicate<T>.

This combination of type parameter and interface is the trick that makes the code acceptable to Burst. Just taking an IFilterPredicate<T> wouldn’t tell Burst what type is being passed since that could be decided at runtime. On the contrary, TFilterPredicate must be known at compile time and Burst therefore knows which bool Check(in T) function to call.

Third, we output the number of NativeArray<T> elements that passed through the filter in an out parameter. We could tell the caller this number using a return value, but we’re using the return value to return the output array instead. This allows a neat trick we’ll see later on.

Now let’s try out this algorithm:

struct EvenPredicate : Algorithms.IFilterPredicate<int>
{
    public bool Check(in int item)
    {
        return (item & 1) == 0;
    }
}
 
void UseFilter()
{
    NativeArray<int> input = new NativeArray<int>(3, Allocator.Temp);
    input[0] = 2;
    input[1] = 3;
    input[2] = 4;
    NativeArray<int> output = new NativeArray<int>(3, Allocator.Temp);
 
    int numFiltered;
    input.Filter(output, new EvenPredicate(), out numFiltered);
 
    for (int i = 0; i < numFiltered; ++i)
    {
        Debug.Log(output[i]); // 2, 4
    }
}

First we needed to define EvenPredicate as the code that determines whether array elements pass through the filter or not. Then we can pass an instance of this struct to Filter. Since it has no fields, we just instantiate one whenever we need it as there’s really no cost to doing so and it keeps the number of variables down.

Map

Next up we have Map. This function converts all of the elements of an input array and writes them to an output array. Note that the types of elements in the input array don’t need to be the same types of elements in the output array.

public static class Algorithms
{
    public interface IMapper<TFrom, TTo>
        where TFrom : struct
        where TTo : struct
    {
        TTo Map(in TFrom item);
    }
 
    public static NativeArray<TTo> Map<TFrom, TTo, TMapper>(
        this NativeArray<TFrom> input,
        NativeArray<TTo> output,
        in TMapper mapper)
        where TFrom : struct
        where TTo : struct
        where TMapper : IMapper<TFrom, TTo>
    {
        for (int i = 0; i < input.Length; ++i)
        {
            output[i] = mapper.Map(input[i]);
        }
        return output;
    }
}

Here we’ve created another interface: IMapper<TFrom, TTo> This has the TTo Map(in TFrom) method that does the mapping. In the Map method, we call this and pass elements of the input array in as the parameter, then write the return value to output array.

Here’s how to use Map:

struct SqrtMapper : Algorithms.IMapper<int, float>
{
    public float Map(in int item)
    {
        return math.sqrt(item);
    }
}
 
void UseMap()
{
    NativeArray<int> input = new NativeArray<int>(3, Allocator.Temp);
    input[0] = 2;
    input[1] = 3;
    input[2] = 4;
    NativeArray<float> output = new NativeArray<float>(3, Allocator.Temp);
 
    input.Map(output, new SqrtMapper());
 
    for (int i = 0; i < output.Length; ++i)
    {
        Debug.Log(output[i]); // 1.414214, 1.732051, 2
    }
}

In this example, we’re mapping from int to float by using math.sqrt to take the square root of every element.

Map and Filter

Finally, let’s combine Map with Filter. No new generic algorithms need to be created for this, so we’ll just write code to use the existing functions in Algorithms and the existing SqrtMapper:

struct LessThanPredicate : Algorithms.IFilterPredicate<float>
{
    public float N;
 
    public bool Check(in float item)
    {
        return item < N;
    }
}
 
void UseMapAndFilter()
{
    NativeArray<int> input = new NativeArray<int>(3, Allocator.Temp);
    input[0] = 2;
    input[1] = 3;
    input[2] = 4;
    NativeArray<float> mapped = new NativeArray<float>(3, Allocator.Temp);
    NativeArray<float> filtered = new NativeArray<float>(3, Allocator.Temp);
 
    int numFiltered;
    input
        .Map(mapped, new SqrtMapper())
        .Filter(filtered, new LessThanPredicate { N = 2 }, out numFiltered);
 
    for (int i = 0; i < numFiltered; ++i)
    {
        Debug.Log(mapped[i]);
    }
}

LessThanPredicate puts a twist on IFilterPredicate by including a threshold field: N. When we call Filter, we create a LessThanPredicate and pass in the threshold. When Check is called, this field can be used to determine whether item is less than the threshold.

We also finally see the use of returning NativeArray from the generic algorithm functions and for making them all extensions methods. The combination of these has allowed us to chain together the function calls in what’s usually considered an intuitive fashion:

int numFiltered;
input
    .Map(mapped, new SqrtMapper())
    .Filter(filtered, new LessThanPredicate { N = 2 }, out numFiltered);

If we hadn’t designed the generic functions like this, we would have instead written these calls:

Algorithms.Map(input, mapped, new SqrtMapper());
int numFiltered = Algorithms.Filter(
    mapped,
    filtered,
    new LessThanPredicate { N = 2 });

This style is a little more verbose and the reader needs to scan the text a little to find the verbs Map and Filter to know what’s happening. There’s no one right way, so feel free to design with either style depending on personal tastes.

Conclusion

The combination of type parameters, interfaces, and generic constraints allows us to easily write Burst-compatible generic algorithms. The result is quite readable and easy to use without sacrificing any performance compared to writing the same code manually over and over. So keep your eyes open for repetitive tasks: there just might be an opportunity to reduce code duplication with a generic algorithm!