Two Loads Or Three

Two orderings of the same $n \times n$ double-precision matrix multiply. Cache blocks hold four 8-byte doubles, and $n$ is large enough that a full row does not stay resident.

/* A */ for (i=0;i<n;i++) for (j=0;j<n;j++) { s=0;
            for (k=0;k<n;k++) s += A[i][k]*B[k][j];
            C[i][j] += s; }

/* B */ for (k=0;k<n;k++) for (i=0;i<n;i++) { r=A[i][k];
            for (j=0;j<n;j++) C[i][j] += r*B[k][j]; }

A's inner loop does 2 loads and 0 stores. B's does 2 loads and 1 store. Which is faster for large $n$ ?

A, because accumulating into the register s keeps C out of the inner loop entirely, and that is the dominant cost.

B, by a wide margin. Its inner loop walks B and C with stride 1, missing 0.25 times each per iteration, while A walks a column of B with stride $n$ and misses on every access, for 1.25 total.

A, because it performs one fewer memory operation per iteration and both versions do the same $n^3$ multiplies.

Identical. Both are $\Theta(n^3)$ , and loop order changes no arithmetic.