2
\$\begingroup\$

Well,

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

profile

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?

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ (Or perhaps you've arranged for anchorStepY to be a power-of-two, leading to simple bit shifting) AnchorStep param is power of two, 4, 8, 16... Also, In-bounds is triggered because I'm using Unity IParallelForBatch and the script can be outside of the split array formed by Unity Jobs. Also, I cannot use 2D arrays in Unity Jobs... \$\endgroup\$
    – z3nth10n
    Dec 1, 2023 at 10:44
  • \$\begingroup\$ Ok, so you're working within constraints, I understand. But after unity hands you a 1D array, you could still turn it into 2D, right? Even if it costs a single memcpy() ? Might be worth a benchmark bake-off to see if it's winning. And as far as parallel goes, maybe the cure is worse than the original slowness symptom? Maybe stick to one thread? Or break out the bulk of the work in parallel jobs that are "easy", and leaving a few "hard" cases for the final thread? \$\endgroup\$
    – J_H
    Dec 1, 2023 at 16:34
  • \$\begingroup\$ No... Unity doesn't allow 2D arrays, NativeArrays are 1D only :( In the parallel case, I only want to test parallel jobs. \$\endgroup\$
    – z3nth10n
    Dec 1, 2023 at 20:35
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.