title: Cache-friendly optimization: Object oriented matrix multiplication and in-function tiled matrix multiplication
body: <p>After writing a matrix class that represents whole matrix in two 1D-buffers using  <a href="https://stackoverflow.com/questions/17711686/matrix-accessing-and-multiplication-optimization-for-cpu">this implementation</a> , I've reached the matrix maltiplication part in my project and inclined to some cache-friendly-optimizations now. Stumbled upon two options(question is in lower part of this page):</p>
  
  <p>1)Selecting blocked/tiled sub-matrices just in the multiplication time.</p>
  
  <ul>
  <li>Done in c++ DLL function, so no function overhead.</li>
  <li>Since the code will be more complex, additional optimizations will be harder to apply.</li>
  </ul>
  
  <p>2)Building a matrix class from sub matrix classes(smaller patches) so multiplication is generally done on sub-matrix classes.</p>
  
  <ul>
  <li>Object oriented approach leaves space for additional optimizations for sub-matrices.</li>
  <li>Object headers and padding behavior of C# can help overcome critical strides?</li>
  <li>Function overhead can be a problem after calling it many times instead of a few times.</li>
  </ul>
  
  <p>Example matrix multiplication: C=A.B</p>
  
  <pre><code> A
   1 2 3 4   is used as  1 2    3 4  
   4 3 4 2               4 3    4 2  
   1 3 1 2                           
   1 1 1 2               1 3    1 2  
                         1 1    1 2
  
  
   B
   1 1 1 1  ---&gt;         1 1    1 1
   1 1 1 1               1 1    1 1
   1 1 1 1 
   1 1 1 1               1 1    1 1
                         1 1    1 1
  
  
   Multiplication:       1 2 * 1 1   +   3 4 * 1 1    ==&gt;  upper-left tile of result
                         4 3   1 1       4 2   1 1  
  
  
                         same for the upper-right of result
  
                         1 3 * 1 1   +   1 2 * 1 1    ==&gt; lower left tile of result
                         1 1   1 1       1 2   1 1
  
                         same for lower-right tile of result
  
          Multiplication is O(n³) but summation is O(n²).
  </code></pre>
  
  <p><strong>Question:</strong> Has anyone tried both(functional and object oriented) and made performance comparisons? Right now, my naive multiplication without any of these cache targeted optimizations, takes:</p>
  
  <pre><code> Matrix Size   Single Threaded Time    Multithreaded Time
   * 128x128   :     5    ms                 1ms-5ms(time sample error is bigger)
   * 256x256   :     25   ms                 7     ms
   * 512x512   :     140  ms                 35    ms
   * 1024x1024 :     1.3  s                  260   ms
   * 2048x2048 :     11.3 s                  2700  ms 
   * 4096x4096 :     88.1 s                  24    s
   * 8192x8192 :     710  s                  177   s
  
   Giga-multiplications of variables per second
                 Single threaded         Multithreaded           Multi/single ratio               
   * 128x128   :     0.42                    2.0 - 0.4               ?
   * 256x256   :     0.67                    2.39                   3.67x  
   * 512x512   :     0.96                    3.84                   4.00x
   * 1024x1024 :     0.83                    3.47                   4.18x
   * 2048x2048 :     0.76                    3.18                   4.18x
   * 4096x4096 :     0.78                    2.86                   3.67x
   * 8192x8192 :     0.77                    3.09                   4.01x
  </code></pre>
  
  <p>(average results for 1.4GHz fx8150 with avx-optimized code using 32-bit floats)(c++ avx-intrinsics in dll functions within Parallel.For() of visual studio C#) </p>
  
  <p>Which size of matrices above could be suffered from cache misses, critical strides and other bad things? Do you know how can I get performance counters of those using intrinsics?</p>
  
  <p>Thans for your time.</p>
  
  <p><strong>Edit:</strong> Inlining optimization within DLL:</p>
  
  <pre><code> Matrix Size   Single Threaded Time    Multithreaded Time           Multi/Single radio
   * 128x128   :  1     ms(%400)          390us avrage in 10k iterations(6G mult /s)
   * 256x256   :  12    ms(%108 faster)   2     ms   (%250 faster)         6.0x
   * 512x512   :  73    ms(%92 faster)    15    ms   (%133 faster)         4.9x
   * 1024x1024 :  1060  ms(%22 faster)    176   ms   (%48 faster)          6.0x
   * 2048x2048 :  10070 ms(%12 faster)    2350  ms   (%15 faster)          4.3x
   * 4096x4096 :  82.0  s(%7 faster)      22    s    (%9 faster)           3.7x
   * 8192x8192 :  676   s(%5 faster)      174   s    (%2 faster)           4.1x
  </code></pre>
  
  <p>After the inlining, the shadowed performance of smaller multiplications become visible.
  There is still DLL-function-C# overhead. 1024x1024 case seems to be starting point of cache-misses. While work is increased by only seven times, the execution time is increased to fifteen times.</p>
  
  <p><strong>Edit:</strong>: Going to try Strassen's algorithm for 3-layers deep with object oriented approach this week. Main matrix will be composed of 4 sub matrices. Then they will be composed of 4 sub-subs each. Then they will be composed of 4 sub-sub-subs each. This should give nearly (8/7)<em>(8/7)</em>(8/7)= +%50 speedup. If it works, will convert DLL-function to patch-optimized one which will use more cache.</p>