Burst + Generic delegate + Generic interface + FunctionPointer Array + Lambda + Headache

[MonolithBR]

I am working on a Wave Function Collapse Burst Job with the following selling points:

• Values can be any unmanaged IEquatable

• Wave can be any struct to that implements IWave (so, it works for 1D, 2D, 3D, and for 4D+ just need to make a new Wave struct)

• Conditions as generic as can be: Get Wave and position, return changes to be made in that position (eliminate impossible states, change probabilities of states, rescale probabilities so they add to 1). Any number of Conditions.

• And the part that is giving me headaches: Some Condition Templates to which you may pass certain parameters and it returns to you a delegate that can be used in BurstCompiler.CompileFunctionPointer, so you only need to pass your delegates to a MakeCollapseConditions and it gives you a NativeArray of FunctionPointers

It goes as follows:

[BurstDiscard()]
public static CollapseConditionFunc<T, TWave> Count<T, TWave>(Predicate<T> predicate, int2 sizeAndStateCount, uint times = 1)
    where T : unmanaged, IEquatable<T>
    where TWave : IWave<T>
{
    return (TWave a, int index) => Count<T, TWave, IPredicate<T>>(a, index, new BurstPredicate<T>(predicate), sizeAndStateCount, times);
}
[BurstCompile()]
private static NativeArray<State<T>> Count<T, TWave, TPredicate>(TWave a, int index, TPredicate predicate, int2 sizeAndStateCount, uint times)
    where T : unmanaged, IEquatable<T>
    where TWave : IWave<T>
    where TPredicate : IPredicate<T>
{
    // Assume this function body works with Burst
}

That is all inside a Burst static class. As you can see, there is generic delegate, generic interface, and lambda. All stuff that Burst isn’t exactly fond of. Lambda specially.

That is one of the templates, some other templates only work with 2D or 3D Waves specifically (RookConnect, to check if states of neighbooring positions satisfy a Connect() Func, will either only make sense in 2D or 3D, as I cannot implement Neighborhood generically for a N-Dimensional Wave).

Now, I understand that if someone passes a Predicate screws with the code safety, it won’t work. Consider the predicate to be of a function that works with Burst in the first place. (No ref types, has [BurstCompile], etc.)

So, the questions:
1- Is this even possible in the first place? Passing these made-on-the-fly functions to Burst, I mean.
2- Is a lambda of a BurstCompile also Burstable? If not, any other way to do this?
3- What do I actually need to do to make sure what I passing into the Predicate will work with Burst?
4- The bottleneck of the Collapse is on the conditon-checks, I’m pretty sure. Should the whole Collapse be a Job, or should only the conditions be parallel jobs?
5- Anything else I may have grossly overlooked? I cannot even compile the code right now because there are still too many things not done.

[MarcoPersson]

Hello MonolithBR,

Lambdas are not supported in Burst, because they’re compiled into managed classes under the hood by the C# compiler. The following code:

public static void M()
{
    Func<int, int> f = (int x) => x + 1;
}

Gets compiled to the equivalent of:

[Serializable]
[CompilerGenerated]
private sealed class <>c
{
    public static readonly <>c <>9 = new <>c();

    public static Func<int, int> <>9__0_0;

    internal int <M>b__0_0(int x)
    {
        return x + 1;
    }
}

public static void M()
{
    Func<int, int> func = <>c.<>9__0_0 ?? (<>c.<>9__0_0 = new Func<int, int>(<>c.<>9.<M>b__0_0));
}

Where you both have an instance of a managed class <>c and the use of delegate object Func which is also managed.

Another problem is that your lambda here is effectively not a normal function, but a closure. I.e. it captures
(and holds on to) values from its outer scope (predicate, sizeAndStateCount and times in this case). It has to store those values somewhere, and in C# they’re fields of the generated lambda object, which again is a managed object. In Burst, you can use function pointers, but as they are they can only point to functions, and not carry any other data around with them.

If you want to play around with how lambda’s and other C# language constructs are lowered by the C# compiler (to see what Burst sees) then I can recommend checking out https://sharplab.io/.

[MonolithBR]

Seeing how the Lambda function captures the variables in sharplab, it’d be better to just make a struct to hold all the function pointers and captured variables.

