# How row-major-matrix format would have a better run-time performance?

**URL:** <https://discourse.julialang.org/t/how-row-major-matrix-format-would-have-a-better-run-time-performance/20092>\
**Category:** General Usage\
**Created:** [January 25, 2019, 1:53pm UTC](https://discourse.julialang.org/t/how-row-major-matrix-format-would-have-a-better-run-time-performance/20092 "2019-01-25T13:53:56Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![bsnyh](https://avatars.discourse-cdn.com/v4/letter/b/ce7236/32.png) [@bsnyh](https://discourse.julialang.org/u/bsnyh)\
**Post date:** [January 25, 2019, 1:53pm UTC](https://discourse.julialang.org/t/how-row-major-matrix-format-would-have-a-better-run-time-performance/20092/1 "2019-01-25T13:53:56Z")

</div>

Hi, I’m interested in the Dijkstra algorithm to find the shortest path. [http://juliagraphs.github.io/LightGraphs.jl/latest/pathing.html#LightGraphs.dijkstra\_shortest\_paths](http://juliagraphs.github.io/LightGraphs.jl/latest/pathing.html#LightGraphs.dijkstra_shortest_paths) When I was reading the documentation, I found that it has mentioned  
" Use a matrix type for `distmx` that is implemented in [row-major matrix format](https://en.wikipedia.org/wiki/Row-_and_column-major_order) for better run-time." Why row-major matrix implementation would give a better performance then?

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [January 25, 2019, 2:03pm UTC](https://discourse.julialang.org/t/how-row-major-matrix-format-would-have-a-better-run-time-performance/20092/2 "2019-01-25T14:03:16Z")

</div>

> [@bsnyh](#):
>
> " Use a matrix type for `distmx` that is implemented in [row-major matrix format](https://en.wikipedia.org/wiki/Row-_and_column-major_order) for better run-time." Why row-major matrix implementation would give a better performance then?

Because they wrote their algorithm in a way that iterates down rows instead of columns. It should just be switched and there would be no performance difference if the algorithm is correctly changed. Indexing is all an abstraction over linear memory.

---

<div class="post-metadata">

**Author:** ![bsnyh](https://avatars.discourse-cdn.com/v4/letter/b/ce7236/32.png) [@bsnyh](https://discourse.julialang.org/u/bsnyh)\
**Post date:** [January 25, 2019, 2:25pm UTC](https://discourse.julialang.org/t/how-row-major-matrix-format-would-have-a-better-run-time-performance/20092/3 "2019-01-25T14:25:38Z")

</div>

@ChrisRackauckas, I’m not sure I understand that

> “there would be no performance difference if the algorithm is correctly changed”

Moreover, the `distmx` is a symmetric matrix in this case. So, are there anything which can be done with respect to this?

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [January 25, 2019, 8:03pm UTC](https://discourse.julialang.org/t/how-row-major-matrix-format-would-have-a-better-run-time-performance/20092/4 "2019-01-25T20:03:07Z")

</div>

The `distmx` is only symmetric for undirected graphs.

To answer your original question, the documentation isn’t quite accurate. The distance matrix is a matrix `A` such that `A[i, j]` is the weight associated with the edge _from_ `i` _to_ `j`. We will correct the documentation so that it’s clearer.

(That said, have a look at [https://github.com/JuliaGraphs/LightGraphs.jl/pull/920](https://github.com/JuliaGraphs/LightGraphs.jl/pull/920) for some history.)

---

<div class="post-metadata">

**Author:** ![bsnyh](https://avatars.discourse-cdn.com/v4/letter/b/ce7236/32.png) [@bsnyh](https://discourse.julialang.org/u/bsnyh)\
**Post date:** [January 25, 2019, 8:48pm UTC](https://discourse.julialang.org/t/how-row-major-matrix-format-would-have-a-better-run-time-performance/20092/5 "2019-01-25T20:48:46Z")

</div>

@anon94023334, I’m just saying I do not quite understand why using a row major matrix format would be more efficient. I did not see the logic, and got very confused. Thank you so much for your kindness.

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [January 25, 2019, 8:51pm UTC](https://discourse.julialang.org/t/how-row-major-matrix-format-would-have-a-better-run-time-performance/20092/6 "2019-01-25T20:51:03Z")

</div>

No worries. You would likely get better answers in the slack channel, though. I admit this question threw me for a loop since I didn’t recall why we made the decision we did.

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [January 25, 2019, 10:08pm UTC](https://discourse.julialang.org/t/how-row-major-matrix-format-would-have-a-better-run-time-performance/20092/7 "2019-01-25T22:08:51Z")

</div>

Ref: [https://github.com/JuliaGraphs/LightGraphs.jl/pull/1120](https://github.com/JuliaGraphs/LightGraphs.jl/pull/1120)