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.