# Detect optimized

I've been trying to optimize this piece of code:

void detect_optimized(int width, int height, int threshold)
{
int x, y, z;
int tmp;

for (y = 1; y < width-1; y++)
for (x = 1; x < height-1; x++)
for (z = 0; z < 3; z++)
{
if (tmp>255)
tmp = 255;
if (tmp<threshold)
tmp = 0;
c[x][y][z] = 255-tmp;
}
return;
}


So far I've tried "Blocking" and a few other things, but I can't seem to get it to run any faster.

Blocking resulted in:

  for(yy = 1; yy<height-1; yy+=4){
for(xx = 1; xx<width -1; xx+=4){
for (y = yy; y < 4+yy; y++){
for (x = xx; x < 4+xx; x++){
for (z = 0; z < 3; z++)
{
if (tmp>255)
tmp = 255;
if (tmp<threshold)
tmp = 0;
c[x][y][z] = 255-tmp;
}}}}}


Which ran at the same speed as the original program.

Any suggestions would be great.

mask_function cannot be changed, but here is its code:

int mask_product(int m[3][3], byte bitmap[MAX_ROW][MAX_COL][NUM_COLORS], int x, int y, int z)
{
int tmp[9];
int i, sum;

// ADDED THIS LINE (sum = 0) TO FIX THE BUG
sum = 0;

tmp[0] = m[0][0]*bitmap[x-1][y-1][z];
tmp[1] = m[1][0]*bitmap[x][y-1][z];
tmp[2] = m[2][0]*bitmap[x+1][y-1][z];
tmp[3] = m[0][1]*bitmap[x-1][y][z];
tmp[4] = m[1][1]*bitmap[x][y][z];
tmp[5] = m[2][1]*bitmap[x+1][y][z];
tmp[6] = m[0][2]*bitmap[x-1][y+1][z];
tmp[7] = m[1][2]*bitmap[x][y+1][z];
tmp[8] = m[2][2]*bitmap[x+1][y+1][z];
for (i=0; i<9; i++)
sum = sum + tmp[i];
return sum;
}

-
The indentation after tmp = 255; indicates that you want that if to be wrapped into the other one's body. Is that correct? If so, then you are missing parenthesis. If not, then the indentation should be fixed. –  Nobody Apr 18 at 18:51
Is mask_product some standard function that you may not change? If not then please provide its code as well. –  Nobody Apr 18 at 18:53
The format must have changed when I copied it. Fixed it. –  user3311482 Apr 18 at 18:53
Did you try optimized compilation? Most of the advisable optimizations can be done automatically by the compiler so you can concentrate on getting the code right (instead of obfuscating it with "optimizations"). –  Nobody Apr 18 at 19:32
What are mask and a? Does your function compile? –  200_success May 12 at 9:48

Do not expect much:

void detect_optimized(int width, int height, int threshold)
{
int x, y, z;
int tmp;
int widthM1= width-1;
int heightM1=height-1;

for (y = 1; y < widthM1; y++){
for (x = 1; x < heightM1; x++){
for (z = 0; z < 3; z++){
if (tmp>255)
c[x][y][z] = 0;
else if (tmp<threshold)
c[x][y][z] = 255;
else
c[x][y][z] = 255 ^ tmp;  // in this case xor is the same as -
}
}
}
return;
}


You can also unroll the z- loop, by copying the inner body 2 more times.

If you can manage to change the mask_function:

int mask_product(int m[3][3], byte bitmap[MAX_ROW][MAX_COL][NUM_COLORS], int x, int y, int z)
{
int xp1=x+1;
int xm1=x-1;
int yp1=y+1;
int ym1=y-1;
return  m[0][0]*bitmap[xm1][ym1][z];
+ m[1][0]*bitmap[x][ym1][z];
+ m[2][0]*bitmap[xp1][ym1][z];
+ m[0][1]*bitmap[xm1][y][z];
+ m[1][1]*bitmap[x][y][z];
+ m[2][1]*bitmap[xp1][y][z];
+ m[0][2]*bitmap[xm1][yp1][z];
+ m[1][2]*bitmap[x][yp1][z];
+ m[2][2]*bitmap[xp1][yp1][z];
}


Also have a look if you can make your compiler inline the mask_product method.

-
Wont an optimization flag help with the unroll? Also, BTW, you should discover the 2nd Monitor - Code Review chat room. –  rolfl Apr 23 at 14:26
@rolfl: In this simple case it might be possible that the compiler can unroll the inner loop, but I would not count on it. –  MrSmith42 Apr 23 at 15:02

I am afraid I can't do much about the performance but here are some other tips:

• The z loop bound is not checked against NUM_COLORS (which I believe is the size of the array for this index).
• z should be renamed to something like colorIndex.
• Using prefix increments (++x) might give a speedup
• Precalculating loop bounds to avoid repeated recalculation might give another speedup: maxY = width - 1; and then for (y = 1; y < maxY; ++y)

• tmp should have a better name (what does it actually contain/represent?)

• place the ifs into an own function (or macro) clamp (which is a widely used name and maybe has a standard implementation) and use it to make the code cleaner: tmp = clamp(tmp, 0, 255);

• do not use global variables instead of function parameters, they introduce hard to debug side effects

• Although you cannot change the mask function I would recommend avoiding the tmp array and instead directly summing up into sum.

You could gain some speedup by replacing the inner loop over the colors by MMX functionality which allows to do the same calculation on all colors at once. However, I am no expert in this and it likely requires inline assembly.

-

Your compiler may already optimize this but it might still be interesting to know.

Everytime you do this:

c[x][y][z]


What actually happens is this:

*(*(*(a+x)+y)+z)


And since x, y and z change at different rates, you can avoid unnecessary arithmetic by caching the intermediate pointers.

for (x = 1; x < height-1; x++) {

int *xx = *(c+x);
for (y = 1; y < width-1; y++) {

/* 3 is the length of z. Think about the memory layout of a
* multidimensional array to understand why. */
int *yy = (xx+(y*3));
for (z = 0; z < 3; z++) {
...
*(yy+(z) = 255-tmp;
}
}
}


As is usually the case with optimization, it's down to you to benchmark the code and decide whether to performance increase is worth to reduced readability and maintainability.

Another optimization that has not been mentioned is switching the order of the loops. Take this loop for example.

for (int x = 0; x < 100; x++) {
for (int y = 0; y < 5; y++) {
...
}
}


The inner loop executes 100*5=500 times and the outer loop executes 100 times making a total of 600 comparisons. If the order were switched so the busiest loop was on the inside:

for (int y = 0; y < 5; y++) {
for (int x = 0; x < 100; x++) {
...
}
}


The inner loop still executes 5*100=500 times however the outer loop only executes 5 times making a total of 505 comparisons. That's 16% fewer comparison operations in this example.

-