I took a deeper look into the FunctionPointer documentation and it seems it doesn’t support passing structs by value, it needs pointers. I also realized making the entire Collapse into a Job is not the way to go, as the clear chokepoint (running every condition for every position in the wave) can be made into a Parallel Batch Job instead, and pass it the NativeArray of FunctionPointers (does this even work? can I actually put FunctionPointers into NativeArrays?).

And now there is a new problem: NativeHashMap<int2, State> as pointer how?

State by the way is a struct with 2 fields ( T value, double probability ) and a bunch of methods and properties (checked sharplab, none of the properties are lowered with underlying fields) , and T is unmanaged, IEquatable.

On a different approach, if each condition is going to be an IJobParallelForBatch anyway, is it possible to pass jobs with some variables already assigned as arguments to a function? That would spare some serious boilerplate, performance issues and unsafeties.

Another thing is I probably need to separate global and local conditions (since global conditions require reading the entire wave, and local conditions require reading only part of the wave (usually a fixed number of elements) for every element, I would like to not read the whole wave for every element. The complexity was already at O(n) when it was just using async, increasing the complexity would undermine the whole purpose of using a Job)

[system]

@MonolithBR

Seeing how the Lambda function captures the variables in sharplab, it’d be better to just make a struct to hold all the function pointers and captured variables.

I took a deeper look into the FunctionPointer documentation and it seems it doesn’t support passing structs by value, it needs pointers. I also realized making the entire Collapse into a Job is not the way to go, as the clear chokepoint (running every condition for every position in the wave) can be made into a Parallel Batch Job instead, and pass it the NativeArray of FunctionPointers (does this even work? can I actually put FunctionPointers into NativeArrays?).

Functions are just the simplest case of an interface. Why not make an interface for your functions, then implement them with structs? You can also make them a tagged union, if the size of the structs do not vary much between the smallest possible function and the largest one.

See this as an example: https://github.com/CareBoo/Burst.Delegates

Also maybe use C# 9 function pointers?

[MonolithBR]

Functions are just the simplest case of an interface. Why not make an interface for your functions, then implement them with structs? You can also make them a tagged union, if the size of the structs do not vary much between the smallest possible function and the largest one.

See this as an example: GitHub - CareBoo/Burst.Delegates: Burst-compatible Delegates

Also maybe use C# 9 function pointers?

So, a condition can have a function defined by whoever decides to use the package, so the maximum diference in size of the smallest possible condition struct and the largest possible condition struct is, well, infinite. Passing a huge function with a ton of parameters shouldn’t prevent the collapse from working, just slow it down a lot. Or so it would be, but I just realized I can precalculate the conditions. So instead of passing a whole function, i just need to pass a NativeHashMap that maps the arguments to bool, which makes it run way faster.

