What is a strided array?

Question

There is also a counterpart which is called density array. What does this mean? I have done some search, but didn't get accurate information.

Answer 1

Say you have a structure

struct SomeStruct {
    int someField;
    int someUselessField;
    int anotherUselessField;
};

and an array

struct SomeStruct array[10];

Then if you look at all the someFields in this array, they can be considered an array on their own, but they're not occupying consequent memory cells, so this array is strided. A stride here is sizeof(SomeStruct), i.e. the distance between two consequent elements of the strided array.

A sparse array mentioned here is a more general concept and actually a different one: a strided array doesn't contain zeroes in skipped memory cells, they're just not the part of the array.

Strided array is a generalization of usual (dense) arrays when stride != sizeof(element).

Answer 2

If you want to operate on a subset of a 2D array, you need to know the 'stride' of the array. Suppose you have:

int array[4][5];

and you want to operate on the subset of the elements starting at array[1][1] to array[2,3]. Pictorially, this is the core of the diagram below:

+-----+-----+-----+-----+-----+
| 0,0 | 0,1 | 0,2 | 0,3 | 0,4 |
+-----+=====+=====+=====+-----+
| 1,0 [ 1,1 | 1,2 | 1,3 ] 1,4 |
+-----+=====+=====+=====+-----+
| 2,0 [ 2,1 | 2,2 | 2,3 ] 2,4 |
+-----+=====+=====+=====+-----+
| 3,0 | 3,1 | 3,2 | 3,3 | 3,4 |
+-----+-----+-----+-----+-----+

To access the subset of the array in a function accurately, you need to tell the called function the stride of the array:

int summer(int *array, int rows, int cols, int stride)
{
    int sum = 0;
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            sum += array[i * stride + j];
    return(sum);
}

and the call:

int sum = summer(&array[1][1], 2, 3, 5);

Answer 3

To stride is to "take long steps"

thefreedictionary.com/stride

For an array this would mean that only some of the elements are present, like just every 10th element. You can then save space by not storing the empty elements in between.

A dense array would be one where many, if not all, elements are present so there is no empty space between the elements.

Answer 4

I'm adding yet another answer here since I didn't find any of the existing ones satisfactory.

Wikipedia explains the concept of stride, and also writes that “stride cannot be smaller than element size (it would mean that elements are overlapping) but can be larger (indicating extra space between elements)”.

However, from the information I've found, strided arrays allow for exactly this: conserve memory by allowing the stride to be zero or negative.

Strided arrays

Compiling APL to JavaScript explains strided arrays as a way to represent multidimensional arrays with both data and stride, unlike the typical "rectangular" representation of arrays that assumes an implicit stride of 1. It allows both positive, negative and zero stride. Why? It allows for many operations to only alter the stride and shape, and not the underlying data, thus allowing efficient manipulation of large arrays.

The advantage of this strided representation becomes apparent when working with large volumes of data. Functions like transpose (⍉⍵), reverse (⌽⍵), or drop (⍺↓⍵) can reuse the data array and only care to give a new shape, stride, and offset to their result. A reshaped scalar, e.g. 1000000⍴0, can only occupy a constant amount of memory, exploiting the fact that strides can be 0.

I haven't worked out exactly how these operations would be implemented as operations on the stride and shape, but it's easy to see that altering only these instead of the underlying data would be much cheaper in terms of computation. However, it's worth keeping in mind that a strided representation might impact cache locality negatively, so depending on the use case it might be better to use regular rectangular arrays instead.

Answer 5

Possibility 1: Stride describes a buffer array to read an optimized array

When you use a method to store multidimensional arrays in linear storage. The stride describes the size in each dimension of a buffer which will help you read that array. Image taken from Nd4j (More info about Stride)

Possibility 2 (lower level): Stride is the distance between contiguous members of an array

It means that addresses of items with index 0 and 1 won't be continuous in memory unless you use a unit Stride. A bigger value will have the items more distant in memory.

This is useful at low level (word length optimization, overlapping arrays, cache optimization). Refer to wikipedia.

Answer 6

In highly-optimized code, one reasonably coomon technique is to insert padding into arrays. That means that the Nth logical element no longer is at offset N*sizeof(T). The reason why this is can be an optimization is that some caches are associativity-limited. This means that they can't cache both array[i] and array[j] for some pairs i,j. If an algorithm operating on a dense array would use many of such pairs, inserting some padding might reduce this.

A common case where this happens is in image procesing. An image often has a line width of 512 bytes or another "binary round number", and many image manipulation routines use the 3x3 neighborhood of a pixel. As a result, you can get quite a few cache evictions on some cache architectures. By inserting a "weird" number of fake pixels (e.g. 3) at the end of each line, you change the "stride" and there's less cache interference between adjacent lines.

This is very CPU-specific so there's no general advice here.