Are there absolute reasons to prefer row/column-major memory ordering?

Question

I've heard it said that "fortran uses column-major ordering because it's faster" but I'm not sure that's true. Certainly, matching column-major data to a column-major implementation will outperform a mixed setup, but I'm curious if there's any absolute reason to prefer row- or column-major ordering. To illustrate the idea, consider the following thought experiment experiment about three of the most common (mathematical) array operations:

Vector-vector inner products

We want to compute the inner product between two equivalent-length vectors, a and b: $$ b = \sum_i a_i x_i. $$ In this case, both a and b are "flat"/one-dimensional and accessed sequentially, so there's really no row- or column-major consideration.

Conclusion: Memory ordering doesn't matter.

Matrix-vector inner products

$$ b_i = \sum_j A_{ij} x_j $$

The naive multiplication algorithm traverses "across" A and "down" x. Again, x is already flat so sequential elements are always adjacent, but adjacent elements in A's rows are most often accessed together (and I suspect this is likely true for more sophisticated multiplication algorithms like the Strassen or Coppersmith-Winograd algorithms).

Conclusion: Row-major ordering is preferred.

(If you let vectors have transposes you can define a left-multiplication of matrices, $x^T A$, in which case column-major does become preferable, but I think it's conceptually simpler to keep vectors transposeless and define this as $A^T x$.)

Matrix-matrix inner products

$$ B_{ik} = \sum_{j} A_{ij} X_{jk} $$

One more time, the schoolbook algorithm traverses across A and down X, so one of those traversals will always be misaligned with the memory layout.

Conclusion: Memory ordering doesn't matter.

Additional consideration: strings & text

ASCII (or similar) strings are most frequently read across-and-down. There's a lot more to consider since a multidimensional array of characters could be ragged (different length rows, e.g. in storing the lines of a book), but the usual traversal pattern at least suggests a preference for row-major ordering.

Conclusion: Row-major ordering is preferred.

---

Of course, this analysis is extremely crude and theoretical, but it at least suggests row-major ordering is a little more "natural" (from a performance perspective) for multidimensional arrays. Does this stand up to real-world examination? Are there any similar analyses that lean the opposite way and suggest an absolute advantage to column-major ordering?

Answer 1

Whether row-major or column-major order is more efficient, depends on the storage access patterns of a specific application.

The underlying principle of computing is that accessing storage in sequential locations tends to be the most efficient pattern possible, whereas accessing storage at disparate locations incurs an overhead in seeking to the data on each iteration, so organising the storage to suit the typical algorithms performed on the data by a particular application, can result in a performance gain.

It's also worth considering what we mean by rows and columns. By a "row" we typically mean a set of fields that relate to one logical/conceptual entity - a row contains fields (in a hierarchical relationship). By a "column", we typically mean a set of fields that share a common meaning or type, but where each field relates to separate logical/conceptual entities - a column is a cross-cut of fields taken from multiple logical entities.

I suspect row-major ordering tends more often to be the default, because it is more common for algorithms to want to access the related fields of the same logical entity at once, than it is for them to want to access fields with the same meaning but across different entities at once.

I suspect also, given the definition of rows and columns above, that row-major aligns with how programmers are most readily inclined to think about accessing data - it's most likely to accord with their mental model of how data is organised. Deviating to column-major is something you then do for a specific performance or algorithmic reason, not by default.

Answer 2

Similar answer to that of Steve.

The most appropriate storage order depends on the traversal patterns. But the programmer has some freedom to optimize the pattern in a way that is cache-friendly.

E.g. a matrix-vector multiply can be implemented as

• clear all $b_r$,

• loop on the matrix rows:

  • loop on the matrix columns:

    • accumulate $A_{rc}x_c$ to $b_r$.

or

• clear all $b_r$,

• loop on the matrix columns:

  • loop on the matrix rows:

    • accumulate $A_{rc}x_r$ to $b_c$.

These two versions trade vector cache-friendly accesses for matrix cache-friendly ones. For matrix-matrix products, there are yet more options.

---

In full-fledges linear algebra libraries, the access patterns are so numerous and varied that every use case might have a differently affinity for one storage order or the other, and an absolute preference is impossible.

Answer 3

The fact is that with current computer hardware, the time to access one cache line (often as large 64 byte) of consecutive bytes is practically the same as the time to access a single word (say 8 bytes) in a cache line, so it is much more efficient to access items that are stored in consecutive memory positions. And accessing items that are say exactly 4,096 bytes apart can be especially inefficient.

Many languages don't support two-dimensional arrays, they support arrays of arrays instead. The first index will specify a subarray. The second index will specify an element within that subarray. Since any objects (including arrays) are stored consecutively, changing the second index will access consecutive items in memory; changing the first index will access items far apart.

(I have seen hardware that actually cached small squares or rectangles in one cache line. So accessing diagonal elements, or more importantly small triangles of data, required fewer cache lines. This required an allocator that would allocate rectangular data)