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,
where T : struct
{
int destIndex = 0;
for (int i = 0; !isDone(i); ++i)
{
if (predicate(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;
[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;
[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
{
[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:
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;
[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:
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);
}```

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))
{
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>
{
[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:
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.