Optimization of array access

[Christoph Bartoschek <bartoschek at gmx dot de>]

Hi,

compiling the following code with g++ -O2 gives me unexpected results. The 
test_pointer() function seems to be faster although it uses more memory and 
has to use lots of pointer dereferenzes. Replacing line 19 by lines 15-18 
has no effect on the runtime.

Why is simulating an 3d-array by pointers faster than using a contingous 
memory array?

Greetings
Christoph

#include <iostream>
#include <sys/time.h>

static int const SIZE = 200;

typedef int * int_p;
typedef int ** int_pp;

int * array = new int[SIZE*SIZE*SIZE];
int *** pointer = new int_pp[SIZE];

typedef int * int_p;

void test_array() {
//    for (int i = 0; i < SIZE; ++i)  //Line 15
//       for (int j = 0; j < SIZE; ++j) //Line 16
//          for (int k = 0; k < SIZE; ++k) //LIne 17
//             array[i * SIZE * SIZE + j * SIZE + k]++;  //Line 18
   for (int i = 0; i < SIZE * SIZE * SIZE; ++i)
      ++array[i];
}

void test_pointer() {
   for (int i = 0; i < SIZE; ++i) 
      for (int j = 0; j < SIZE; ++j)
         for (int k = 0; k < SIZE; ++k)
            pointer[i][j][k]++;
}

int main() {

   for (int i = 0; i < SIZE; ++i) pointer[i] = new int_p[SIZE];
   for (int i = 0; i < SIZE; ++i) 
      for (int j = 0; j < SIZE; ++j)
         pointer[i][j] = new int[SIZE];
         
   struct timeval start, stop;
   gettimeofday(&start, NULL);
   for (int i = 0; i < 10; ++i)
      test_array();
   gettimeofday(&stop, NULL);
   std::cout << "Array: " << (stop.tv_sec - start.tv_sec) + 1e-6 * 
(stop.tv_usec - start.tv_usec) << " s" <<std::endl;
   

   gettimeofday(&start, NULL);
   for (int i = 0; i < 10; ++i)
      test_pointer();
   gettimeofday(&stop, NULL);
   std::cout << "Zeiger: " << (stop.tv_sec - start.tv_sec) + 1e-6 * 
(stop.tv_usec - start.tv_usec) << " s" <<std::endl;
}