Help optimizing integer math

Question

I need some help optimizing a section of math heavy code. I've done the profiling, and isolated the slow method. The problem is that the lines individually aren't slow, but they're called many many many times, so I need to really pinch microseconds here.

This code is used to convert pixel data after performing an NTSC filtering. I've provided the profiling data next to the lines as a % of total running time, so you can see what needs work. This function overall accounts for about half of my running time (48% self, 53% with children).

// byte[] ntscOutput;
// ushort[] filtered; - the pixels are ushort, because of the texture color depth

int f_i = 0;
int row = 0;
for (int i = 0; i < 269440; i++)                                  // 3.77 %
{
    int joined = (ntscOutput[f_i + 1] << 8) + ntscOutput[f_i];    // 6.6 %
    f_i += 2;                                                     // 1.88 %

    filtered[i] = (ushort)joined;                                 // 2.8 %

    ushort red = (ushort)(joined & 0xf800);                       // }
    ushort green = (ushort)(joined & 0x7e0);                      //  > 2.36 % each
    ushort blue = (ushort)(joined & 0x1f);                        // }

    red = (ushort)((red - (red >> 3)) & 0xf800);                  // }
    green = (ushort)((green - (green >> 3)) & 0x7e0);             //  > 4.24 % each
    blue = (ushort)((blue - (blue >> 3)) & 0x1f);                 // }

    filtered[i + 602] = (ushort)(red | green | blue);             // 5.65 %

    row++;
    if (row > 601)
    {
        row = 0;
        i += 602;
    }
}

I'm open to any method of optimizing. If it's not really possible to improve the actual math operations, maybe something with unsafe code and pointers would work in manipulating the arrays, to prevent so many casts? Maybe changing my array types somehow, or maybe some kind of loop unrolling? I'm confident that it's possible, because the filtering operation itself is a huge C library function with tons of loops and math, and the whole thing totals 1.35% of my running time.

Answer 1

You are asking for micro optimizations, but have you tried macro optimizations first?

269440 is divisible by any 2^n, that means you can easily thread this code to the number of processors you have, and have basically the speed n-tupled.

Just be sure to not declare threads inside this code though.

Micro optimization using the unchecked keyword could probably be achieved in the rgb block, by surrounding everything with unchecked {}, but that probably won't aid much.

The real optimization would be:

For all possible values of joined (ushort) store all resulting values of filtered[i + 602] into an array with the index of each being (ushort)joined, and do not use calculation but get the value directly from the array.

Then skip the rgb part and use as the loop body:

filtered[i] = (ushort)joined;
filtered[i+602] = precalculatedValues[(ushort)joined];

You could that way convert joined to ushort (after removing the bitwise operations).

Answer 2

I'm wondering, since you're looping 269440 times (well, less with the row variable), and there are only 2^16 possibilities to the filtered variable result, have you considered a look-up table? I'm not sure how well a 2^16 long array would sit in C#, but it might be worth a try.