22

For an assignment of a course called High Performance Computing, I required to optimize the following code fragment:

int foobar(int a, int b, int N)
{
    int i, j, k, x, y;
    x = 0;
    y = 0;
    k = 256;
    for (i = 0; i <= N; i++) {
        for (j = i + 1; j <= N; j++) {
            x = x + 4*(2*i+j)*(i+2*k);
            if (i > j){
               y = y + 8*(i-j);
            }else{
               y = y + 8*(j-i);
            }
        }
    }
    return x;
}

Using some recommendations, I managed to optimize the code (or at least I think so), such as:

  1. Constant Propagation
  2. Algebraic Simplification
  3. Copy Propagation
  4. Common Subexpression Elimination
  5. Dead Code Elimination
  6. Loop Invariant Removal
  7. bitwise shifts instead of multiplication as they are less expensive.

Here's my code:

int foobar(int a, int b, int N) {

    int i, j, x, y, t;
    x = 0;
    y = 0;
    for (i = 0; i <= N; i++) {
        t = i + 512;
        for (j = i + 1; j <= N; j++) {
            x = x + ((i<<3) + (j<<2))*t;
        }
    }
    return x;
}

According to my instructor, a well optimized code instructions should have fewer or less costly instructions in assembly language level.And therefore must be run, the instructions in less time than the original code, ie calculations are made with::

execution time = instruction count * cycles per instruction

When I generate assembly code using the command: gcc -o code_opt.s -S foobar.c,

the generated code has many more lines than the original despite having made ​​some optimizations, and run-time is lower, but not as much as in the original code. What am I doing wrong?

Do not paste the assembly code as both are very extensive. So I'm calling the function "foobar" in the main and I am measuring the execution time using the time command in linux

int main () {
    int a,b,N;

    scanf ("%d %d %d",&a,&b,&N);
    printf ("%d\n",foobar (a,b,N));
    return 0;
}
23
  • 33
    Constant Propagation, Algebraic Simplification, Copy Propagation, Common Subexpression Elimination, Dead Code Elimination, Loop Invariant Removal, and using bitwise shifts instead of multiplication as they are less expensive - fun fact: these are exactly the "simple" optimizations that modern optimizing compilers can do by themselves, and often better than the programmer; for this reason, usually a programmer is concerned with more "high level" (e.g. algorithmic) optimizations (or more subtle stuff - e.g. related to the cache - that in general require profiling). Commented Nov 25, 2012 at 21:53
  • 17
    Tell the compiler you want all the optimization bells and whistles, because it is smarter than you about this stuff? Commented Nov 25, 2012 at 21:53
  • 3
    Running gcc with -O3 should have some effect. Although I'm not sure how much an optimizing compiler defeats the purpose of this exercise.
    – pmr
    Commented Nov 25, 2012 at 21:55
  • 5
    Unfortunately, a lot of "HPC programming" courses look like they've been teleported straight from the 1970'ies. Been there, done that. And unfortunately for the OP, based on this assignment, including this one. :(
    – janneb
    Commented Nov 25, 2012 at 22:00
  • 4
    Also: Is it just me, or does this whole function look like it could be flattened into a single, loop-free expression?
    – user149341
    Commented Nov 25, 2012 at 22:03

7 Answers 7

23

Initially:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 4*(2*i+j)*(i+2*k);
        if (i > j){
           y = y + 8*(i-j);
        }else{
           y = y + 8*(j-i);
        }
    }
}

Removing y calculations:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 4*(2*i+j)*(i+2*k);
    }
}

Splitting i, j, k:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 8*i*i + 16*i*k ;                // multiple of  1  (no j)
        x = x + (4*i + 8*k)*j ;                 // multiple of  j
    }
}

Moving them externally (and removing the loop that runs N-i times):

for (i = 0; i <= N; i++) {
    x = x + (8*i*i + 16*i*k) * (N-i) ;
    x = x + (4*i + 8*k) * ((N*N+N)/2 - (i*i+i)/2) ;
}

