arrays - right index changes faster??

[DonnaPin]

Hello, I am reviewing arrays, and in my book it says "2D arrays are stored in row - column matrix, where the first index indicates the row and the second indicated the column. This means that when array elements are accessed in the order in which they are actually stored in memory, the right index changes faster than the left"

I am really not understanding why this is, I do not understand why it changes faster. Could someone maybe explain this in another way? I tried looking it up and I have found something talking about row major, and it says the rows change faster. But isnt the left index the rows? If anyone could help with this it would be appreciated.

[Repeater]

Here's an array, 5 rows and 5 columns.

int array[5][5];

Let's access each element, in the order in which they are actually stored in memory.

In memory, array[0][0] is right next to array[0][1], and that is next to array [0][2], and so on.

Let's access each element, in the order in which they are actually stored in memory.

array[0][0];
array[0][1];
array[0][2];
array[0][3];
array[0][4];
array[1][0];
array[1][1];
array[1][2];
array[1][3];
array[1][4];
array[2][0];
array[2][1];
array[2][2];
array[2][3];
array[2][4];
array[3][0];
array[3][1];
array[3][2];
array[3][3];
array[3][4];
array[4][0];
array[4][1];
array[4][2];
array[4][3];
array[4][4];

Do you see how the column number changed EVERY time, but the row number changed a lot less frequently?
Do you see how the column index changed EVERY time, but the row index changed a lot less frequently?
Do you see how the right index changed EVERY time, but the left index changed a lot less frequently?

[DonnaPin]

OK I may have been an idiot with this one. Is it just meaning it is just changing faster with the numbers like you have shown, Ie- the right index numbers change faster than the left. I was assuming it to mean that it had something to do with memory being faster with something to do with columns.

[jonnin]

in a quick nutshell,
IF your data is large, such that a row is bigger than a page of memory (this varies by system, or by processor/OS era) then if you cross that boundary every time in a loop, you are creating excessive page faults and should index it the other way. The simple matrix multiply falls into this trap naturally.
so if you indexed it
a[0][0]
a[1][0]
a[2][0]
style, it will page fault badly on large arrays.

so your instincts about why this matters; for memory access and performance, are spot on.

*The compiler may be smart enough to fix this for some code? Not sure. Best not to trust it on this.

the same issue can be created with 2-d pointers and vectors and other containers.

[seeplus]

the right index numbers change faster than the left

Yes. The column number starts at 0 and increments to no_cols - 1. It then is reset to 0 and the row number is incremented. The column number is then incremented to no_cols - 1, reset to 0, row incremented etc etc while row number is < no_rows.

To access the memory location for a 2-d array (like here) and saying there are n rows and m cols, then if you want to access the location for row r and column c the calculation is

m * r + c

so for the 5x5 matrix, [1][3] gives 8 (1 * 5 + 3)
[2][4] gives 14 (2 * 5 + 4)

[lastchance]

In c/c++ and NumPy arrays in python the rightmost index changes fastest (i.e. at every step in memory). This is row-major order.

In Fortran and Matlab the leftmost index changes fastest. This is column-major order.

Because of cacheing it is fastest to access elements adjacent to each other in memory - so think about the order of nested loops.

If you're doing multi-language programming ... avoid multi-dimensional arrays!

[againtry]

This has now become a joke.
The comment about speed relates to the relative rate of change of the two indices and has nothing to do with all this other claptrap.