JacksonDunstan.com

Many algorithms get used over and over: searching, sorting, filtering, etc. C# makes these available with LINQ and functions like Array.Sort, but these can’t be compiled by Burst because interfaces and delegates aren’t supported. So how do we implement these generic algorithms to avoid re-writing them over and over? Today we’ll explore one technique to solve this problem. Read on to learn how!

The Normal Way

Say we wanted to create a function that copied all of the elements of a NativeArray that pass a test into another NativeArray. Such a function might be called Filter and would look like this:

public static int Filter<T>(
    NativeArray<T> input,
    NativeArray<T> output,
    Func<T, bool> predicate)
    where T : struct
{
    int destIndex = 0;
    for (int i = 0; i < input.Length; ++i)
    {
        if (predicate(input[i]))
        {
            output[destIndex] = input[i];
            destIndex++;
        }
    }
    return destIndex;
}

Then we’d call this function like so:

// Input is 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
NativeArray<int> input = new NativeArray<int>(10, Allocator.TempJob);
NativeArray<int> output = new NativeArray<int>(10, Allocator.TempJob);
for (int i = 0; i < input.Length; ++i)
{
    input[i] = i;
}
 
// Filter odds
int resultCount = Filter(input, output, val => (val & 1) != 0);
 
// Print results: 1, 3, 5, 7, 9
for (int i = 0; i < resultCount; ++i)
{
    print(output[i]);
}
 
// Cleanup
input.Dispose();
output.Dispose();

If we wanted to remove the restriction that only NativeArray can be filtered so that we can use any type of collection, we could rewrite Filter to look like this:

public static int Filter<T>(
    Func<int, bool> isDone,
    Func<int, bool> predicate,
    Action<int, int> addResult)
    where T : struct
{
    int destIndex = 0;
    for (int i = 0; !isDone(i); ++i)
    {
        if (predicate(i))
        {
            addResult(destIndex, i);
            destIndex++;
        }
    }
    return destIndex;
}

Here’s how to use this version:

// Input is 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
NativeArray<int> input = new NativeArray<int>(10, Allocator.TempJob);
NativeArray<int> output = new NativeArray<int>(10, Allocator.TempJob);
for (int i = 0; i < input.Length; ++i)
{
    input[i] = i;
}
 
// Filter odds
int resultCount = Filter(
    i => i >= input.Length,
    val => (val & 1) != 0,
    (dest, src) => output[dest] = input[src]);
 
// Print results: 1, 3, 5, 7, 9
for (int i = 0; i < resultCount; ++i)
{
    print(output[i]);
}
 
// Cleanup
input.Dispose();
output.Dispose();

The Unsuccessful Way

Let’s try directly porting the first version to a Burst-compiled job:

[BurstCompile]
struct UnsuccessfulFilterArrayJob<T> : IJob
    where T : struct
{
    public Func<T, bool> Predicate;
    [ReadOnly] public NativeArray<T> Input;
    [WriteOnly] public NativeArray<T> Output;
    [WriteOnly] public NativeArray<int> ResultCount;
 
    public void Execute()
    {
        int destIndex = 0;
        for (int i = 0; i < Input.Length; ++i)
        {
            if (Predicate(Input[i]))
            {
                Output[destIndex] = Input[i];
                destIndex++;
            }
        }
        ResultCount[0] = destIndex;
    }
}

All we’ve done here is to make a struct, move the parameters and return value to fields, and rename the function to match the requirements of IJob. Unfortunately, this won’t compile:

/Users/builduser/buildslave/unity/build/Runtime/Jobs/Managed/IJob.cs(29,13): error: The delegate managed type `System.Func`2<System.Int32,System.Boolean>` is not supported by burst
 at Unity.Jobs.IJobExtensions.JobStruct`1<UnsuccessfulFilterArrayJob`1<System.Int32>>.Execute(ref UnsuccessfulFilterArrayJob`1<int> data, System.IntPtr additionalPtr, System.IntPtr bufferRangePatchData, ref Unity.Jobs.LowLevel.Unsafe.JobRanges ranges, int jobIndex) (at /Users/builduser/buildslave/unity/build/Runtime/Jobs/Managed/IJob.cs:29)
 
 
While compiling job: System.Void Unity.Jobs.IJobExtensions/JobStruct`1<UnsuccessfulFilterArrayJob`1<System.Int32>>::Execute(T&,System.IntPtr,System.IntPtr,Unity.Jobs.LowLevel.Unsafe.JobRanges&,System.Int32)

The reason is that we made use of a delegate, which is forbidden by Burst. Any code relying on Action and Func simply won’t compile.

