Why is my program slow when looping over exactly 8192 elements?

by

Here is the extract from the program in question. The matrix img[][] has the size SIZE×SIZE, and is initialized at:

img[j][i] = 2 * j + i

Then, you make a matrix res[][], and each field in here is made to be the average of the 9 fields around it in the img matrix. The border is left at 0 for simplicity.

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

That’s all there’s to the program. For completeness’ sake, here is what comes before. No code comes after. As you can see, it’s just initialization.

#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++) 
    for(j=0;j<SIZE;j++) 
        img[j][i] = (2*j+i)%8196;

Basically, this program is slow when SIZE is a multiple of 2048, e.g. the execution times:

SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

The compiler is GCC.
From what I know, this is because of memory management, but I don’t really know too much about that subject, which is why I’m asking here.

Also how to fix this would be nice, but if someone could explain these execution times I’d already be happy enough.

I already know of malloc/free, but the problem is not amount of memory used, it’s merely execution time, so I don’t know how that would help.

2 s
2

Leave a Comment