Why is there huge performance hit in 2048×2048 versus 2047×2047 array multiplication?

by

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.

More Related Contents:

  1. Sum multidimensional array over dimensions [closed]
  2. C# how to create an array of objects? [closed]
  3. how to write every element of an array in a line of a textbox C# [closed]
  4. Convert string[] to Array
  5. How can I get more than one random numbers in a specific range using C#?
  6. How do I divide an array into separate arrays in C#?
  7. Cannot deserialize the JSON array (e.g. [1,2,3]) into type ‘ ‘ because type requires JSON object (e.g. {“name”:”value”}) to deserialize correctly
  8. Array slices in C#
  9. How do I concatenate two arrays in C#?
  10. Are arrays or lists passed by default by reference in c#?
  11. How do I convert a Stream into a byte[] in C#? [duplicate]
  12. How to store int[] array in application Settings
  13. change array size
  14. Fast way to convert a two dimensional array to a List ( one dimensional )
  15. Array Size (Length) in C#
  16. How can I print the contents of an array horizontally?
  17. Checking if a string array contains a value, and if so, getting its position
  18. What is the use of the ArraySegment class?
  19. How to pass a single object[] to a params object[]
  20. How to add a string to a string[] array? There’s no .Add function
  21. C# Cast Entire Array?
  22. List array duplicates with count
  23. Converting jagged array to 2D array C#
  24. Sorting an array related to another array
  25. Why does my C# array lose type sign information when cast to object?
  26. How to sort two arrays by same index?
  27. Why is array co-variance considered so horrible?
  28. byte[] to unsigned BigInteger?
  29. Byte Array to Bitmap Image
  30. array of events in C#?

Leave a Comment