4

I have been tasked with optimizing a particular for loop in C. Here is the loop:

#define ARRAY_SIZE 10000
#define N_TIMES    600000

for (i = 0; i < N_TIMES; i++)
{
    int j;

    for (j = 0; j < ARRAY_SIZE; j++)
    {
        sum += array[j];
    }
}

I'm supposed to use loop unrolling, loop splitting, and pointers in order to speed it up, but every time I try to implement something, the program doesn't return. Here's what I've tried so far:

for (i = 0; i < N_TIMES; i++) 
{
    int j,k;

    for (j = 0; j < ARRAY_SIZE; j++) 
    {    
        for (k = 0; k < 100; k += 2) 
        {
            sum += array[k];
            sum += array[k + 1];
        }
    } 
}

I don't understand why the program doesn't even return now. Any help would be appreciated.

Improve this question
13
  • 1
    Use a debugger. I would leave the compiler do the optimizations. I guess it is some homework! And the second program is not the same as the first, you are summing the array only up to 101 in the second case. Commented Jun 10, 2014 at 4:59
  • 6
    Your new program's run time is about 100x the original. Commented Jun 10, 2014 at 4:59
  • 2
    @Sky I would say about 100x as it does sum += twice... Commented Jun 10, 2014 at 5:05
  • 2
    Not what you asked, but you can eliminate the outer loop entirely. And in the inner loop just have sum += array[j] * N_TIMES; Now you can use pointer arithmetic for a little more performance with sum += *array++ * N_TIMES; Commented Jun 10, 2014 at 5:06
  • 1
    TBH the best answer is probably to take a modern compiler, put it on maximum optimization level and see what assembly it generates Commented Jun 10, 2014 at 5:25

3 Answers 3

Reset to default
9

That second piece of code is both inefficient and wrong, since it adds values more than the original code.

The loop unrolling (or lessening in this case since you probably don't want to unroll a ten-thousand-iteration loop) would be:

// Ensure ARRAY_SIZE is a multiple of two before trying this.
for (int i = 0; i < N_TIMES; i++)
    for (int j = 0; j < ARRAY_SIZE; j += 2)
        sum += array[j] + array[j+1];

But, to be honest, the days of dumb compilers has long since gone. You should generally leave this level of micro-optimisation up to your compiler, while you concentrate on the more high-level stuff like data structures, algorithms and human analysis.

That last one is rather important. Since you're adding the same array to an accumulated sum a constant number of times, you only really need the sum of the array once, then you can add that partial sum as many times as you want:

int temp = 0;
for (int i = 0; i < ARRAY_SIZE; i++)
    temp += array[i];
sum += temp * N_TIMES;

It's still O(n) but with a much lower multiplier on the n (one rather than six hundred thousand). It may be that gcc's insane optimisation level of -O3 could work that out but I doubt it. The human brain can still outdo computers in a lot of areas.

For now, anyway :-)

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

Thank you. I understand that compilers will do most of the work these days, but the assignment requires that I use these optimization techniques to speed things up. I appreciate the help!
@user3698112: then submit something similar to the second code segment. You'll blow the other submissions out of the water and probably also blow the hat off your educator :-)
@paxdiablo the second for loop is a simple multiplication sum = temp * N_TIMES;
@Manül: yes, how very silly of me. Modified to incorporate your suggestion.
If you're going to unroll, fix the "loop carried dependency" by summing into two separate accumulators, then add them at the end: sum1 += array[j]; sum2 += array[j+1]; Otherwise the unrolling doesn't really accomplish much.
|
3

There is nothing wrong on your program... it will return. It is only going to take 50 times more than the first one...

On the first you had 2 fors: 600.000 * 10.000 = 6.000.000.000 iterations.

On the second you have 3 fors: 600.000 * 10.000 * 50 = 300.000.000.000 iterations...

Improve this answer

3 Comments

There's fifty times the number of loops but each loop also does twice the workload. So the time takes will probably be about a hundred times as long.
Yes, that's why i used the word iterations and not operations... by iterations I meant the number of comparisons/increments for the variables that control the loops only...
Ah, I see, I looked only at the "take 50 times more" and assumed that was time. My apologies.
1

Loop unrolling doesn't speed loops up, it slows them down. In olden times it gave you a speed bump by reducing the number of conditional evaluations. In modern times it slows you down by killing the cache.

There's no obvious use case for loop splitting here. To split a loop you're looking for two or more obvious groupings in the iterations. At a stretch you could multiply array[j] by i rather than doing the outer loop and claim you've split the inner from the outer, then discarded the outer as useless.

C array-indexing syntax is just defined as (a peculiar syntax for) pointer arithmetic. But I guess you'd want something like:

sum += *arrayPointer++;

In place of your use of j, with things initialised suitably. But I doubt you'll gain anything from it.

As per the comments, if this were real life then you'd just let the compiler figure this stuff out.

Improve this answer

2 Comments

You can partially unroll a loop and still stay within code cache bounds. Not sure if the effect is worth it though, given how fast the cache is. But you're right, in a system that caches code, unrolling a 10000-iteration loop may well make things worse.
@paxdiabli possibly true, but your expanded loop is more likely to push something else out of the cache, especially if it starts near a page boundary. But on the other hand your branch predictor is quite possibly running the next iteration while it evaluates the condition putting you back to no benefit. All cutting back to the issue that these are highly architecture-dependant trade offs, best left to the architecture-specific compiler.

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.