title: Why does the order of loops in a matrix multiply algorithm affect performance?
body: <p>I am given two functions for finding the product of two matrices:</p>
  
  <pre><code> void MultiplyMatrices_1(int **a, int **b, int **c, int n){
        for (int i = 0; i &lt; n; i++)
            for (int j = 0; j &lt; n; j++)
                for (int k = 0; k &lt; n; k++)
                    c[i][j] = c[i][j] + a[i][k]*b[k][j];
    }
  
   void MultiplyMatrices_2(int **a, int **b, int **c, int n){
        for (int i = 0; i &lt; n; i++)
            for (int k = 0; k &lt; n; k++)
                for (int j = 0; j &lt; n; j++)
                    c[i][j] = c[i][j] + a[i][k]*b[k][j];
   }
  </code></pre>
  
  <p>I ran and profiled two executables using <code>gprof</code>, each with identical code except for this function. The second of these is significantly (about 5 times) faster for matrices of size 2048 x 2048.  Any ideas as to why?</p>