Rewritting:

for (i = 0; i <= N; i++) {
    x = x +         ( 8*k*(N*N+N)/2 ) ;
    x = x +   i   * ( 16*k*N + 4*(N*N+N)/2 + 8*k*(-1/2) ) ;
    x = x +  i*i  * ( 8*N + 16*k*(-1) + 4*(-1/2) + 8*k*(-1/2) );
    x = x + i*i*i * ( 8*(-1) + 4*(-1/2) ) ;
}

Rewritting - recalculating:

for (i = 0; i <= N; i++) {
    x = x + 4*k*(N*N+N) ;                            // multiple of 1
    x = x +   i   * ( 16*k*N + 2*(N*N+N) - 4*k ) ;   // multiple of i
    x = x +  i*i  * ( 8*N - 20*k - 2 ) ;             // multiple of i^2
    x = x + i*i*i * ( -10 ) ;                        // multiple of i^3
}

Another move to external (and removal of the i loop):

x = x + ( 4*k*(N*N+N) )              * (N+1) ;
x = x + ( 16*k*N + 2*(N*N+N) - 4*k ) * ((N*(N+1))/2) ;
x = x + ( 8*N - 20*k - 2 )           * ((N*(N+1)*(2*N+1))/6);
x = x + (-10)                        * ((N*N*(N+1)*(N+1))/4) ;

Both the above loop removals use the summation formulas:

Sum(1, i = 0..n) = n+1
Sum(i1, i = 0..n) = n(n + 1)/2
Sum(i2, i = 0..n) = n(n + 1)(2n + 1)/6
Sum(i3, i = 0..n) = n2(n + 1)2/4

8
  • 1
    @Mysticial: Probably somewhat like "looks too complicated". Nicely done, ypercube!
    – stefan
    Commented Nov 25, 2012 at 23:50
  • 1
    @Mysticial: Probably "don't do people's homework for them", which is a viewpoint for which I confess to having a lot of sympathy. Commented Nov 26, 2012 at 0:00
  • I like the approach, but this simply does not return correct results. Trivial case: running it with N = 1, it returns 2049 instead of the correct 2048. Commented Nov 26, 2012 at 0:53
  • @NikB.: Are you sure? The codepad test shows 2048. Commented Nov 26, 2012 at 1:01
  • It does for me, on VS2010 64-bit. I'll double check a little later with a different compiler. Is that the entire body of the function (plus int x=0, k=256;) followed by return x? Commented Nov 26, 2012 at 1:18
22

y does not affect the final result of the code - removed:

int foobar(int a, int b, int N)
{
    int i, j, k, x, y;
    x = 0;
    //y = 0;
    k = 256;
    for (i = 0; i <= N; i++) {
        for (j = i + 1; j <= N; j++) {
            x = x + 4*(2*i+j)*(i+2*k);
            //if (i > j){
            //   y = y + 8*(i-j);
            //}else{
            //   y = y + 8*(j-i);
            //}
        }
    }
    return x;
}

k is simply a constant:

int foobar(int a, int b, int N)
{
    int i, j, x;
    x = 0;
    for (i = 0; i <= N; i++) {
        for (j = i + 1; j <= N; j++) {
            x = x + 4*(2*i+j)*(i+2*256);
        }
    }
    return x;
}

The inner expression can be transformed to: x += 8*i*i + 4096*i + 4*i*j + 2048*j. Use math to push all of them to the outer loop: x += 8*i*i*(N-i) + 4096*i*(N-i) + 2*i*(N-i)*(N+i+1) + 1024*(N-i)*(N+i+1).

You can expand the above expression, and apply sum of squares and sum of cubes formula to obtain a close form expression, which should run faster than the doubly nested loop. I leave it as an exercise to you. As a result, i and j will also be removed.

a and b should also be removed if possible - since a and b are supplied as argument but never used in your code.

