# <span class='text-muted'>049.</span> Fortran is column-major

<span style='font-size: small;' class='text-muted'>topic: {ref}`arrays`</span>

The order you loop through multidimensional arrays can have a big impact on speed.
Fortran is [column-major](https://en.wikipedia.org/wiki/Row-_and_column-major_order),
meaning consecutive elements of a column are stored next to each other in memory,
and you should loop through arrays in this order.

```{literalinclude} ../../src/column-major.f90
:language: fortran
:caption: column-major.f90 | <a href="https://github.com/zmoon/FortranTipBrowser/blob/main/src/column-major.f90" target="_blank" title="See this source on GitHub"><i class="fab fa-github"></i></a> | <a href="https://github.com/Beliavsky/FortranTip/blob/main/column_major.f90" target="_blank" title="See the original source on Beliavsky/FortranTip GitHub"><i class="fab fa-github"></i><sub>0</sub></a> | <a href="https://godbolt.org/#g:!((g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:fortran,selection:(endColumn:1,endLineNumber:36,positionColumn:1,positionLineNumber:36,selectionStartColumn:1,selectionStartLineNumber:36,startColumn:1,startLineNumber:36),source:'program+column_major%0A+++use+iso_fortran_env,+only:+wp+%3D%3E+real64,+int64%0A%0A+++integer,+parameter+::+m+%3D+10000,+n+%3D+m%0A+++integer+::+array(m,+n)%0A+++integer+::+i,+j,+tot%0A+++integer(int64)+::+irate,+tic,+toc%0A%0A+++call+system_clock(count_rate%3Dirate)++!!+%23+of+clock+ticks+per+second%0A+++array+%3D+0%0A%0A+++!!+FASTER:+Looping+consecutively+through+columns%0A+++call+system_clock(count%3Dtic)%0A+++tot+%3D+0%0A+++do+j+%3D+1,+size(array,+dim%3D2)%0A++++++do+i+%3D+1,+size(array,+dim%3D1)%0A+++++++++!!+Do+something+with+array(i,+j)%0A+++++++++tot+%3D+tot+%2B+array(i,+j)%0A++++++end+do%0A+++end+do%0A+++call+system_clock(count%3Dtoc)%0A+++print+%22(g12.3)%22,+(toc+-+tic)+/+real(irate,+wp)%0A%0A+++!!+SLOWER:+Looping+consecutively+through+rows%0A+++call+system_clock(count%3Dtic)%0A+++tot+%3D+0%0A+++do+i+%3D+1,+size(array,+dim%3D1)%0A++++++do+j+%3D+1,+size(array,+dim%3D2)%0A+++++++++!!+Do+something+with+array(i,+j)%0A+++++++++tot+%3D+tot+%2B+array(i,+j)%0A++++++end+do%0A+++end+do%0A+++call+system_clock(count%3Dtoc)%0A+++print+%22(g12.3)%22,+(toc+-+tic)+/+real(irate,+wp)%0A%0Aend+program%0A'),l:'5',n:'0',o:'Fortran+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:gfortran112,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'0',intel:'0',libraryCode:'0',trim:'1'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:fortran,libs:!(),options:'',selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1,tree:'1'),l:'5',n:'0',o:'x86-64+gfortran+11.2+(Fortran,+Editor+%231,+Compiler+%231)',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',m:62.300683371298405,n:'0',o:'',t:'0'),(g:!((h:output,i:(compiler:1,editor:1,fontScale:14,fontUsePx:'0',tree:'1',wrap:'1'),l:'5',n:'0',o:'Output+of+x86-64+gfortran+11.2+(Compiler+%231)',t:'0')),header:(),l:'4',m:37.699316628701595,n:'0',o:'',s:0,t:'0')),l:'3',n:'0',o:'',t:'0')),version:4" target="_blank" title="Open in Godbolt Compiler Explorer"><img src="https://raw.githubusercontent.com/compiler-explorer/compiler-explorer/main/views/resources/site-logo.svg" alt="Godbolt Compiler Explorer logo" width="55.11" height="16.7" class="align-text-bottom" /></a> | <a href="https://play.fortran-lang.org/?code=program%20column_major%0A%20%20%20use%20iso_fortran_env%2C%20only%3A%20wp%20%3D%3E%20real64%2C%20int64%0A%0A%20%20%20integer%2C%20parameter%20%3A%3A%20m%20%3D%2010000%2C%20n%20%3D%20m%0A%20%20%20integer%20%3A%3A%20array%28m%2C%20n%29%0A%20%20%20integer%20%3A%3A%20i%2C%20j%2C%20tot%0A%20%20%20integer%28int64%29%20%3A%3A%20irate%2C%20tic%2C%20toc%0A%0A%20%20%20call%20system_clock%28count_rate%3Dirate%29%20%20%21%20%23%20of%20clock%20ticks%20per%20second%0A%20%20%20array%20%3D%200%0A%0A%20%20%20%21%20FASTER%3A%20Looping%20consecutively%20through%20columns%0A%20%20%20call%20system_clock%28count%3Dtic%29%0A%20%20%20tot%20%3D%200%0A%20%20%20do%20j%20%3D%201%2C%20size%28array%2C%20dim%3D2%29%0A%20%20%20%20%20%20do%20i%20%3D%201%2C%20size%28array%2C%20dim%3D1%29%0A%20%20%20%20%20%20%20%20%20%21%20Do%20something%20with%20array%28i%2C%20j%29%0A%20%20%20%20%20%20%20%20%20tot%20%3D%20tot%20%2B%20array%28i%2C%20j%29%0A%20%20%20%20%20%20end%20do%0A%20%20%20end%20do%0A%20%20%20call%20system_clock%28count%3Dtoc%29%0A%20%20%20print%20%22%28g12.3%29%22%2C%20%28toc%20-%20tic%29%20/%20real%28irate%2C%20wp%29%0A%0A%20%20%20%21%20SLOWER%3A%20Looping%20consecutively%20through%20rows%0A%20%20%20call%20system_clock%28count%3Dtic%29%0A%20%20%20tot%20%3D%200%0A%20%20%20do%20i%20%3D%201%2C%20size%28array%2C%20dim%3D1%29%0A%20%20%20%20%20%20do%20j%20%3D%201%2C%20size%28array%2C%20dim%3D2%29%0A%20%20%20%20%20%20%20%20%20%21%20Do%20something%20with%20array%28i%2C%20j%29%0A%20%20%20%20%20%20%20%20%20tot%20%3D%20tot%20%2B%20array%28i%2C%20j%29%0A%20%20%20%20%20%20end%20do%0A%20%20%20end%20do%0A%20%20%20call%20system_clock%28count%3Dtoc%29%0A%20%20%20print%20%22%28g12.3%29%22%2C%20%28toc%20-%20tic%29%20/%20real%28irate%2C%20wp%29%0A%0Aend%20program%0A" target="_blank" title="Open in Fortran Playground"><img src="https://raw.githubusercontent.com/fortran-lang/playground/main/frontend/src/fortran-logo.png" alt="Fortran logo" height="15.5" class="align-text-bottom" /></a>
```

```{code-block} text
:caption: Output[^gfortran-version]

   0.225    
   0.398    

```

[^gfortran-version]: Compiled using `GNU Fortran (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0` with no flags

Another way to think about this is to say that
the first (leftmost) index ($i$) varies fastest when considering all elements of the array in storage order,
as illustrated [here](https://en.wikipedia.org/wiki/File:Row_and_column_major_order.svg),
so you want that to be the innermost loop.
The last (rightmost) index ($j$ in 2-D), varies slowest, so we want this to be our outermost loop.

```{tip}
Different languages use different storage.
For example, C is row-major, and this is what NumPy uses by default.
Want NumPy arrays to be stored Fortran-style (column-major) instead?
Specify `order='F'` when creating arrays!
```

```{note}
Although Fortran's array *storage* order is column-*major*,
semantically we still refer to the first dimension
(`dim=1` in the above program, first index (`i`) in the `array(i, j)` indexing)
as the row dimension (with index $i$).
```

```{note}
This idea extends to arrays with more than two dimensions.
In general, the loop nesting order for fastest access will be
*last dimension* $\to \ldots \to$ *first dimension*,
as shown [here](https://fortran-lang.org/en/learn/best_practices/multidim_arrays/).
Also, the 1-D slice `arr(:, 1, 1, ..., 1)` is contiguous,
like the column slice `arr(:, 1)` is for 2-D arrays.
```

Some further references:
* <https://fortran-lang.org/en/learn/best_practices/multidim_arrays/>
* <https://eli.thegreenplace.net/2015/memory-layout-of-multi-dimensional-arrays>

---

<blockquote class="twitter-tweet"><p lang="en" dir="ltr">The order you loop through multidimensional arrays can have a big impact on speed. Fortran is column-major, meaning consecutive elements of a column are stored next to each other in memory, and you should loop through arrays in this order. <a href="https://t.co/oEtrOaMbzC">pic.twitter.com/oEtrOaMbzC</a></p>&mdash; FortranTip (@fortrantip) <a href="https://twitter.com/fortrantip/status/1475049356155883524?ref_src=twsrc%5Etfw">December 26, 2021</a></blockquote><script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>