Can this code be optimised?

Question

I have some image processing code that loops through 2 multi-dimensional byte arrays (of the same size). It takes a value from the source array, performs a calculation on it and then stores the result in another array.

int xSize = ResultImageData.GetLength(0);
int ySize = ResultImageData.GetLength(1);

for (int x = 0; x < xSize; x++)
{                
   for (int y = 0; y < ySize; y++) 
   {                                                
      ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) +
                                    (AlphaImageData[x, y] * OneMinusAlphaValue));
   }
}

The loop currently takes ~11ms, which I assume is mostly due to accessing the byte arrays values as the calculation is pretty simple (2 multiplications and 1 addition).

Is there anything I can do to speed this up? It is a time critical part of my program and this code gets called 80-100 times per second, so any speed gains, however small will make a difference. Also at the moment xSize = 768 and ySize = 576, but this will increase in the future.

Update: Thanks to Guffa (see answer below), the following code saves me 4-5ms per loop. Although it is unsafe code.

int size = ResultImageData.Length;
int counter = 0;
unsafe
{
    fixed (byte* r = ResultImageData, c = CurrentImageData, a = AlphaImageData)
    {
        while (size > 0)
        {
            *(r + counter) = (byte)(*(c + counter) * AlphaValue + 
                                    *(a + counter) * OneMinusAlphaValue);
            counter++;
            size--;
        }
    }
}

Answer 1

These are all independent calculations so if you have a multicore CPU you should be able to gain some benefit by parallelizing the calculation. Note that you'd need to keep the threads around and just hand them work to do since the overhead of thread creation would probably make this slower rather than faster if the threads are recreated each time.

The other thing that may work is farming the work off to the graphics processor. Look at this question for some ideas, for example, using Accelerator.

Answer 2

To get any real speadup for this code you would need to use pointers to access the arrays, that removes all the index calculations and bounds checking.

int size = ResultImageData.Length;
unsafe 
{
   fixed(byte* rp = ResultImageData, cp = CurrentImageData, ap = AlphaImageData) 
   {
      byte* r = rp;
      byte* c = cp;
      byte* a = ap;
      while (size > 0) 
      {
         *r = (byte)(*c * AlphaValue + *a * OneMinusAlphaValue);
         r++;
         c++;
         a++;
         size--;
      }
   }
}

Edit:
Fixed variables can't be changed, so I added code to copy the pointers to new pointers that can be changed.

Answer 3

An option would be to use unsafe code: fixing the array in memory and use pointer operations. I doubt the speed increase will be that dramatic though.

One note: how are you timing? If you are using DateTime then be aware that this class has poor resolution. You should add an outer loop and repeat the operation say ten times -- I bet the result is less than 110ms.

for (int outer = 0; outer < 10; ++outer)
{
    for (int x = 0; x < xSize; x++)
    {                
         for (int y = 0; y < ySize; y++) 
         {                                                
              ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) +
                                             (AlphaImageData[x, y] * OneMinusAlphaValue));
         }
    }
}

Answer 4

Since it appears that each cell in the matrix is calculated entirely independent of the others. You may want to look into having more than one thread handle this. To avoid the cost of creating threads you could have a thread pool.

If the matrix is of sufficient size, it could be a very nice speed gain. On the other hand, if it is too small, it may not help (even hurt). Worth a try though.

An example (pseudo code) could be like this:

void process(int x, int y) {
    ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) +
        (AlphaImageData[x, y] * OneMinusAlphaValue));
}

ThreadPool pool(3); // 3 threads big

int xSize = ResultImageData.GetLength(0);
int ySize = ResultImageData.GetLength(1);

for (int x = 0; x < xSize; x++) {
     for (int y = 0; y < ySize; y++)  {
         pool.schedule(x, y);  // this will add all tasks to the pool's work queue
     }
}

pool.waitTilFinished(); // wait until all scheduled tasks are complete

EDIT: Michael Meadows mentioned in a comment that plinq may be a suitable alternative: http://msdn.microsoft.com/en-us/magazine/cc163329.aspx

Answer 5

