title: compiler nested loop optimization for sequential memory access.
body: <p>I came across a strange performance issue in a matrix multiply benchmark (matrix_mult in Metis from the <a href="http://pdos.csail.mit.edu/mosbench/">MOSBENCH</a> suite). The benchmark was optimized to tile the data such that the active working set was 12kb (3 tiles of 32x32 ints) and would fit into the L1 cache. To make a long story short, swapping the inner two most loops had a performance difference of almost 4x on certain array input sizes (4096, 8192) and about a 30% difference on others. The problem essentially came down to accessing elements sequentially versus in a stride pattern. Certain array sizes I think created a bad stride access that generated a lot cache line collisions. The performance difference is noticeably less when changing from 2-way associative L1 to an 8-way associative L1.</p>
  
  <p>My question is why doesn't gcc optimize loop ordering to maximize sequential memory accesses?  </p>
  
  <p>Below is a simplified version of the problem (note that performance times are highly dependent on L1 configuration. The numbers indicated below are from 2.3 GHZ AMD system with 64K L1 2-way associative compiled with -O3).</p>
  
  <pre><code>N = ARRAY_SIZE // 1024
  int* mat_A = (int*)malloc(N*N*sizeof(int));
  int* mat_B = (int*)malloc(N*N*sizeof(int));
  int* mat_C = (int*)malloc(N*N*sizeof(int));
  
  // Elements of mat_B are accessed in a stride pattern of length N
  // This takes 800 msec  
  for (int t = 0; t &lt; 1000; t++) 
     for (int a = 0; a &lt; 32; a++) 
        for (int b = 0; b &lt; 32; b++)
           for (int c = 0; c &lt; 32; c++) 
              mat_C[N*a+b] += mat_A[N*a+c] * mat_B[N*c+b];
  
  // Inner two loops are swapped
  // Elements are now accessed sequentially in inner loop
  // This takes 172 msec  
  for (int t = 0; t &lt; 1000; t++) 
     for (int a = 0; a &lt; 32; a++) 
        for (int c = 0; c &lt; 32; c++) 
           for (int b = 0; b &lt; 32; b++)
              mat_C[N*a+b] += mat_A[N*a+c] * mat_B[N*c+b];
  </code></pre>