When adding two 2D matrices of the same size (in row major format), in sequential code with no vector operations, is it faster to add them column by column or row by row?

At first I thought it would be faster to add them row by row, but now I'm thinking it would be faster to add them column by column. If you have the following:

for i = 0 until rows do
    result[i, :] = add(left[i, :], right[i, :])

When left[i, 0] is accessed, (some of) the remainder of the row is loaded in the CPU cache. This will speed up memory access on that row, but the other rows aren't yet loaded into the cache. However, if you have:

for i = 0 until columns do
    result[:, i] = add(left[:, i], right[:, i])

The first call to add() will load multiple rows into the cache. So this should be faster, right? Am I missing something?

  • 1
    $\begingroup$ This depends on the memory layout, cache size, matrix size; but generally I would expect the first one to be faster, because the memory access pattern is more predicable and even if multiple rows are loaded in the second case, not all necessarily fit in the primary cache, however in the first case one row will probably fit in the primary cache, so less lookups into higher order caches are required. You should test this experimentally. $\endgroup$
    – plshelp
    Commented Feb 8, 2023 at 21:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.