1
\$\begingroup\$

I've been working on optimizing such as loop unrolling, is there anything I can do to optimize this code to make it run faster/in less cycles?

void compute_ranks(float *F, int N, int *R, float *avg, float *passing_avg, int *num_passed) {
    int i, j;
    *num_passed = 0;
    *avg = 0.0;
    *passing_avg = 0.0;

    // init ranks
    for (i = 0; i < N; i++) {
        R[i] = 1;
    }

    // compute ranks
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            if (F[i] < F[j]) {
                R[i] += 1;
            }
        }
    }

    // compute averages
    for (i = 0; i < N; i++) {
        *avg += F[i];
        if (F[i] >= 50.0) {
            *passing_avg += F[i];
            *num_passed += 1;
        }
    }

    // check for div by 0
    if (N > 0) *avg /= N;
    if (*num_passed) *passing_avg /= *num_passed;

} // compute_ranks

I did this for the first one

or (i = 0; i < N; i += 5) {
        R[i] = 1;
        R[i+1] = 1;
        R[i+2] = 1;
        R[i+3] = 1;
        R[i+4] = 1;
    }*/

Is there a way to not use pointers or anything really to make this more optimized?

\$\endgroup\$
2
  • 3
    \$\begingroup\$ Welcome to Code Review! As per the How to Ask guidelines, please retitle the question to state what the code accomplishes, not what your concern is. \$\endgroup\$ Nov 25, 2016 at 8:52
  • 1
    \$\begingroup\$ If you work with huge numbers of elements, consider switching to a different algorithm. Computing the rank is similar to sorting. Your algorithm is currently of the order of O(NN) while sorting is known to be of O(Nlog(N)). \$\endgroup\$
    – Codo
    Nov 25, 2016 at 9:13

3 Answers 3

5
\$\begingroup\$

One possible optimization is to use local variables instead of directly writing to the out parameters. So instead of:

// compute averages
for (i = 0; i < N; i++) {
    *avg += F[i];
    if (F[i] >= 50.0) {
        *passing_avg += F[i];
        *num_passed += 1;
    }
}

you write:

int l_num_passed = 0;
float l_avg = 0.0;
float l_passing_avg = 0.0;

// compute averages
for (i = 0; i < N; i++) {
    l_avg += F[i];
    if (F[i] >= 50.0) {
        l_passing_avg += F[i];
        l_num_passed += 1;
    }
}

*num_passed = l_num_passed;
*avg = l_avg;
*passing_avg = l_passing_avg;

That way the compiler can use fast registers. If you directly write to the out parameter within the loop, the compiler cannot use registers as it must stay on the defensive side by assuming that avg could point to the same memory location as passing_avg or even num_passed.

This unfortunate feature of C and C++ is known as pointer aliasing and often prevents the compiler from making effective use of registers.

You can also use local variables for the other loop. Instead of:

// compute ranks
for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
        if (F[i] < F[j]) {
            R[i] += 1;
        }
    }
}

write:

float fi;
int rank;

// compute ranks
for (i = 0; i < N; i++) {
    fi = F[i];
    rank = 1;
    for (j = 0; j < N; j++) {
        if (fi < F[j]) {
            rank += 1;
        }
    }
    R[i] = rank;
}
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Congratulations on passing your First Post Review with flying colours. Feel free to stick around! \$\endgroup\$
    – Mast
    Nov 25, 2016 at 9:53
  • \$\begingroup\$ Hello, thank you so much! I did try these right after I posted my question, but I the results hasn't changed that much. Is there a way to make them even faster? I kinda did the ones you mentioned before, tried them but didn't see that much difference \$\endgroup\$
    – Andrew
    Nov 25, 2016 at 10:51
  • \$\begingroup\$ @Andrew did you compile with optimizations enabled? \$\endgroup\$ Nov 25, 2016 at 11:19
3
\$\begingroup\$

Check if your compiler has an annotation that lets you signal that the pointers will not alias (overlap). This will allow the compiler to unroll and interleave iterations of the loops that touch multiple pointers.

As a clarity change I would make a results struct:

struct ranks_results{
    float avg;
    float passing_avg;
    int num_passed;
}

and then make that the return value.


Computing ranks can be done by doing a sort the indexes based on the value in the F array:

// init ranks
for (i = 0; i < N; i++) {
    R[i] = i; 
}

globF = F;
qsort(R, N, sizeof(*R), index_comp);

//inc by one so the rank becomes 1 based.
for (i = 0; i < N; i++) {
    R[i]++;
}

where index_comp and globF are:

float *globF; //must be global because we can't pass a context pointer to qsort
// this makes it non-thread safe!!

int index_comp (const void * a, const void * b)
{
   float fa = globF[*(int*)a];
   float fb = globF[*(int*)b];

   if(fa == fb) return 0;
   if(fa < fb) return -1;
   if(fa > fb) return 1;
}

This will make the algorithm O(n log n) instead of O(n²)


I see that your function actually does 2 things, computes the ranks and computes 2 averages (one filtered and one not) and the computing effort of the ranks is not reused for the averages. It may be more advantageous to split them out into their own functions.

\$\endgroup\$
1
\$\begingroup\$

Can you not collapse your for loops down into a single loop?

// compute ranks
for (i = 0; i < N; i++) {
    R[i] = 1; // This will be initialised for use in the below inner loop

    for (j = 0; j < N; j++) {
        if (F[i] < F[j]) {
            R[i] += 1;
        }
    }

    *avg += F[i]; 
    if (F[i] >= 50.0) {
        *passing_avg += F[i];
        *num_passed += 1;
    }
}

It may only be a relatively small change and not likely to be significantly faster, if I've made an error forgive me.

\$\endgroup\$

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.