Sum of squares and sum of cubes formula:

  • Sum(x2, x = 1..n) = n(n + 1)(2n + 1)/6
  • Sum(x3, x = 1..n) = n2(n + 1)2/4
6
  • 1
    if i don't have a typo: x = (7 * N^4 + 8194 * N^3 + 6137 * N^2 - 2050 * N) / 6
    – stefan
    Commented Nov 25, 2012 at 22:18
  • 1
    Thanks @nhahtdh! As a side note: the evaluation of this term might lead to overflow. Some rearrangement might be useful to account for that (such as pulling out N, sorting a bit to have divisibility by 6 for a large part)
    – stefan
    Commented Nov 25, 2012 at 22:33
  • @stefan: I think pulling out divisible part, calculate the rest divide by 6, then do the subtraction, and then doing the addition should be a good order. (N^4 + 4*N^3 + 5*N^2 - 4*N)/6 - 341*N + ...
    – nhahtdh
    Commented Nov 25, 2012 at 22:37
  • Yeah, i would do it something along the lines of N * ((N + 1)(N(1365 + N) - 342) + (N-2)(N-1)(N+1)/6) :D
    – stefan
    Commented Nov 25, 2012 at 22:54
  • 1
    Nope, only if you deal with integers ;-) To allow that, just split it like this: N ((N + 1)(N(1365 + N) - 342)) + N(N-2)(N-1)(N+1)/6
    – stefan
    Commented Nov 25, 2012 at 23:03
20

This function is equivalent with the following formula, which contains only 4 integer multiplications, and 1 integer division:

x = N * (N + 1) * (N * (7 * N + 8187) - 2050) / 6;

To get this, I simply typed the sum calculated by your nested loops into Wolfram Alpha:

sum (sum (8*i*i+4096*i+4*i*j+2048*j), j=i+1..N), i=0..N

Here is the direct link to the solution. Think before coding. Sometimes your brain can optimize code better than any compiler.

6
  • That's why many developers are replaced by mathematicians. ;) Commented Nov 26, 2012 at 9:11
  • 2
    This includes the most important lesson. Shifting around small bits in the code will give you speed increases in the range of 10%-1000%. A better algorithm, such as this one, might lead to a hundred-fold speedup, which is impossible with any other "optimization".
    – Alexander
    Commented Nov 26, 2012 at 10:00
  • 1
    @Alexander The other lesson is, don't do formal derivations by hand, use a symbolic math software if possible. Others also tried to derive a formula, but no one found the simplest one, the one Wolfram Alpha derived.
    – kol
    Commented Nov 26, 2012 at 10:23
  • I'm pretty sure many could find the formula by hand. Not faster than Wolfram Alpha or any other symbolic calulator but equally well. Commented Dec 1, 2012 at 21:00
  • @ypercube You are absolutely right. When I wrote that comment I was listening to the birth of other answers and I was surprised to see people struggling to derive the correct formula. I didn't want to hurt anybody, I just wanted to emphasize how useful symbolic calculators can be.
    – kol
    Commented Dec 1, 2012 at 21:57
5

Briefly scanning the first routine, the first thing you notice is that expressions involving "y" are completely unused and can be eliminated (as you did). This further permits eliminating the if/else (as you did).

What remains is the two for loops and the messy expression. Factoring out the pieces of that expression that do not depend on j is the next step. You removed one such expression, but (i<<3) (ie, i * 8) remains in the inner loop, and can be removed.

Pascal's answer reminded me that you can use a loop stride optimization. First move (i<<3) * t out of the inner loop (call it i1), then calculate, when initializing the loop, a value j1 that equals (i<<2) * t. On each iteration increment j1 by 4 * t (which is a pre-calculated constant). Replace your inner expression with x = x + i1 + j1;.

One suspects that there may be some way to combine the two loops into one, with a stride, but I'm not seeing it offhand.

2

A few other things I can see. You don't need y, so you can remove its declaration and initialisation.

Also, the values passed in for a and b aren't actually used, so you could use these as local variables instead of x and t.