Current approach is making the conditions structs that implement IParallelJobFor and ICondition (ICondition is just 1 method and a property: void Setup(TWave input) and bool Impossible { get; }
And as i have previously stated: I cannot compile the code to test due to the humoungous amount of compiler errors that arise form the implementation being incomplete.

Problem I then ran into: the Conditions are different structs, using an interface or a generic struct to make an array of them results in not being able to .Schedule()

The (probably unsafe) solution: Have ICondition implement DoSchedule() and DoComplete() to Schedule and Complete the Job from a method inside the Job struct that isn’t the Execute() method. I don’t know if this works. Probably doesn’t.

And this also leads into the problem of can i Schedule the same instance of a job again after it has completed or do I have to create a new Instance?

[jasonboukheir]

@MonolithBR

And this also leads into the problem of can i Schedule the same instance of a job again after it has completed or do I have to create a new Instance?

A Job is just a data struct, you should just be able to schedule another one. What exactly is your problem here? Having trouble exactly what you’re trying to accomplish.

[Zuntatos]

I’ve got some absolutely disgusting code for what seems like a related use case; I’m passing managed callbacks to filter some data inside of a burst job.

• a Filter wrapper class that holds an interface instance that does the actual work, it’s kept alive for at least the time the job runs to prevent GC of the wrapper instance
• an internal method on the wrapper class calls the actual work method on said filter instance
• the wrapper class has an internal instance method which is cast to a delegate, a ref to the delegate is stored in the wrapper as well to prevent GC of the delegate instance
• the delegate instance is cast to a functionpointer with Marshal.GetFunctionPointerForDelegate(…), which is then wrapped in a Unity.Burst.FunctionPointer
• this burst functionpointer is passed to the job and used as a delegate

this all seems to work fine; the downside is that (besides the ugly way it’s done) is that the managed callback runs, well, managed. So you’re getting the performance associated with that. But you can also use reference types and such in there, use globals, etc.

It doesn’t allocate any GC beyond the initial wrapper allocation which can be reused, and you can do basically anything you want in the managed callback.

[MonolithBR]

@jasonboukheir

A Job is just a data struct, you should just be able to schedule another one. What exactly is your problem here? Having trouble exactly what you’re trying to accomplish.

I see. A question: I have a struct which implements IParallelJob, and a method called DoSchedule(). Can I use DoSchedule to schedule the Job the struct represents, or do I have to call Schedule() directly?

Also, I am quite shaky with how Native Container works, so another question (cause google did not give me answers, and I’m still in the cannot-compile situation.) Does the operator = with NativeArray just copy the pointer or does it actually behave as a value-type and copy every value?

Thanks for all the help, btw.

[MonolithBR]

@Zuntatos

this all seems to work fine; the downside is that (besides the ugly way it’s done) is that the managed callback runs, well, managed. So you’re getting the performance associated with that. But you can also use reference types and such in there, use globals, etc.

My trashy workaround the generic-delegates-in-burst problem was to, well, cache every possible argument combination and respective output in the constructor.
I literally created a NativeHashMap of ValueTuple to bool for every argument that would be passed into the delegate. “Since I can expect every combinantion passed multiple times throughout the job, might as well cache all of them right off the bat.” was my reasoning.
My frames are happy, because it means the complexity of the conditions with respect to the passed delegate is O(1), in that the delegate doesn’t actually matter after the cache is made.
My RAM is not. If I have N states, Connect’s NativeHashMap will take N^2 bytes of memory in the values alone. Then another N^2*constant for the keys. Plus NHM’s overhead.

[MonolithBR]

And now I can finally compile. And now my dumb decision of having made things outside the Jobs with native arrays has come back to bite me as native arrays, much like C arrays, will promptly deallocate upon leaving their scope. So returning a NativeArray (or any NativeContainer for that matter) from a normal function is the same as returning an unitialized pointer. So my idea of using a function to generate a cache of the function as a NativeHashMap to then pass said NativeHashMap into the Job needs some tweaking.

Also: a little problem I ran into: Why the C is burst complaining about a == operator?
Here’s the code:

public void Execute(int index)
{
    // Determine borders (1 - not border, 0 - border)
    key.x = index % columnCount;
    key.y = index / columnCount;
    left = key.x != 0;
    right = key.x != columnCount - 1;
    down = key.y != 0;
    up = key.y != columnCount - 1;
    near.FromBools(right, left, up, down);
    // If state, for any neighboor, cannot connect to neighboor's superposition, set state Impossible.
    _change = new NativeArray<State<T>>(stateCount, Allocator.Temp);
    for (stateIndex = 0; stateIndex < stateCount; stateIndex++)
    {
        state = wave[key, stateIndex];
        _change[stateIndex] = new State<T>(state.value, -1);
        if (state.Impossible) continue;
        for (d = 1; d <= 128; d <<= 1)
        {
            if ((near & (Direction)d) != 0)
            {
                offset = key + ((Direction)d).AsInt2();
                for (otherStateIndex = 0; otherStateIndex < stateCount; otherStateIndex++)
                {
                    otherState = wave[offset, otherStateIndex];
                    if (otherState.Impossible) continue;
                    if ((conditionant[(state.value, otherState.value)] & d) == 0) // <--- Burst TraceStack points here.
                    {
                        _change[stateIndex] *= 0;
                        break;
                    }
                }
            }
            else
            {
                if ((conditionant[(state.value, null)] & d) == 0)
                    _change[stateIndex] *= 0;
            }
            if (_change[stateIndex].probability == 0)
                break;
        }
    }

    for (int i = 0; i < _change.Length; i++)
        if (_change[i].probability == 0)
        {
            changeWriter.Add(index, _change[i]);
        }
}

And yes, this is still that same Wave Function Collapse project.
conditionant is a NativeHashMap<(int, int?), byte>

[DreamingImLatios]

@MonolithBR

And now my dumb decision of having made things outside the Jobs with native arrays has come back to bite me as native arrays, much like C arrays, will promptly deallocate upon leaving their scope. So returning a NativeArray (or any NativeContainer for that matter) from a normal function is the same as returning an unitialized pointer.

Not true. There is likely something else at play here.

@MonolithBR

Why the C is burst complaining about a == operator?

What is the error?

[sinaari]

@MonolithBR

… native arrays … will promptly deallocate upon leaving their scope. So returning a NativeArray (or any NativeContainer for that matter) from a normal function is the same as returning an unitialized pointer.

That is no surprise since you’re using Allocator.Temp for it, and that its intended behavior.
You need to manually manage the arrays, so create them beforehand using Allocator.Persistent, and .Dispose() them later when you’re done.

@MonolithBR

Also: a little problem I ran into: Why the C is burst complaining about a == operator?

And what is the error?

[sinaari]

@jasonboukheir

A Job is just a data struct, you should just be able to schedule another one. What exactly is your problem here? Having trouble exactly what you’re trying to accomplish.

In search for answers to questions that are much similar to the OP, I came across your library that can be a part of the solution to the problem: https://github.com/CareBoo/Burst.Delegates
It looks quite interesting, but would you please explain, why was the project archived?
Are there any issues with it, or does it still work as intended?

[jasonboukheir]

@sinaari

In search for answers to questions that are much similar to the OP, I came across your library that can be a part of the solution to the problem: https://github.com/CareBoo/Burst.Delegates
It look quite interesting, but would you please explain, why was the project archived?
Are there any issues with it, or does it still work as intended?

I archived it because I thought it wasn’t all that useful. It was originally intended to pair well with https:///github.com/CareBoo/Blinq, which used recursive generic types to make fully stack allocated, lazy, burst-compatible, linq statements. However, it turns out, that recursive generic types make compilers and IDEs mad (looking at you IL2CPP). Also the generic types end up spreading everywhere, and the hassle it saves I felt wasn’t worth it.

If you look in the exp branch, I started working on adding a PartialInvoke with basic value closure support. That was kind of cool. I might pick it up again if I start seeing more interest.

[sinaari]

@jasonboukheir

I archived it because I thought it wasn’t all that useful. It was originally intended to pair well with https:///github.com/CareBoo/Blinq, which used recursive generic types to make fully stack allocated, lazy, burst-compatible, linq statements. However, it turns out, that recursive generic types make compilers and IDEs mad (looking at you IL2CPP). Also the generic types end up spreading everywhere, and the hassle it saves I felt wasn’t worth it.

If you look in the exp branch, I started working on adding a PartialInvoke with basic value closure support. That was kind of cool. I might pick it up again if I start seeing more interest.

Thank you for the answer!

It’s interesting to know that this idea is reaching the limites of the abilitiy of the compiler. I’ve encountered such stuff before in other technologies, so I know what you mean.

And generics can be quite contagious, that’s true. I wonder if it’s actually possible to contain their spread in the user code if the user only writes some LINQ-like statements with lambdas, and doesn’t actually let anything propagate into the rest of the user types. But I’m just starting to experiment with Burst-compiled code, so I don’t really know much about how it all works in a real project. We’ll see . I might try out the Blinq and Burst.Delegates libs when I get to some more exploration.

[jasonboukheir]

@sinaari

I might try out the Blinq and Burst.Delegates libs when I get to some more exploration.

By the way, if you’re looking at trying Blinq, I’d recommend instead to try this out: https://github.com/cathei/LinqGen.

It uses source generators to generate the method, overcoming a lot of the limitations to using nested, recursive generics. It was something I was thinking about doing after Blinq, but haven’t had the motivation or time to invest. Very happy to see it being done in that project!

[sinaari]

@jasonboukheir

By the way, if you’re looking at trying Blinq, I’d recommend instead to try this out: https://github.com/cathei/LinqGen.

It uses source generators to generate the method, overcoming a lot of the limitations to using nested, recursive generics. It was something I was thinking about doing after Blinq, but haven’t had the motivation or time to invest. Very happy to see it being done in that project!

Oh yeah, looks interesting! Thanks, I’ll try that out too!