Contiguous vs Non-contiguous Memory Layout

letters, words, sentences can all be a symbol
Let us consider a 2-dimensional array. This array (matrix) with N-elements will be represented in the memory as a 1-dimensional sequence of N-blocks. The former is called non-contiguous memory layout and the latter contiguous memory layout.

The question then is

How is the 2-D array (non-contiguous layout) represented in the computer as contiguous layout ?

Depending upon the styles (C or Fortran), the non-contiguous layout is transformed by the computer to contiguous layout.

C-style transformation of non-contiguous to contiguous layout

letters, words, sentences can all be a symbol
Let us consider a 2-D array, x = numpy.random.rand(4,3). The shape of the array is therefore 4 × 3 array (numpy.shape(x) = (4,3)). Also any element in the array is associated with its respective, index (n0, n1).

Then, for a C-style non-contiguous layout with shape, (d0, d1, …, dN−1), the value associated with (n0, n1, …, nN−1) is located in the contiguous layout with index = nC.

If,

ni ≜ value of ith index in the non-contiguous layout.
eg. for (2, 1) entry in x is (n0 = 2, n1 = 1)

Then, for C-style non-contiguous layout with shape (d0, d1, …, dN−1) the value in (n0, n1, …, nN−1) is located in the contiguous layout with index nC

C = set of all possible C sub ij

Note for dk, dk + 1, …, dm−1, dm if k < m then,

C = set of all possible C sub ij

Examples illustrating transformation to contiguous layout in C-style

Eg.1: Location of element in x with index (2, 1)

For a C-style non-contiguous layout x with shape, (d0 = 4, d1 = 3) the value in (n0 = 2, n1 = 1) of the non-contiguous layout is located in the contiguous layout with index nC given by,

W = set of all possible w sub i
word is a compound symbol from (say) a shift register


Eg.2: Location of element in x with index (3, 1)

For a C-style non-contiguous layout x with shape, (d0 = 4, d1 = 3) the value in (n0 = 3, n1 = 1) of the non-contiguous layout is located in the contiguous layout with index nC given by,

W = set of all possible w sub i
word is a compound symbol from (say) a shift register

Notice that to move from the element with index (2, 1) in the array x to the element at (3, 1), three elements within the array must be jumped.

word is a compound symbol from (say) a shift register

Stride in an array

The number of elements that must be jumped to get to the next element (eg. next arrow) is given by the stride.

Stride in N-dimensional C-style array

W = set of all possible w sub i
where stride
W = set of all possible w sub i

F-style transformation of non-contiguous to contiguous layout

For a F-style non-contiguous layout with shape, (d0, d1, …, dN−1), the value associated with (n0, n1, …, nN−1) is located in the contiguous layout with index = nF.

C = set of all possible C sub ij

Eg.1: Location of element in x with index (1, 2, 1)

For a F-style non-contiguous layout with shape, (d0 = 2, d1 = 4, d2 = 3) the value in (n0 = 1, n1 = 2, n2 = 1) of the non-contiguous layout is located in the contiguous layout with index nF given by,

W = set of all possible w sub i
word is a compound symbol from (say) a shift register

Eg.2: Location of element in x with index (1, 1, 1)

To move from the element with index (1, 2, 1) in the array x to the element at (1, 1, 1), two elements within the array must be jumped.

word is a compound symbol from (say) a shift register

C-style and F-style array transformations are transpose of each other

word is a compound symbol from (say) a shift register
Elements that must be jumped to get from one element to another is the same.
word is a compound symbol from (say) a shift register



Indexing in C-style is horizontal while Fortran-style indexing is vertical.

word is a compound symbol from (say) a shift register