Noncontiguous memory layout

Both of the examples presented above are single-segment arrays where the entire array is visited by sequentially marching through memory one element at a time. When an algorithm in C or Fortran expects an N-dimensional array, this single segment (of a certain fundamental type) is usually what is expected along with the shape N-tuple. With a single-segment of memory representing the array, the one-dimensional index into computer memory can always be computed from the N-dimensional index. This concept is explored further in the following paragraphs.

Let ni be the value of the ith index into an array whose shape is represented by the N integers di (i = 0 ... N — 1). Then, the one-dimensional index into a C-style contiguous array is

while the one-dimensional index into a Fortran-style contiguous array is

In these formulas we are assuming that m

^ dj = dk dk+1 • • • dm-1 dm j=k so that if m < k, the product is 1. While perfectly general, these formulas may be a bit confusing at first glimpse. Let's see how they expand out for determining the one-dimensional index corresponding to the element (1, 3, 2) of a 4 x 5 x 6 array. If the array is stored as Fortran contiguous, then nF = no • (1)+ n1 • (4)+ n2 • (4 • 5) = 1 + 3 • 4 + 2 • 20 = 53.

On the other hand, if the array is stored as C contiguous, then nC = no • (5 • 6)+ n • (6)+ n2 • (1) = 1 • 30 + 3 • 6 + 2 • 1 = 50.

The general pattern should be more clear from these examples.

The formulas for the one-dimensional index of the N-dimensional arrays reveal what results in an important generalization for memory layout. Notice that each formula can be written as

where sX gives the stride for dimension i.3 Thus, for C and Fortran contiguous arrays respectively we have

sC = J^J dj = di+idi+2 • • • dN-1, j=i+1 ¿-1

The stride is how many elements in the underlying one-dimensional layout of the array one must jump in order to get to the next array element of a specific dimension in the N-dimensional layout. Thus, in a C-style 4 x 5 x 6 array one must jump over 30 elements to increment the first index by one, so 30 is the stride for the first dimension (sC = 30). If, for each array, we define a strides tuple with N integers, then we have pre-computed and stored an important piece of how to map the N-dimensional index to the one-dimensional one used by the computer.

In addition to providing a pre-computed table for index mapping, by allowing the strides tuple to consist of arbitrary integers we have provided a more general layout for the N-dimensional array. As long as we always use the stride information to move around in the N-dimensional array, we can use any convenient layout we wish for the underlying representation as long as it is regular enough to be defined by constant jumps in each dimension. The ndarray object of NumPy uses this stride information and therefore the underlying memory of an ndarray can be laid out dis-contiguously.

0 0

Post a comment