Also, rather than adding i to 512 each time through you can note that t starts at 512 and increments by 1 each iteration.

int foobar(int a, int b, int N) {
    int i, j;
    a = 0;
    b = 512;
    for (i = 0; i <= N; i++, b++) {
        for (j = i + 1; j <= N; j++) {
            a = a + ((i<<3) + (j<<2))*b;
        }
    }
    return a;
}

Once you get to this point you can also observe that, aside from initialising j, i and j are only used in a single mutiple each - i<<3 and j<<2. We can code this directly in the loop logic, thus:

int foobar(int a, int b, int N) {
    int i, j, iLimit, jLimit;
    a = 0;
    b = 512;
    iLimit = N << 3;
    jLimit = N << 2;
    for (i = 0; i <= iLimit; i+=8) {
        for (j = i >> 1 + 4; j <= jLimit; j+=4) {
            a = a + (i + j)*b;
        }
        b++;
    }
    return a;
}
2

OK... so here is my solution, along with inline comments to explain what I did and how.

int foobar(int N)
{ // We eliminate unused arguments 
    int x = 0, i = 0, i2 = 0, j, k, z;

    // We only iterate up to N on the outer loop, since the
    // last iteration doesn't do anything useful. Also we keep
    // track of '2*i' (which is used throughout the code) by a 
    // second variable 'i2' which we increment by two in every
    // iteration, essentially converting multiplication into addition.
    while(i < N) 
    {           
        // We hoist the calculation '4 * (i+2*k)' out of the loop
        // since k is a literal constant and 'i' is a constant during
        // the inner loop. We could convert the multiplication by 2
        // into a left shift, but hey, let's not go *crazy*! 
        //
        //  (4 * (i+2*k))         <=>
        //  (4 * i) + (4 * 2 * k) <=>
        //  (2 * i2) + (8 * k)    <=>
        //  (2 * i2) + (8 * 512)  <=>
        //  (2 * i2) + 2048

        k = (2 * i2) + 2048;

        // We have now converted the expression:
        //      x = x + 4*(2*i+j)*(i+2*k);
        //
        // into the expression:
        //      x = x + (i2 + j) * k;
        //
        // Counterintuively we now *expand* the formula into:
        //      x = x + (i2 * k) + (j * k);
        //
        // Now observe that (i2 * k) is a constant inside the inner
        // loop which we can calculate only once here. Also observe
        // that is simply added into x a total (N - i) times, so 
        // we take advantange of the abelian nature of addition
        // to hoist it completely out of the loop

        x = x + (i2 * k) * (N - i);

        // Observe that inside this loop we calculate (j * k) repeatedly, 
        // and that j is just an increasing counter. So now instead of
        // doing numerous multiplications, let's break the operation into
        // two parts: a multiplication, which we hoist out of the inner 
        // loop and additions which we continue performing in the inner 
        // loop.

        z = i * k;

        for (j = i + 1; j <= N; j++) 
        {
            z = z + k;          
            x = x + z;      
        }

        i++;
        i2 += 2;
    }   

    return x;
}

The code, without any of the explanations boils down to this:

int foobar(int N)
{
    int x = 0, i = 0, i2 = 0, j, k, z;

    while(i < N) 
    {                   
        k = (2 * i2) + 2048;

        x = x + (i2 * k) * (N - i);

        z = i * k;

        for (j = i + 1; j <= N; j++) 
        {
            z = z + k;          
            x = x + z;      
        }

        i++;
        i2 += 2;
    }   

    return x;
}

I hope this helps.

0

int foobar(int N) //To avoid unuse passing argument

{

int i, j, x=0;   //Remove unuseful variable, operation so save stack and Machine cycle

for (i = N; i--; )               //Don't check unnecessary comparison condition 

   for (j = N+1; --j>i; )

     x += (((i<<1)+j)*(i+512)<<2);  //Save Machine cycle ,Use shift instead of Multiply

return x;

}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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