   Tell me if I am right or not - Saving CPU usage
  I am trying to optimize CPU usage with bitwise operators in C++,The original part of code wasvoid optimize_me(int img[]){int width = 32;int height = 32;int factor = 4;for ( int y = 0; y < height; y += 1 ){for ( int x = 0; x < width; x += 1 ){int red   = (img[x + y * width] / 65536) % 256;int green = (img[x + y * width] /   256) % 256;int blue  = (img[x + y * width] /1) % 256;red   = red   / factor + y;green = green / factor + y;blue  = blue  / factor + y;if ( red > 255) red  = 255;    if ( green > 255) green = 255;    if ( blue  > 255) blue  = 255;if ( red   < 0) red= 0;    if ( green < 0) green = 0;    if ( blue  < 0) blue  = 0;img[x + y * width] = red*65536 + green*256 + blue*1;}}}and I re wrote this like is shown below:void optimize_me(int img[]){int width = 32;int height = 32;int factor = 4;for ( int y = 0; y < height; y += 1 ){for ( int x = 0; x < width; x += 1 ){int red   = (img[x + (y << 5)] >> 16) % 256;int green = (img[x + (y << 5)] >>  8) % 256;int blue  = (img[x + (y << 5)] >>  0) % 256;red   = (red   >> 2) + y;green = (green >> 2)+ y;blue  = (blue  >> 2) + y;if ( red >   255) red  = 255;    if ( green > 255) green = 255;    if ( blue  > 255) blue  = 255;if ( red   < 0) red   = 0;    if ( green < 0) green = 0;    if ( blue  < 0) blue  = 0;img[x + (y << 5)] = (red<<16) + (green<<8) + (blue<<0);}}}Is it OK ?How can optimize % 256 also ? I heard it is possible,but how? give me some light on this please.   
  Think about this carefully.If all you needed to do to optimise is replace division by a power of two with a bit-shift, wouldn't the compiler already do this? You need to be able to read and compare the generated assembly, to see if your source code changes are actually having an effect. You also need to be able to profile your code to see if these changes are having any effect, and also that the effect is a positive one.You have to be careful too, it looks like you have created a bug:img[x + (y << 5)] = (red<<16) + (green<<8) + (blue<<0);You have changed "y * width" to "y << 5".[edit]I apologise, I now see that the width is constant. Still, commenting such optimisations is important. Consider that maybe someday you change this function to accept images of an arbitrary size. Without a big warning comment mentioning what you are doing, it would be easy to overlook this and introduce this bug.But you can do something like this to remove the mod operation.// inside the inner loopint index = x + y * width;unsigned pixel = img[index];unsigned red = (pixel & 0xff0000) >> 16unsigned green = (pixel & 0xff00) >> 8;unsigned blue = pixel & 0xff;// ... transformation code ...img[index] = (red << 16) + (green << 8) + blue;Note that precomputing and storing the index and the pixel value might be optimisations, but more importantly they are code readability issues. It is far easier to read code like that, IMO.[Edited by - rip-off on May 15, 2009 4:11:41 PM];  I don't know how write shifting left or right operator to put in codeI read that in C people use << (shit to left) or >> (shift to right) but I don't kown if this is applicable in C++.Do you know ?   ;Quote:Original post by joecoolmanI don't know how write shifting left or right operator to put in codeHow did you do the first pass?Quote:I read that in C people use << (shit to left) or >> (shift to right) but I don't kown if this is applicable in C++.Do you know ?Yes, you can shift in C++ just as you can in C.   ;  Here is my first pass on your original function, written how I would write it* paying no mind to optimisation. I would usually use bitshifting to isolate pixel channels, that is not something I consider an optimisation. It seems more obvious to me.Some changes include high level ones, such as noticing that it is impossible for the inner transformation to create negative pixel values (you are adding "y", a positive number, to "red", "green" or "blue", another positive number).inline unsigned compute(unsigned value, int y){   const unsigned factor = 4;   return ((value / factor) + y) & 0xff;}void optimize_me(unsigned img[]){   const int width = 32;   const int height = 32;   for ( int y = 0; y < height; ++y )   { for ( int x = 0; x < width; ++x ) {    int index = x + (y * height);    unsigned pixel = img[index];    unsigned int red, green, blue;    red   = (pixel & 0xff0000) >> 16;    green = (pixel & 0x00ff00) >> 8;    blue  = (pixel & 0x0000ff);    red   = compute(red  , y);    green = compute(green, y);    blue  = compute(blue , y);    img[index] = (red << 16) + (green << 8) + blue; }   }}Now I am going to show what assembly GCC (with -O2) generates:.globl optimize_me   .type   optimize_me, @functionoptimize_me:   ; make some space   pushl   %ebp   movl    %esp, %ebp   pushl   %edi   xorl    %edi, %edi   pushl   %esi   pushl   %ebx   subl    $4, %esp   movl    8(%ebp), %eax   movl    %eax, -16(%ebp)   .p2align 4,,7 ; our outer loop.L4:   movl    -16(%ebp), %ebx   xorl    %esi, %esi   .p2align 4,,7   ; our inner loop.L5:   movl    (%ebx), %eax   addl    $1, %esi   ; extract the pixel channels.   movzbl  %al,%edx   movl    %eax, %ecx   ; the RGB values are in a,c and d.   ; this next bit isolates and compresses them to 0-255   andl    $16711680, %eax   andl    $65280, %ecx   shrl    $18, %eax   shrl    $10, %ecx   ; this appears to be the inlined call to "compute"   ; adding "y" to each component   ; plus a rather lonely looking shift right for the blue component   addl    %edi, %eax   shrl    $2, %edx   addl    %edi, %ecx   addl    %edi, %edx   ; and clamping it to 0-255   andl    $255, %eax   andl    $255, %ecx   andl    $255, %edx   ; this is writing the value back to the array   sall    $16, %eax   sall    $8, %ecx   addl    %eax, %edx   addl    %edx, %ecx   movl    %ecx, (%ebx)   addl    $4, %ebx   ; here is one loop   cmpl    $32, %esi   jne.L5   ; and another loop   addl    $1, %edi   subl    $-128, -16(%ebp)   cmpl    $32, %edi   jne.L4   ; cleanup and return from the function   addl    $4, %esp   popl    %ebx   popl    %esi   popl    %edi   popl    %ebp   retIf you aren't an assembly wizard (and I am surely not**, I can get by though [grin]) you might not see some of the points. Anyway, the point is that when presented with reasonable code, the compiler optimised it without much help. For example, there are no "div" instructions, it seems to be performing shifts (although I can only see the shift for the blue channel) despite the clear division used in "compute".You can write your code naturally, and the compiler will oblige. If you write your code so it is hard to read, you may cause bugs and you may still get the same assembly out the other side.Now, someone might be able to rewrite this using intrinsics, making use of SSE or something to increase the amount of work done per loop, but that is about it. I'm sure an assembly master could shave a few instructions off the generated code too.* Well, usually I wouldn't bother with the "inline" keyword. It appears on -O2, GCC doesn't inline the compute() function by itself. On -O3 it does. With the "inline" keyword, it inlines even in -O2.** This is a disclaimer in case I am drawing totally wrong conclusions from the assembly BTW [smile]   ;Quote:Original post by rip-offAnyway, the point is that when presented with reasonable code, the compiler optimised it without much help. For example, there are no "div" instructions, it seems to be performing shifts (although I can only see the shift for the blue channel) despite the clear division used in "compute".You can write your code naturally, and the compiler will oblige. If you write your code so it is hard to read, you may cause bugs and you may still get the same assembly out the other side.But that's not quite the whole truth, is it? There was one subtle change you had to make yet didn't really mention to get the compiler to translate those divisions and modulo operations straight into shifts and ANDs.At the end of the day just trusting the compiler to do the right thing without understanding the optimizations it is doing for you and occasionally checking up on the generated assembly code doesn't really work. Not if you're interested in maximizing performance anyway.   ;Quote:Original post by implicitBut that's not quite the whole truth, is it? There was one subtle change you had to make yet didn't really mention to get the compiler to translate those divisions and modulo operations straight into shifts and ANDs.Well, I cannot comment on what you are referring to, even if I have my suspicions on what you are hinting at [evil].I will emphasise: I wrote the code, then looked at the assembly. The only deviation from my own coding style was the presence of the "inline" keyword. I included it on a hunch, after all this is a discussion about optimisation.I didn't tweak the source trying to get it to produce pretty assembly.Quote:At the end of the day just trusting the compiler to do the right thing without understanding the optimizations it is doing for you and occasionally checking up on the generated assembly code doesn't really work. Not if you're interested in maximizing performance anyway.Well, I was focusing mainly on the bitshifting for that post, not general optimisation. In general, I would trust the compiler, use profiling to identify the hotspots, then maybe look at the assembly when investigating how to improve things.In this topic I was just warning against filling your code with complex bit shifting, when the compiler can do the hard work for you.   ;Quote:Original post by rip-offQuote:Original post by implicitBut that's not quite the whole truth, is it? There was one subtle change you had to make yet didn't really mention to get the compiler to translate those divisions and modulo operations straight into shifts and ANDs.Well, I cannot comment on what you are referring to, even if I have my suspicions on what you are hinting at [evil].Oh, I'm trying to refer to the fact that you switched to using unsigned integers. The compiler has to add extra code to deal with rounding negative integers towards zero when dividing or calculating the remainder, and whether or not you knew that or not the OP almost certainly didn't.At any rate I would probably write something along the following lines if I had to implement the algorithm in C. This relies on the fact that the height never exceeds 192, so we don't have to handle overflow. I'd probably unroll it a bit as well, but this is meant to be illustrative..void optimize_me(unsigned *img) {enum {WIDTH = 32,HEIGHT = 32,STEP = 0x010101};unsigned x, y;for(y = 0; y < HEIGHT * STEP; y += STEP) {for(x = 0; x < WIDTH; ++x) {unsigned pixel = *img;pixel >>= 2;pixel &= 0x3f3f3f;pixel += y;*img++ = pixel; }}};  Of course, but the primary reason I switched to unsigned was for correctness rather than as an optimisation.Clever code though [smile].   