optimizing array loop in c

Question

I have looked online and in my books but I can't seem to get this. I was asked to optimize a small part of a program. Specifically to take an array and add its contents within a small amount of time, with vi and gcc, without using the built-in optimizer. I have tried loop unrolling and a couple of other optimizations meant for products. Can you please help?

int length = ARRAY_SIZE;
int limit = length-4;
for (j=0; j < limit; j+=5) {
    sum += array[j] + array[j+1] + array[j+2] + array[j+3] + array[j+4];
}
for(; j < length; j++){
    sum += array[j];    
}

The array values are non-constant ints and all values have been initialized.

Answer 1

Create sub-sums which then add up to a sum.

Here's a basic version of what it might look like

for (j=0; j < limit; j+=4) {
    sum1 += array[j];
    sum2 += array[j+1];
    sum3 += array[j+2];
    sum4 += array[j+3];
}
sum = sum1 + sum2 + sum3 + sum4;

This avoids some read-after-write dependencies - that is, the computation of sum2 in each loop iteration need not wait on the results of sum1 to execute, and the processor can schedule both lines in the loop simultaneously.