title: Matrix Multiplication optimization via matrix transpose
body: <p>I am working on an assignment where I transpose a matrix to reduce cache misses for a matrix multiplication operation. From what I understand from a few classmates, I should get 8x improvement. However, I am only getting 2x ... what might I be doing wrong? </p>
  
  <p><a href="https://gist.github.com/3824894#file_matrix.cpp" rel="nofollow">Full Source on GitHub</a></p>
  
  <pre><code>void transpose(int size, matrix m) {
      int i, j;
      for (i = 0; i &lt; size; i++) 
          for (j = 0; j &lt; size; j++) 
              std::swap(m.element[i][j], m.element[j][i]);
  }
  
  void mm(matrix a, matrix b, matrix result) {
      int i, j, k;
      int size = a.size;
      long long before, after;
  
      before = wall_clock_time();
      // Do the multiplication
      transpose(size, b); // transpose the matrix to reduce cache miss
      for (i = 0; i &lt; size; i++)
          for (j = 0; j &lt; size; j++) {
              int tmp = 0; // save memory writes
              for(k = 0; k &lt; size; k++)
                  tmp += a.element[i][k] * b.element[j][k];
              result.element[i][j] = tmp;
          }
      after = wall_clock_time();
      fprintf(stderr, "Matrix multiplication took %1.2f seconds\n", ((float)(after - before))/1000000000);
  }
  </code></pre>
  
  <p>Am I doing things right so far? </p>
  
  <p>FYI: The next optimization I need to do is use SIMD/Intel SSE3</p>