Matrix-Multiplication: Why non-blocked outperforms blocked?
<p>I'm trying to speed up a matrix multiplication algorithm by blocking the loops to improve cache performance, yet the non-blocked version remains significantly faster regardless of matrix size, block size (I've tried lots of values between 2 and 200, potenses of 2 and others) and optimization level.</p>

<p>Non-blocked version:</p>

<pre><code>  for(size_t i = 0; i &lt; n; ++i)
  {
    for(size_t k = 0; k &lt; n; ++k)
    {
      int r = a[i][k];
      for(size_t j = 0; j &lt; n; ++j)
      {
        c[i][j] += r * b[k][j];
      }
    }
  }
</code></pre>

<p>Blocked version:</p>

<pre><code>  for(size_t kk = 0; kk &lt; n; kk += BLOCK)
  {
    for(size_t jj = 0; jj &lt; n; jj += BLOCK)
    {
      for(size_t i = 0; i &lt; n; ++i)
      {
        for(size_t k = kk; k &lt; kk + BLOCK; ++k)
        {
          int r = a[i][k];
          for(size_t j = jj; j &lt; jj + BLOCK; ++j)
          {
            c[i][j] += r * b[k][j];
          }
        }
      }
    }
  }
</code></pre>

<p>I also have a bijk version and a 6-loops bikj version but they all gets outperformed by the non-blocked version and I don't get why this happens. Every paper and tutorial that I've come across seems to indicate that the the blocked version should be significantly faster. I'm running this on a Core i5 if that matters.</p>