# What are the pros and cons of row/column major ordering?

**URL:** https://discourse.julialang.org/t/what-are-the-pros-and-cons-of-row-column-major-ordering/110045
**Category:** Internals & Design
**Tags:** arrays, column-major, row-major
**Created:** [February 10, 2024, 8:38pm UTC](https://discourse.julialang.org/t/what-are-the-pros-and-cons-of-row-column-major-ordering/110045 "2024-02-10T20:38:39Z")
**Posts on this page:** 1
**Showing post:** 4

<div class="post-metadata">

### Author: ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [February 10, 2024, 9:44pm UTC](https://discourse.julialang.org/t/what-are-the-pros-and-cons-of-row-column-major-ordering/110045/4 "2024-02-10T21:44:36Z")

</div>

> [@mstewart](#):
>
> The first one is cache-friendly for row-major order and the second is cache-friendly for column-major order.

That’s true for matrix–vector multiplication, but for matrix–matrix multiplication, both are cache-unfriendly.

Above, you are only talking about spatial locality (consecutive access), but to optimize matrix–matrix multiplication for cache you mainly need to think about temporal locality (re-using a number multiple times once it is in cache). The problem with either rows-times-columns or columns-times-rows is that it does O(1) work per cache miss, regardless of the storage format.

To optimize temporal locality, you need to multiply the matrices by submatrix blocks, roughly \sim \sqrt{Z} \times \sqrt{Z} blocks for a cache that holds Z elements. That way, you load a block into cache (Z cache misses) and then do O(Z^{3/2}) work for the block multiplication. This does O(\sqrt{Z}) work per cache miss, which allows you to completely mask the memory latency and (roughly) hit the peak flop rate of the CPU.

See also the analysis in [this paper](https://people.cs.umass.edu/~emery/classes/cmpsci691s-fall2004/papers/cache-oblivious-algorithms-extended.pdf), or [this Julia notebook from my course notes](https://github.com/mitmath/18335/blob/spring21/notes/Memory-and-Matrices.ipynb) with some experiments. The MIT course [6.172](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2018/) has two free lecture videos ([first](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2018/lecture-videos/lecture-14-caching-and-cache-efficient-algorithms/) and [second](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2018/lecture-videos/lecture-15-cache-oblivious-algorithms/)) on cache-efficient algorithms, including a discussion of matrix multiplication.

> [@leespen1](#):
>
> Doesn’t this mean that column-major ordering makes matrix multiplication less cache-friendly?

The upshot is that, for highly optimized matrix-multiplication algorithms, there probably isn’t much difference between multiplying two row-major vs. two column-major matrices, or either one by a vector.

> [@leespen1](#):
>
> What is less clear to me is why one would want to store matrices in column major order in the first place.

See the discussion: [Why column major?](https://discourse.julialang.org/t/why-column-major/24374)

---

_[View the full topic](https://discourse.julialang.org/t/what-are-the-pros-and-cons-of-row-column-major-ordering/110045)._