I'd recommend running a few empty tests to figure out what your theoretical bounds are. For example, take out the calculation from inside the loop and see how much time is saved. Try replacing the double loop with a single loop that runs the same number of times and see how much time that saves. Then you can be sure you are going down the right path for optimization (the two paths I see are flattening the double loop into a single loop and working with the multiplication [maybe using a lookup table would be faster]).

Answer 6

Just real quick, you can get an optimization by looping in reverse and comparing against 0. Most CPUs have a fast op for comparison to 0.

E.g.

int xSize = ResultImageData.GetLength(0) -1;
int ySize = ResultImageData.GetLength(1) -1; //minor optimization suggested by commenter

for (int x = xSize; x >= 0; --x)
{                
     for (int y = ySize; y >=0; --y) 
     {                                                
          ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) +
                                         (AlphaImageData[x, y] * OneMinusAlphaValue));
     }
}

See http://dotnetperls.com/Content/Decrement-Optimization.aspx

Answer 7

You are probably suffering from Boundschecking. Like Jon Skeet states, a jagged array instead of a multidimensional (that is data[][] instead of data[,]) will be faster, strange as that may seem.

The compiler will optimize

for (int i = 0; i < data.Length; i++) 

by eliminating the per-element range check. But it's some kind of special case, it won't do the same for Getlength().

For the same reason, caching or hoisting the Length property (putting it in a variable like xSize) also used to be a bad thing though I haven't been able to verify that with Framework 3.5

Answer 8

Try swapping the x and y for loops for a more linear memory access pattern and (thus) less cache misses, like so.

int xSize = ResultImageData.GetLength(0);
int ySize = ResultImageData.GetLength(1);

for (int y = 0; y < ySize; y++) 
{
    for (int x = 0; x < xSize; x++)
    {
        ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) +
            (AlphaImageData[x, y] * OneMinusAlphaValue));
    }
}

Answer 9

If you are using LockBits to get at the image buffer, you should loop through y in the outer loop and x in the inner loop as that is how it is stored in memory (by row, not column). I would say that 11ms is pretty darn fast though...

Answer 10

Does the image data have to be stored in a multi-dimensional (rectangular) array? If you use jagged arrays instead, you may well find the JIT has more optimizations available (including removing the bounds checking).

Answer 11

If CurrentImageData and/or AlphaImageData don't change every time you run your code snippet, you could store the product prior to running the code snippet you show and avoid that multiplication in your loops.

Edit: Another thing I just thought of: Sometimes int operations are quicker than byte operations. Offset this with your processor cache utilization (you'll increase the data size considerably and stand a greater risk of a cache miss).

Answer 12

442,368 additions and 884,736 multiplications for the calculation i would think 11ms is actually extremely slow on a modern CPU.

while i don't know much about the specifics of .net i do know high speed calculation is not its strong suit. In the past i've built java apps with similar problems, i've always used C libraries to do the image / audio processing.

coming from a hardware perspective you want to make sure the memory accesses are sequential, that is step through the buffer in the order it exists in memory. you also may need to reorder this such that the compiler takes advantage of available instructions such as SIMD. How to approach this will end up being dependent on your compiler and i can't help on vs.net.

on an embedded DSP i would break out

(AlphaImageData[x, y] * OneMinusAlphaValue) and (CurrentImageData[x, y] * AlphaValue) and use SIMD instructions to calculate buffers, possibly in parallel before performing the addition. perhaps doing small enough chunks to keep the buffers in cache on the cpu.

i believe anything you do will require more direct access to the memory/cpu than .net allows.

Answer 13

You may also want to take a look at the Mono runtime and its Simd extensions. Perhaps some of your calculations can make use of the SSE acceleration as I gather that you basically do vector calculations (I don't know up to which vector size there is acceleration for multiplication but there is for some sizes)

(Blog post announcing Mono.Simd: http://tirania.org/blog/archive/2008/Nov-03.html)

Of course, that wouldn't work on Microsoft .NET but maybe you are interested in some experimentation.

Answer 14

Interestingly, image data is frequently pretty similar, meaning that the calculations are likely very repetitive. Have you explored doing a lookup table for the calculations? So any time 0.8 was multiplied by 128 - value[80,128] which you've precalculated to 102.4, you simply looked that up? You're basically trading memory space for CPU speed, but it could work for you.

Of course, if your image data has too high a resolution (and goes to too significant a digit), this may not be practical.