c# - Why is there huge performance hit in 2048x2048 versus 2047x2047 array multiplication?

itemprop="text">

I am making some matrix multiplication
benchmarking, as previously mentioned in
href="https://stackoverflow.com/questions/6058139/why-is-matlab-so-fast-in-matrix-multiplication">Why
is MATLAB so fast in matrix
multiplication?

Now I've
got another issue, when multiplying two 2048x2048 matrices, there is a big difference
between C# and others. When I try multiply only 2047x2047 matrices, it seems normal.
Added some others for comparsion too.

1024x1024
- 10 seconds.

1027x1027 - 10
seconds.

2047x2047 - 90
seconds.

2048x2048 - 300
seconds.

2049x2049 - 91 seconds.
(update)

2500x2500 - 166
seconds

That is three and a half minute
difference for the 2k by 2k case.

using 2dim
arrays

//Array init like
            this
int rozmer = 2048;

float[,] matice = new
            float[rozmer, rozmer];

//Main multiply code
for(int j =
            0; j < rozmer; j++)
{
 for (int k = 0; k < rozmer;
            k++)
 {
 float temp = 0;
 for (int m = 0; m < rozmer;
            m++)
 {

 temp = temp + matice1[j,m] *
            matice2[m,k];
 }
 matice3[j, k] = temp;
 }

            }

itemprop="text">

class="normal">Answer

This
probably has do with conflicts in your L2
cache.

Cache misses on matice1 are not the
problem because they are accessed sequentially.

However for matice2
if a full column fits in L2 (i.e when you access matice2[0, 0], matice2[1, 0],
matice2[2, 0] ... etc, nothing gets evicted) than there is no problem with cache misses
with matice2 either.

Now to go deeper in how
caches works, if byte address of your variable is X, than the cache line for it would be
(X >> 6) & (L - 1). Where L is total number of cache lines in your cache. L is
always power of 2.
The six comes from fact that 2^6 == 64 bytes is standard
size of cache line.

Now what does this mean?
Well it means that if I have address X and address Y and
(X >> 6) - (Y
>> 6) is divisible by L (i.e. some large power of 2), they will be stored in the
same cacheline.

Now to go back to your problem
what is the difference between 2048 and 2049,

when 2048 is your
size:

if you take &matice2[x, k] and
&matice2[y, k] the difference (&matice2[x, k] >> 6) - (&matice2[y,k]
>> 6) will be divisible by 2048 * 4 (size of float). So a large power of
2.

Thus depending on size of your L2 you will
have a lot of cache line conflicts, and only utilize small portion of your L2 to store a
column, thus you wont actually be able to store full column in your cache, thus you will
get bad performance.

When size is 2049, then the
difference is 2049 * 4 which is not power of 2 thus you will have less conflicts and
your column will safely fit into your cache.

Now
to test this theory there are couple things you can
do:

Allocate your array matice2 array
like this matice2 [razmor, 4096], and run with razmor = 1024, 1025 or any size, and you
should see very bad performance compared to what you had before. This is because you
forcefully align all columns to conflict with each
other.

Then try matice2 [razmor, 4097] and run
it with any size and you should see much better performance.