LinearUpscale2DArrayInPlace in Unity Jobs

Question

Well,

I have this function which is called in the Unity Job system, I'm profiling it:

The code:

    public static void LinearUpscale2DArrayInPlace(NativeArray<double> array, int width, int height, int anchorStepX, int anchorStepY, int min = 0, int max = 0)
    {
        // Interpolate columns where the anchor points are
        var lastYCell = height - anchorStepY;
        for (var y = min; y < lastYCell + max; y += anchorStepY)
        {
            for (var x = min; x < width + max; x += anchorStepX)
            {
                var index0 = To2D1D(y, x, width);
                var index1 = To2D1D(y + anchorStepY, x, width);

                if (!IsInBounds(index0, min, max) || !IsInBounds(index1, min, max))
                    continue;

                var startValue = array[index0];
                var endValue = array[index1];
                var diff = endValue - startValue;

                for (var cellY = 1; cellY < anchorStepY; cellY++)
                {
                    var index2 = To2D1D(y + cellY, x, width);
                    if (!IsInBounds(index2, min, max))
                        continue;
                    array[index2] = startValue + diff * cellY / anchorStepY;
                }
            }
        }

        // Interpolate in rows, each row has values in the anchor columns
        var lastXCell = width - anchorStepX;
        for (var y = min; y < height + max; y++)
        {
            for (var x = min; x < lastXCell + max; x += anchorStepX)
            {
                var index0 = To2D1D(y, x, width);
                var index1 = To2D1D(y, x + anchorStepX, width);

                if (!IsInBounds(index0, min, max) || !IsInBounds(index1, min, max))
                    continue;

                var startValue = array[index0];
                var endValue = array[index1];
                var diff = endValue - startValue;

                for (var cellX = 1; cellX < anchorStepX; cellX++)
                {
                    var index2 = To2D1D(y, x + cellX, width);
                    if (!IsInBounds(index2, min, max))
                        continue;
                    array[index2] = startValue + cellX * diff / anchorStepX;
                }
            }
        }
    }

    public static bool IsInBounds(int v, int min, int max) =>
        v >= min && v < max;

    public static bool IsInBounds(int v, int length) =>
        v >= 0 && v < length;

    public static int To2D1D(int x, int y, int width) =>
        x + y * width;

I'm unsure what can I do to improve those methods. Can someone guide me?

Answer 1

Yay, a performance question that comes with profiler measurements! Excellent.

function call overhead

Thank you for those three tiny helper functions, they do a good job of explaining what's going on.

However, maybe we'd like to inline them? I mean, with your current optimization flags, maybe the compiler cannot "see through" the function call boundary, so it's having a tough time proving some very basic arithmetic facts?

Which leads us to...

1-D versus 2-D

Passing in a one-dimensional array seems like a pretty inconvenient way of representing your higher level business concepts. Couldn't we cast it to a two-dimensional array? I'd even be willing to suffer the cost of a single big memcpy()if it meant the compiler could easily see that (x, y) remain within bounds.

I know / division isn't quite as expensive as it used to be on earlier CPUs. But still, that cellY / anchorStepY expression to recover a y-coordinate seems inconvenient. I'm sad that in that loop we don't have row number already available for use. (Or perhaps you've arranged for anchorStepY to be a power-of-two, leading to simple bit shifting.)

in-bounds by construction

                if (!IsInBounds(index0, min, max) || ... )
                    continue;

Does this even trigger, does it ever report out-of-bounds? The y < lastYCell + max and x < width + max guards seem like they're already performing the same work, no? If that predicate does sometimes report false, then consider changing the loop around, not unlike a loop unroll. Maybe you'd like to iterate over slightly fewer cells with no check, and then at the end take care of those remaining cells while carefully checking.

I wonder if a few judicious assert statements would help the compiler to see that indexes are provably within-bounds. Comparing generated object code for very slightly different functions over at https://godbolt.org may prove instructive.

---

This code achieves most of its design goals.

I would be willing to delegate or accept maintenance tasks on it.

Answer 2

The best optimization is to remove computations that aren't required entirely. Since there is a direct mathematical relationship between the loop variables and the index variables it should be possible to remove the bounds check completely by simply adjusting the loop boundaries accordingly.

So let's look at index0 and index1 first.

We know:

1. Both x and y always start at min.
2. index0 = y + x * width and index1 = y + stepY + x*width

What I assume:

1. You never exceed 2^31 for x and y (i.e. no overflow)
2. width >= 1
3. stepY >= 1

From this we can conclude:

1. The bounds check for <= min is pointless since we know that index0 and index1 are by necessity greater than min
2. For any x > max/width both index0 and index1 will be greater than max too and thus be out of bounds.
3. For any y > max - stepY index1 will be greater than max and thus out of bounds
4. For any given value of y if x > max/width - y then index0 will be out of bounds

This means the first two loops can have adjusted boundaries without changing any other logic:

for (var y = min; y <= max - anchorStepY; y += anchorStepY)
{
    for (var x = min; x <= max/width - y; x += anchorStepX)
    {

Given the above - for index2 we know that

1. index2 = y + cellY + x * width with cellY = [1, stepY]
2. We also know that y <= max - stepY which means that max(index2) = max - stepY + stepY + x * width

From this we can conclude that the bounds check is not required and can be removed.

Last but not least:

1. index1 = index0 + stepY - this removes one To2D1D call
2. index2 = index0 + cellY - this removes another To2D1D call

Furthermore you can introduce a loop variable for index0 which gets initialized to y and gets incremented by width on every iteration of x. Something like this:

for (var y = min; y <= max - anchorStepY; y += anchorStepY)
{
    var index0 = y;
    for (var x = min; x <= max/width - y; x += anchorStepX, index0 += width)
    {

Now we have eliminated all calls to To2D1D

Similar logic can be applied to the second loop block.

At this point none of the helper methods are required any longer.