2
\$\begingroup\$

The problem is that I am trying to modify the code to invert the image in C and optimize it to make it run faster than the original by any method I could think of. After tried to use blocking and loop unrolling, it still does not seem to speed up. Maybe I did it in a wrong way as I'm not really fully understanding these methods.

void invert(int width, int height, char *code)
{
  int x, y, z;
  int i, n;
  char RGB[4]="RGB";

  for (z=0; z<3; z++)
    for (y=0; y<width; y++)
      for (x=0; x<height; x++)
      {
        b[x][y][z] = a[x][y][z];
        n = strlen(code);
        for(i=0; i<n; i++)
        {
          if (code[i]==RGB[z])
          {
            b[x][y][z] = 255 - a[x][y][z];
          }
        }
      }
  return;
}

void invert_optimized(int width, int height, char *code)
{
  int x, y, z , xx , yy;
  int i, n;
  char RGB[4]="RGB";

  for (z=0; z<3; z++)
    for (xx=0; xx<height; xx+=4)
        for (yy=0; yy<width; yy+=4)
        for (x=xx; x<4+xx; x++)
            for (y=yy; y<4+yy; y++)
              {
                c[x][y][0] = a[x][y][0];
                c[x][y][1] = a[x][y][1];
                c[x][y][2] = a[x][y][2];
                n = strlen(code);
                for(i=0; i<n; i++)
                {
                  if (code[i]==RGB[z])
                  {
                    c[x][y][z] = 255 - a[x][y][z];
                  }
                }
              }
  return;
}

I also was thinking about inline, but the problem is that I don't know how to implement it for this code and I don't think it will work for this either.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Could you explain the problem more clearly? What is in the array a? What is in the string code? My best guess is that a is array of size [height][width][3] with 8-bit RGB values, and that code is a string consisting of which of the RGB values to invert. Is that correct? \$\endgroup\$
    – JS1
    Apr 17, 2015 at 6:15

2 Answers 2

2
\$\begingroup\$

I rewrote your function so the main loop didn't have to loop against code at all. I did that by preprocessing the code string. I also reordered the loops so that the array would be traversed in the same order as memory (good for cache hits). It ran about 39x as fast as the original function, using a 5000 x 5000 array.

void invert(int width, int height, char *code)
{
    int x, y, z;
    int i, n;
    int doInvert[3] = {0};

    n = strlen(code);
    for (i=0;i<n;i++) {
        switch (code[i]) {
            case 'R': doInvert[0] = 1; break;
            case 'G': doInvert[1] = 1; break;
            case 'B': doInvert[2] = 1; break;
            default : break;
        }
    }
    for (x=0; x<height; x++) {
        for (y=0; y<width; y++) {
            for (z=0; z<3; z++) {
                if (doInvert[z])
                    b[x][y][z] = 255 - a[x][y][z];
                else
                    b[x][y][z] = a[x][y][z];
            }
        }
    }
}
\$\endgroup\$
6
  • \$\begingroup\$ I went the same direction, just processing the code string once. I took the approach of memcpy for the whole array and then just swap as needed. Since you have a test environment setup (it sounds like), would you be willing to test my attempt with a memcpy and just invert as needed. It may not be faster than yours, but I was guessing it might potentially yield better cache performance in the loop since you wouldn't be accessing two separate arrays so you could gain on localization. \$\endgroup\$
    – pstrjds
    Apr 17, 2015 at 6:40
  • \$\begingroup\$ @pstrjds I did what you said, and it was about 20% slower. Probably because it had to walk through memory twice that way. \$\endgroup\$
    – JS1
    Apr 17, 2015 at 6:52
  • \$\begingroup\$ Thanks - it was just a thought. I didn't think it would be better, it was a guess and worth a try. \$\endgroup\$
    – pstrjds
    Apr 17, 2015 at 6:53
  • \$\begingroup\$ @pstrjds Actually I'm surprised at how much faster this is than the original. At first I forgot to use -O4 when I compiled, and it was only 6.4x faster. Now using -O4, it is somewhere between 30x-50x faster. I had to actually test the resulting matrix to make sure it wasn't just optimizing the whole function call away! \$\endgroup\$
    – JS1
    Apr 17, 2015 at 6:57
  • \$\begingroup\$ I figured one of the biggest issues would be the strlen call in the innermost loop. That is expensive and I don't think the compiler could optimize it away. It might have, but I am not sure it would be able to see it as loop invariant. So for 5000x5000 that function got called alot! \$\endgroup\$
    – pstrjds
    Apr 17, 2015 at 7:03
1
\$\begingroup\$
  1. You can move the `strlen` call to outside all of the loops since that is loop invariant.
  2. You can store the "RGB" char value at the outer for loop so that you aren't looking it up inside the for loops. I would assume a good compiler would do that, but due to the nesting it might miss it and so you can just code it up yourself that way.
  3. Just kind of brainstorming, but it might be better to figure out which bits you need to flip, memcpy the whole array, and then just flip those specific bits. (see invert2) This turned out to be a bad idea

Just as an aside, my C is rusty and I did not compile this, but the concept should still come through clearly.

void invert(int width, int height, char *code)
{
  int x, y, z;
  int i, n;
  char RGB[4]="RGB";
  char rgb;

  n = strlen(code);

  for (z=0; z<3; z++)
  {
    rgb = RGB[z];
    for (y=0; y<width; y++)
      for (x=0; x<height; x++)
      {
        b[x][y][z] = a[x][y][z];
        for(i=0; i<n; i++)
        {
          if (code[i]==rgb)
          {
            b[x][y][z] = 255 - a[x][y][z];
          }
        }
      }
  }
  return;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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