# Why column major?

**URL:** <https://discourse.julialang.org/t/why-column-major/24374>\
**Category:** General Usage\
**Tags:** question, array, linearalgebra, column-major\
**Created:** [May 19, 2019, 10:49am UTC](https://discourse.julialang.org/t/why-column-major/24374 "2019-05-19T10:49:56Z")\
**Posts on this page:** 20\
**Page:** 3

<div class="post-metadata">

**Author:** ![Nathan\_Boyer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nathan_boyer/32/14825_2.png) [@Nathan\_Boyer](https://discourse.julialang.org/u/Nathan_Boyer)\
**Post date:** [August 31, 2021, 6:37pm UTC](https://discourse.julialang.org/t/why-column-major/24374/41 "2021-08-31T18:37:54Z")

</div>

Thanks @lmiq. I’ll use your framework to attempt to answer my own question, though I still don’t understand some of the weirdness illustrated by OP.

```julia
using BenchmarkTools

"""
Innermost loop is performed first.
Remember "Run first over first index."
Higher dimensions should appear last in indexing and as the topmost `for` loop.
"""
function update_fast1!(A)
    for k in axes(A,3) 
       for j in axes(A,2) 
           for i in axes(A,1)
              A[i,j,k] = A[i,j,k] - 1.0
           end
       end
    end
 end

 "Reverse iteration is slower."
 function update_slow1!(A)
    for i in axes(A,1) 
       for j in axes(A,2) 
           for k in axes(A,3)
              A[i,j,k] = A[i,j,k] - 1.0
          end
       end
    end
 end

"""
One-line nested for loops unroll as though you are reading them from top to bottom.
The last loop listed is performed first.
"""
function update_fast2!(A)
    for k in axes(A,3), j in axes(A,2), i in axes(A,1)
        A[i,j,k] = A[i,j,k] - 1.0
    end
end

"Reverse iteration is slower."
function update_slow2!(A)
    for i in axes(A,1), j in axes(A,2), k in axes(A,3)
        A[i,j,k] = A[i,j,k] - 1.0
    end
end

"""
For some reason, inside an array comprehension, the reversed order is faster.
The first loop listed is performed first.
"""
function create_fast1(A)
    B = [A[i,j,k] + 1.0 for i in axes(A,1), j in axes(A,2), k in axes(A,3)]
end

"The order from `update_fast2!` is slow in this case."
function create_slow1(A)
    B = [A[i,j,k] + 1.0 for k in axes(A,3), j in axes(A,2), i in axes(A,1)]
end

"Here the original `update_fast2!` order is fast again, but the result is a `Vector` not a 3D `Array`."
function create_fast2(A)
    B = [A[i,j,k] + 1.0 for k in axes(A,3) for j in axes(A,2) for i in axes(A,1)]
end

"Reverse order is slower. Again result is a `Vector`."
function create_slow2(A)
    B = [A[i,j,k] + 1.0 for i in axes(A,1) for j in axes(A,2) for k in axes(A,3)]
end

```

```julia
julia> A = rand(500, 500, 500);

julia> @btime update_fast1!($A);
  68.297 ms (0 allocations: 0 bytes)

julia> @btime update_slow1!($A);
  3.781 s (0 allocations: 0 bytes)

julia> @btime update_fast2!($A);
  67.938 ms (0 allocations: 0 bytes)

julia> @btime update_slow2!($A);
  3.710 s (0 allocations: 0 bytes)

julia> @btime create_fast1($A);
  275.710 ms (2 allocations: 953.67 MiB)

julia> @btime create_slow1($A);
  2.683 s (2 allocations: 953.67 MiB)

julia> @btime create_fast2($A);
  1.191 s (29 allocations: 1.14 GiB)

julia> @btime create_slow2($A);
  7.202 s (29 allocations: 1.14 GiB)

```

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [August 31, 2021, 6:55pm UTC](https://discourse.julialang.org/t/why-column-major/24374/42 "2021-08-31T18:55:57Z")

</div>

> [@Nathan\_Boyer](#):
>
> ```julia
> For some reason, inside an array comprehension, the reversed order is faster.
> The first loop listed is performed first.
> 
> ```

If rules to remember is what is needed, remember that what is being iterated first is what is closer to the expression being evaluated.

IMO, it is not completely unnatural that in

```julia
[A[i,j,k] + 1.0 for i in axes(A,1), for j in axes(A,2), for k in axes(A,3)]

```

the first thing being iterated is `for i in axes(A,1)`.

but I guess one also gets accustomed by that.

Then if you remove the commas you are doing a different thing, which is building an iterator product to create a vector. Then I agree that what is fast or not can be strange, seems to be that there is an arbitrary choice there. To be truth I never used (and probably never will use) that syntax.

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [August 31, 2021, 6:57pm UTC](https://discourse.julialang.org/t/why-column-major/24374/43 "2021-08-31T18:57:56Z")

</div>

Yeah, I think the awkward ordering of `[(i, j) for i in 1:2 for j in 1:3]` is just left over from Python, from which this particular syntax originated.

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [August 31, 2021, 7:02pm UTC](https://discourse.julialang.org/t/why-column-major/24374/44 "2021-08-31T19:02:10Z")

</div>

As a performance comment, there are two primary aspects.  
One is SIMD, which we won’t get in the examples that don’t have `@inbounds`.

The others are memory related.  
Memory is fetched one cache-line at a time. Most CPUs today have 64 byte cachelines. The Apple M1 has 128 byte cachelines, and the Fujitsu A64FX has 256 byte cachelines.

Cachelines are contiguous. A 64 byte cacheline contains `8` `Float64`.  
So if you’re iterating across columns, you’re only using 1/8 of the `Float64`s fetched from memory. If the arrays are large enough, that cacheline will be evicted before it comes time to use another element from it, meaning you need to fetch it again.  
Hence, you can expect an 8x performance difference.

Another factor is that the prefetchers have an easier time with contiguous memory accesses.  
There is also a strided prefetcher, but it requires relatively small strides and won’t prefetch across pages, and if you’re going across columns of large arrays, you’re probably iterating across pages relatively rapidly, too. Do that too much, and you’ll also run out of TLB entries, and need to start computing address translations for the mapping of virtual memory to hardware.

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [August 31, 2021, 7:08pm UTC](https://discourse.julialang.org/t/why-column-major/24374/45 "2021-08-31T19:08:04Z")

</div>

While this is interesting I don’t see how any of this is different if one has column-major vs. row-major ordering?

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [August 31, 2021, 7:08pm UTC](https://discourse.julialang.org/t/why-column-major/24374/46 "2021-08-31T19:08:27Z")

</div>

It is not. I was just making a comment on the consequences of accessing data in the wrong order.

---

<div class="post-metadata">

**Author:** ![Nathan\_Boyer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nathan_boyer/32/14825_2.png) [@Nathan\_Boyer](https://discourse.julialang.org/u/Nathan_Boyer)\
**Post date:** [August 31, 2021, 7:11pm UTC](https://discourse.julialang.org/t/why-column-major/24374/47 "2021-08-31T19:11:50Z")

</div>

That is a great way to remember it!  
_Iterator closest to the expression is evaluated first._

I can probably also safely ignore the last use case, since I don’t really understand what it does anyway.

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [August 31, 2021, 7:13pm UTC](https://discourse.julialang.org/t/why-column-major/24374/48 "2021-08-31T19:13:42Z")

</div>

> [@Nathan\_Boyer](#):
>
> _Iterator closest to the expression is evaluated first._

Actually, note that while in:

```julia
[A[i,j,k] + 1.0 for i in axes(A,1), j in axes(A,2), k in axes(A,3)]

```

the `i` index moves faster, in

```julia
[A[i,j,k] + 1.0 for i in axes(A,1) for j in axes(A,2) for k in axes(A,3)]

```

the opposite is true, with `k` moving faster.

So it’s not always true that the iterator closest to the expression is evaluated first.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [August 31, 2021, 7:14pm UTC](https://discourse.julialang.org/t/why-column-major/24374/49 "2021-08-31T19:14:45Z")

</div>

> [@Nathan\_Boyer](#):
>
> I can probably also safely ignore the last use case, since I don’t really understand what it does anyway.

That has been my approach so far (not necessarily consciously, since I never used that other syntax).

---

<div class="post-metadata">

**Author:** ![Nathan\_Boyer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nathan_boyer/32/14825_2.png) [@Nathan\_Boyer](https://discourse.julialang.org/u/Nathan_Boyer)\
**Post date:** [August 31, 2021, 7:25pm UTC](https://discourse.julialang.org/t/why-column-major/24374/50 "2021-08-31T19:25:17Z")

</div>

> [@e3c6](#):
>
> So it’s not always true that the iterator closest to the expression is evaluated first.

Yes, that last case breaks the rule (apparently because of Python). Good to highlight the inconsistency, but I don’t think most people need that syntax.

> [@rdeits](#):
>
> Yeah, I think the awkward ordering of `[(i, j) for i in 1:2 for j in 1:3]` is just left over from Python, from which this particular syntax originated.

---

<div class="post-metadata">

**Author:** ![Nathan\_Boyer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nathan_boyer/32/14825_2.png) [@Nathan\_Boyer](https://discourse.julialang.org/u/Nathan_Boyer)\
**Post date:** [August 31, 2021, 7:33pm UTC](https://discourse.julialang.org/t/why-column-major/24374/51 "2021-08-31T19:33:43Z")

</div>

“_Inside out_” might also be a useful way to remember.

Although that’s maybe not as obvious in the second case:

> [@Nathan\_Boyer](#):
>
> ```julia
> function update_fast2!(A)
> for k in axes(A,3), j in axes(A,2), i in axes(A,1)
> A[i,j,k] = A[i,j,k] - 1.0
> end
> end
> 
> ```

---

<div class="post-metadata">

**Author:** ![dlfivefifty](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dlfivefifty/32/1959_2.png) [@dlfivefifty](https://discourse.julialang.org/u/dlfivefifty)\
**Post date:** [August 31, 2021, 8:05pm UTC](https://discourse.julialang.org/t/why-column-major/24374/52 "2021-08-31T20:05:31Z")

</div>

FYI One place where row major is faster is lazy matrix-vector multiplication `getindex`:

```julia
julia> n = 20_000; A = randn(n,n); b = randn(n);

julia> @time ApplyVector(*, A, b)[100]
  0.004955 seconds (27 allocations: 2.188 KiB)
180.974127516603

julia> @time ApplyVector(*, A', b)[100]
  0.000492 seconds (31 allocations: 2.250 KiB)
-50.2513375406383

```

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [August 31, 2021, 11:52pm UTC](https://discourse.julialang.org/t/why-column-major/24374/53 "2021-08-31T23:52:22Z")

</div>

Do you have an explanation for this?

---

<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:** [September 1, 2021, 1:02am UTC](https://discourse.julialang.org/t/why-column-major/24374/54 "2021-09-01T01:02:31Z")

</div>

[Cache locality](https://en.wikipedia.org/wiki/Locality_of_reference) (specifically spatial locality, i.e. cache-line utilization). You are essentially computing `dot(@view(A[i, :]), b)`, which is faster if `A[i, :]` is contiguous in memory (i.e. if `A` is row-major).

---

<div class="post-metadata">

**Author:** ![Astlaan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/astlaan/32/45420_2.png) [@Astlaan](https://discourse.julialang.org/u/Astlaan)\
**Post date:** [December 27, 2022, 7:29pm UTC](https://discourse.julialang.org/t/why-column-major/24374/55 "2022-12-27T19:29:46Z")

</div>

Another interesting example are integrations.

In the case of multiple integrations (ex. triple integrals), we usually think of the “fastest” as the last (rightmost) index.

---

<div class="post-metadata">

**Author:** ![ParadaCarleton](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/paradacarleton/32/20005_2.png) [@ParadaCarleton](https://discourse.julialang.org/u/ParadaCarleton)\
**Post date:** [December 30, 2022, 12:50am UTC](https://discourse.julialang.org/t/why-column-major/24374/56 "2022-12-30T00:50:03Z")

</div>

Don’t you mean leftmost? When you integrate `f(x, y, z) dx dy dz` you start by integrating (“iterating” over) x, then over y, then z.

Actually, thank you for bringing this up, I think this is how I’ll finally be able to remember how Julia iterates over an array.

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [December 30, 2022, 6:31am UTC](https://discourse.julialang.org/t/why-column-major/24374/57 "2022-12-30T06:31:26Z")

</div>

[C++23](https://en.cppreference.com/w/cpp/header/mdspan) actually refers to column and row major as “layout\_left” and “layout\_right”, respectively.

---

<div class="post-metadata">

**Author:** ![mtd](https://avatars.discourse-cdn.com/v4/letter/m/ee59a6/32.png) [@mtd](https://discourse.julialang.org/u/mtd)\
**Post date:** [February 17, 2024, 1:50am UTC](https://discourse.julialang.org/t/why-column-major/24374/58 "2024-02-17T01:50:10Z")

</div>

Re “surprising”

> [@e3c6](#):
>
> makes `[... for i=1:5, j=1:5]` different from `for i=1:5 for j=1:5`. The difference is not just that the later is linearized, but also the order in which elements are traversed

A mnemonic that might help with this is to visualize that in both forms, the lexically “inside” variable (eg the first variable `i` in the tail of the generator expression, or the second variable `j` in head of the statement form) forms the inner loop and varies fastest.

---

<div class="post-metadata">

**Author:** ![lmtzx9h4qqnt](https://avatars.discourse-cdn.com/v4/letter/l/74df32/32.png) [@lmtzx9h4qqnt](https://discourse.julialang.org/u/lmtzx9h4qqnt)\
**Post date:** [February 17, 2024, 2:47am UTC](https://discourse.julialang.org/t/why-column-major/24374/59 "2024-02-17T02:47:13Z")

</div>

How is one supposed to tell that `i` is lexically “inside” in `for i=1:5, j=1:5`, though? Especially since the behavior for the other version is the opposite:

```julia
[... for i=1:5, j=1:5]
[... for i=1:5 for j=1:5]

```

I don’t see how the syntax would allow you to tell the difference here.

---

<div class="post-metadata">

**Author:** ![mtd](https://avatars.discourse-cdn.com/v4/letter/m/ee59a6/32.png) [@mtd](https://discourse.julialang.org/u/mtd)\
**Post date:** [February 17, 2024, 11:31pm UTC](https://discourse.julialang.org/t/why-column-major/24374/60 "2024-02-17T23:31:03Z")

</div>

> [@lmtzx9h4qqnt](#):
>
> How is one supposed to tell that `i` is lexically “inside” … Especially since the behavior for the other version is the opposite

eek I wasn’t aware of that last form (4 below), which my mnemonic fails for. Color me surprised! Thanks for setting me straight, and sorry to derail old topic.

```julia
for i=1:2, j=3:4; f(i, j) end # (1) i lexically outside, controls outer loop
for i=1:2 for j=3:4; f(i, j) end end # (2) i lexically outside, controls outer loop
[f(i, j) for i=1:2, j=3:4]; # (3) i lexically inside, controls inner loop
[f(i, j) for i=1:2 for j=3:4]; # (4) i lexically inside, controls outer loop

```

[Previous page](https://discourse.julialang.org/t/why-column-major/24374.md?page=2)