5 nested for loops, speed optimization

Question

I have a piece of code that calculates a value from "double **times". Let's say "times" is of dimensions [nsims][N] (created with malloc..), where int N=40 and int nsims=50000. The result is stored in "double **moments". So we have 5 nested for-loops. The problem however is speed, since this piece of code needs to be run approximately 1 million times. I am already using threads (not shown here) to split the inner-most for loop into 10 parallel threads, which already saves a lot of time. Does anyone see other optimization possibilities, especially regarding different data structures or something like this? Even if I don't have the "interm= ..." formula, it's still taking too much time. ``` for(j=2;j<=N;j++) { for(k=j;k<=N;k++) { moment=0; for(i=2;i<=N;i++) { for(l=i;l<=N;l++) { if(strcmp(mmethod, "emp")==0) { for(a=0;a<nsims;a++) { interm=interm + (double) times[a][k] * times[a][j]*times[a][i] * times[a][l]; } interm = (double) interm/nsims; moment = moment + (interm*i*l); interm=0; }…

Accepted Answer

Notice how within your inner loop, you are looking up and multiplying `times[a][k]*times[a][j]*times[a][i]` every time, even though that expression is the same for each value of `a`. It could be expensive, both for the multiplications and the memory lookups. (Maybe the compiler is smart enough to optimize that away, I don't know.) You might try caching those values in the inner loop though, something like this:

```
  ...
  double akji[nsims];
  for (a = 0; a < nsims; ++a) { akji[a] = times[a][k]*times[a][j]*times[a][i]; }
  for(l=i;l<=N;l++) {
interm=0;
for(a=0;a<nsims;a++) {
  interm += akji[a]*times[a][l]; 
}
moment += (interm*l);
  }
  moment = moment * i / nsims;
  ...
```

5 nested for loops, speed optimization

Solution

Problem