The Unsuccessful Way: Part 2

Let’s try avoiding the use of delegates by turning to an interface implemented by a struct. Structs are certainly allowed by Burst, so there’s reason to believe that this might work:

interface IFilterPredicate<T>
{
    bool Test(in T val);
}
 
struct IsOddFilterPredicate : IFilterPredicate<int>
{
    public bool Test(in int val)
    {
        return (val & 1) != 0;
    }
}
 
[BurstCompile]
struct UnsuccessfulFilterArrayJob2<T> : IJob
    where T : struct
{
    public IFilterPredicate<T> Predicate;
    [ReadOnly] public NativeArray<T> Input;
    [WriteOnly] public NativeArray<T> Output;
    [WriteOnly] public NativeArray<int> ResultCount;
 
    public void Execute()
    {
        int destIndex = 0;
        for (int i = 0; i < Input.Length; ++i)
        {
            if (Predicate.Test(Input[i]))
            {
                Output[destIndex] = Input[i];
                destIndex++;
            }
        }
        ResultCount[0] = destIndex;
    }
}

This too doesn’t compile:

/Users/builduser/buildslave/unity/build/Runtime/Export/NativeArray/NativeArray.cs(141,13): error: Unexpected error while processing function `IFilterPredicate`1<int>.Test(IFilterPredicate`1<int>* this, System.Int32& modreq(System.Runtime.InteropServices.InAttribute) val)`. Reason: Object reference not set to an instance of an object
 at Unity.Collections.NativeArray`1<System.Int32>.get_Item(Unity.Collections.NativeArray`1<int>* this, int index) (at /Users/builduser/buildslave/unity/build/Runtime/Export/NativeArray/NativeArray.cs:138)
 at UnsuccessfulFilterArrayJob2`1<System.Int32>.Execute(UnsuccessfulFilterArrayJob2`1<int>* this) (at /Users/jackson/Code/UnityPlayground/Assets/TestScript.cs:109)
 at Unity.Jobs.IJobExtensions.JobStruct`1<UnsuccessfulFilterArrayJob2`1<System.Int32>>.Execute(ref UnsuccessfulFilterArrayJob2`1<int> data, System.IntPtr additionalPtr, System.IntPtr bufferRangePatchData, ref Unity.Jobs.LowLevel.Unsafe.JobRanges ranges, int jobIndex) (at /Users/builduser/buildslave/unity/build/Runtime/Jobs/Managed/IJob.cs:30)
 
Internal compiler exception: System.NullReferenceException: Object reference not set to an instance of an object
  at Burst.Compiler.IL.Helpers.CecilExtensions.IsDelegate (Mono.Cecil.TypeDefinition typeDef) [0x0002b] in <3179d4839c86430ca331f2949f40ede5>:0 
  at Burst.Compiler.IL.Intrinsics.FunctionPointerProcessor.IsDelegateInvoke (Burst.Compiler.IL.Syntax.ILFunctionReference method) [0x0000b] in <3179d4839c86430ca331f2949f40ede5>:0 
  at Burst.Compiler.IL.Intrinsics.FunctionPointerProcessor.IsHandling (Burst.Compiler.IL.Syntax.ILFunctionReference method) [0x00009] in <3179d4839c86430ca331f2949f40ede5>:0 
  at Burst.Compiler.IL.Syntax.ILBuilder.IsIntrinsicCall (Burst.Compiler.IL.Syntax.ILFunctionReference binding, System.Boolean& dontVisitImpl) [0x00019] in <3179d4839c86430ca331f2949f40ede5>:0 
  at Burst.Compiler.IL.Syntax.ILBuilder.CreateFunctionFromRef (Burst.Compiler.IL.Syntax.ILFunctionReference funcRef) [0x0003d] in <3179d4839c86430ca331f2949f40ede5>:0 
  at Burst.Compiler.IL.Syntax.ILBuilder.VisitPendingFunctionReferences () [0x000c1] in <3179d4839c86430ca331f2949f40ede5>:0 
 
While compiling job: System.Void Unity.Jobs.IJobExtensions/JobStruct`1<UnsuccessfulFilterArrayJob2`1<System.Int32>>::Execute(T&,System.IntPtr,System.IntPtr,Unity.Jobs.LowLevel.Unsafe.JobRanges&,System.Int32)

The proximate cause here is an “internal compiler exception,” but really this is due to our usage of an interface type within the job struct.

The Manual Way

At this point we might give up and simply duplicate the filtering algorithm for every Burst-compiled job that wants to use it. This allows us to remove the delegate or interface at the expense of duplicating the algorithm code everywhere that wants to use it and the associated downsides of difficult code maintenance and readability. Here’s how that would look:

[BurstCompile]
struct ManualFilterOddJob : IJob
{
    [ReadOnly] public NativeArray<int> Input;
    [WriteOnly] public NativeArray<int> Output;
    [WriteOnly] public NativeArray<int> ResultCount;
 
    public void Execute()
    {
        int destIndex = 0;
        for (int i = 0; i < Input.Length; ++i)
        {
            if ((Input[i] & 1) != 0)
            {
                Output[destIndex] = Input[i];
                destIndex++;
            }
        }
        ResultCount[0] = destIndex;
    }
}

Notice that the if no longer relies on a predicate delegate, but instead directly contains the “is odd” check.

Here is the assembly code this compiles to, which we’ll reference later:

        movsxd  rcx, dword ptr [rdi + 8]
        test    rcx, rcx
        jle     .LBB0_1
        mov     rdx, qword ptr [rdi]
        xor     eax, eax
        .p2align        4, 0x90
.LBB0_6:
        mov     esi, dword ptr [rdx]
        test    sil, 1
        je      .LBB0_3
        mov     r8, qword ptr [rdi + 56]
        cdqe
        mov     dword ptr [r8 + 4*rax], esi
        inc     eax
.LBB0_3:
        add     rdx, 4
        dec     rcx
        jne     .LBB0_6
        mov     rcx, qword ptr [rdi + 112]
        mov     dword ptr [rcx], eax
        ret
.LBB0_1:
        xor     eax, eax
        mov     rcx, qword ptr [rdi + 112]
        mov     dword ptr [rcx], eax
        ret

The Generic Way

Thankfully, this is actually unnecessary. It turns out that we can make a reusable algorithm with a little more usage of C# generics. Here’s how:

[BurstCompile]
struct FilterArrayJob<T, TPredicate> : IJob
    where T : struct
    where TPredicate : IFilterPredicate<T>
{
    public TPredicate Predicate;
    [ReadOnly] public NativeArray<T> Input;
    [WriteOnly] public NativeArray<T> Output;
    [WriteOnly] public NativeArray<int> ResultCount;
 
    public void Execute()
    {
        int destIndex = 0;
        for (int i = 0; i < Input.Length; ++i)
        {
            if (Predicate.Test(Input[i]))
            {
                Output[destIndex] = Input[i];
                destIndex++;
            }
        }
        ResultCount[0] = destIndex;
    }
}

The key difference here is that we take two type parameters: the element type T and the predicate type TPredicate. This allows us to explicitly tell Burst what kind of predicate struct we’re using so that everything is known at compile time.

This does compile and is now usable like this:

// Input is 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
NativeArray<int> input = new NativeArray<int>(10, Allocator.TempJob);
NativeArray<int> output = new NativeArray<int>(10, Allocator.TempJob);
NativeArray<int> resultCount = new NativeArray<int>(1, Allocator.TempJob);
for (int i = 0; i < input.Length; ++i)
{
    input[i] = i;
}
 
// Filter odds
new FilterArrayJob<int, IsOddFilterPredicate>
{
    Predicate = new IsOddFilterPredicate(),
    Input = input,
    Output = output,
    ResultCount = resultCount
}.Run();
 
// Print results: 1, 3, 5, 7, 9
for (int i = 0; i < resultCount[0]; ++i)
{
    print(output[i]);
}
 
// Cleanup
input.Dispose();
output.Dispose();
resultCount.Dispose();

This compiles to almost identical assembly as the manual version. The only difference is an offset of 8 bytes:

        movsxd  rcx, dword ptr [rdi + 16]
        test    rcx, rcx
        jle     .LBB0_1
        mov     rdx, qword ptr [rdi + 8]
        xor     eax, eax
        .p2align        4, 0x90
.LBB0_6:
        mov     esi, dword ptr [rdx]
        test    sil, 1
        je      .LBB0_3
        mov     r8, qword ptr [rdi + 64]
        cdqe
        mov     dword ptr [r8 + 4*rax], esi
        inc     eax
.LBB0_3:
        add     rdx, 4
        dec     rcx
        jne     .LBB0_6
        mov     rcx, qword ptr [rdi + 120]
        mov     dword ptr [rcx], eax
        ret
.LBB0_1:
        xor     eax, eax
        mov     rcx, qword ptr [rdi + 120]
        mov     dword ptr [rcx], eax
        ret

The Really Generic Way

In the beginning, we took another step and abstracted even the NativeArray so we could use other types of collection like NativeChunkedList. Let’s apply the same technique here to see if we can achieve that in Burst-compiled code. First, here’s the new interface:

interface IFilterUser<T>
{
    bool IsDone(int index);
    bool Predicate(int index);
    void AddResult(int destIndex, int srcIndex);
}

Just like before, we’ve abstracted the input and output collections so that the algorithm doesn’t directly manipulate them or even know their types. Instead, it just relies on indexes which are always an int.

Next, here’s the job that uses this interface:

[BurstCompile]
struct FilterJob<T, TUser> : IJob
    where T : struct
    where TUser : IFilterUser<T>
{
    public TUser User;
    [WriteOnly] public NativeArray<int> ResultCount;
 
    public void Execute()
    {
        int destIndex = 0;
        for (int i = 0; !User.IsDone(i); ++i)
        {
            if (User.Predicate(i))
            {
                User.AddResult(destIndex, i);
                destIndex++;
            }
        }
        ResultCount[0] = destIndex;
    }
}

This is also just like before, since all we’ve done is replace the loop condition with a call to IsDone and the output writing with a call to AddResult.

Now let’s see how to create a “user” struct for odd integers:

struct IsOddFilterUser : IFilterUser<int>
{
    [ReadOnly] public NativeArray<int> Input;
    [WriteOnly] public NativeArray<int> Output;
 
    public bool IsDone(int index)
    {
        return index >= Input.Length;
    }
 
    public bool Predicate(int index)
    {
        return (Input[index] & 1) != 0;
    }
 
    public void AddResult(int destIndex, int srcIndex)
    {
        Output[destIndex] = Input[srcIndex];
    }
}

And here’s how to put them together to run a job that filters odd integers:

// Input is 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
NativeArray<int> input = new NativeArray<int>(10, Allocator.TempJob);
NativeArray<int> output = new NativeArray<int>(10, Allocator.TempJob);
NativeArray<int> resultCount = new NativeArray<int>(1, Allocator.TempJob);
for (int i = 0; i < input.Length; ++i)
{
    input[i] = i;
}
 
// Filter odds
new FilterJob<int, IsOddFilterUser>
{
    User = new IsOddFilterUser
    {
        Input = input,
        Output = output
    },
    ResultCount = resultCount
}.Run();
 
// Print results: 1, 3, 5, 7, 9
for (int i = 0; i < resultCount[0]; ++i)
{
    print(output[i]);
}
 
// Cleanup
input.Dispose();
output.Dispose();
resultCount.Dispose();

Finally, let’s take a look at the assembly Burst compiled this to:

        movsxd  rcx, dword ptr [rdi + 8]
        test    rcx, rcx
        jle     .LBB0_1
        mov     rdx, qword ptr [rdi]
        xor     eax, eax
        .p2align        4, 0x90
.LBB0_6:
        mov     esi, dword ptr [rdx]
        test    sil, 1
        je      .LBB0_3
        mov     r8, qword ptr [rdi + 56]
        cdqe
        mov     dword ptr [r8 + 4*rax], esi
        inc     eax
.LBB0_3:
        add     rdx, 4
        dec     rcx
        jne     .LBB0_6
        mov     rcx, qword ptr [rdi + 112]
        mov     dword ptr [rcx], eax
        ret
.LBB0_1:
        xor     eax, eax
        mov     rcx, qword ptr [rdi + 112]
        mov     dword ptr [rcx], eax
        ret

Amazingly, this is the exact same assembly as the manual version!

Conclusion

Not only is it possible to write generic algorithms in Burst-compiled code, but all of this abstraction ends up being totally free from a performance perspective. It’s not quite as friendly as using lambdas, but readability and code reuse are much improved over manually copying the algorithm into every job type.

#1 by DreamingImLatios on September 30th, 2019 · Reply

Did you find a way to make generics work for builds? The Unity Editor runs Burst in a JIT context but at build there is no such luxury.

#2 by jackson on September 30th, 2019 · Reply

The generics-based jobs worked for me in both the editor and in a standalone macOS build using 2019.2.6f1.

#3 by Renan on November 11th, 2019 · Reply

I’ve been doing copy/past all over the code base. I’ll definitely try this out!

Thanks!

#4 by Frank on May 28th, 2020 · Reply

Just wondering this there is a way I can be sure my jobs were bursted in editor and build.

#5 by jackson on June 2nd, 2020 · Reply

You could look at the IL2CPP output, similar to what’s shown in this article.

Burst-Compiled Generic Algorithms