Optimizing for speed - 4 dimensional array lookup in C

Question

I have a fitness function that is scoring the values on an int array based on data that lies on a 4D array. The profiler says this function is using 80% of CPU time (it needs to be called several million times). I can't seem to optimize it further (if it's even possible). Here is the function:

unsigned int lookup_array[26][26][26][26]; /* lookup_array is a global variable */

unsigned int get_i_score(unsigned int *input) {
register unsigned int i, score = 0;

for(i = len - 3; i--; ) 
    score += lookup_array[input[i]][input[i + 1]][input[i + 2]][input[i + 3]];

return(score)
}

I've tried to flatten the array to a single dimension but there was no improvement in performance. This is running on an IA32 CPU. Any CPU specific optimizations are also helpful. Thanks

Answer 1

What is the range of the array items? If you can change the array base type to unsigned short or unsigned char, you might get fewer cache misses because a larger portion of the array fits into the cache.

Answer 2

Most of your time probably goes into cache misses. If you can optimize those away, you can get a big performance boost.