matrix - Representation of multi-dimensional arrays in memory

Question

I would like to know how multi-dimensional arrays/matrices are represented in memory.

From other posts I learnt that the computer uses 'row-major' or 'column-major'. I understood how these two work. However, I don't understand how the computer is able to distinguish between two separate rows when the rows are placed next to each other in memory.

In other words, if the matrix looked like:

1 2 3
4 5 6
7 8 9

It would be represented as

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

in row-major.

How does the computer know where the next row starts?

Additionally, how would the computer approach storing a 3 or four dimensional array in the memory?

question from:https://stackoverflow.com/questions/65854603/representation-of-multi-dimensional-arrays-in-memory

Answer 1

There are (at least) two different systems for storing two (or more) dimensional arrays that are used in different programming languages.

Some languages, such as Java, actually just create an array-of-arrays. Each row is stored as a separate one-dimensional array. The supposed "two-dimensional-array" is just another one-dimensional array that stores the addresses (or locations in memory) of each of the one-dimensional arrays for the individual rows. This system generalizes easily to multi-dimensional arrays (3, 4, etc.). It also allows "ragged" multi-dimensional arrays where each row has a different length.

Other languages, such as C, store an entire two (or more) dimensional array in a single block of contiguous memory. In this case, the programming language implementation needs to use a formula for calculating the location of any element given its coordinates. For a two-dimensional array stored in row-major-order, as you described, the formula for the index of the element at row R and column C is R * COLUMNS + C where COLUMNS is the number of columns in the array. The crucial implication of this is that the computer needs to know how many columns there are in the array in order to evaluate this formula.

For example, a C programmer might wish to write the following function that calculates the sum of all of the elements in a two-dimensional array:

int sum(int array[][], int rows, int cols) {
    int total = 0;
    for (int r=0; r<rows; r++) {
        for (int c=0; c<cols; c++) {
            total += array[r][c];
        }
    }
    return total;
}

This is not legal C code, because the computer does not know how many columns there are in the array, and so cannot calculate the locations of the elements.

Here is a legal version of the same function:

int sum(int array[][10], int rows, int cols) {
    int total = 0;
    for (int r=0; r<rows; r++) {
        for (int c=0; c<cols; c++) {
            total += array[r][c];
        }
    }
    return total;
}

Notice how the array argument has now been declared to have 10 columns. Of course, this function is a lot less useful than the previous one, since it will only work on arrays with 10 columns.

The C system generalizes to 3 or 4 (or more) dimensional arrays, as long as all of the sizes are fixed in advance (except possibly for the first dimension). So, a function could take an argument of type int array[][10][10][10] for example, which would be a four-dimensional array with an unknown number of "rows" but with a size of 10 in all of the other dimensions.