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.

Rosati

Answer 1

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.

Belgae

The term for that I know is "sparse array" (I've actually heard of "sparse matrices" or "sparse vectors", esp. in numerics). Is "strided array" a synonym of "sparse array"? – Killjoy

"Sparse array" is probably a more common term, but perhaps with a slightly different meaning (not a regular distance between the elements?). The term stride does appear in the <valarray> section of the C++ standard. – Belgae

@Kos: sparse array can have way more general shapes. This is indeed a particular case of sparse array. – Vanlandingham

@Alexandre, no, a strided array can have stride that is not a multiple of element's size. And these concepts are different logically – Abroms

@unkulunkulu: when you use level 1/2 BLAS for instance, you pass the stride of the array as an argument, and it is a number. Most usages of stride assume a constant stride, which is the number of elements to skip plus one. – Vanlandingham

@Alexandre, what you said is true (although that plus one part is suspicious), but it doesn't provide argument for the statement that strided array is special case of sparse (which is wrong). In MPI there are also strided array types and stride is constant, yes. So it has nothing to do with sparse arrays. – Abroms

@unkulunkulu: It depends on the format. I could decide to store my array in the form (index, value), in which case { (1, 0.42), (2000, 7), (2001, 53.2) } is a sparse array, but I would be reluctant to call it a strided array. For the plus one thing, it is just about pointer arithmetic: stride = 1 means dense array. It is the number of elements by which you increase the current pointer to go to the next. – Vanlandingham

@Alexandre, you get it wrong, read Jonathan and mine answers for what a strided array is. It doesn't have zeroes in between its elements. And once again, stride is not "1", it can be a non-multiple of element's size, it's just a distance between consecutive array elements. I agree, someone can derive its own definitions based on meaning of the word "stride", but in traditional sense it cannot be considered a particular case of sparse array (where the goal is to reduce memory consumption when the majority of elements are zero). – Abroms

I concur, I don't think this answer should be the accepted one. There is come great (correct) descriptions in the numpy/blas/lapack/eigen docs of dense matrices where you can "stride" along a dimension with certain length steps in the flat-array space. – Logo

Answer 2

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).

Abroms

Well, actually, they say that strides can be non-const, I overlooked that :( – Abroms

So I'm confused again. If the difference between sparse vs stride is not the "distances" being equal or not, then what is? – Killjoy

@Kos, It's kind of logical: sparse array is just cutting memory usage (and algorithm complexity some times) by listing only non-zero elements of the array along with their indices, while strided array is a way of saying where in memory elements are located when they're not contiguously placed. – Abroms

This is what Wikipedia has as the Stride of an array. However, in languages such as C or C++, this is not an interesting property; it is simply the size of the elements of the array. The language referenced is PL/1. I do not find that page compelling — though I don't have specific counter-data which would be necessary to warrant editing it. The answer by FireFly references this page too. – Reduplicate

Answer 3

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);

Reduplicate

Answer 4

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.

Inertia

Answer 5

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.

Endue

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.

Anishaaniso

Answer 7

strided matrices is also used as a term in optimisation, there are several optimisations possible. Say in machine learning you have a neuron that accesses 3x3 nearby neurons from the preceding layer, unoptimized code might look something like this:

var sum = 0;
for(var xoffset = -1; xoffset <= 1; xoffset++){
   for(var yoffset = -1; yoffset <= 1; yoffset++){
       sum += weight[(x+xoffset)*heightstride + (y+yoffset)] * previouslayer[(x+xoffset)*heightstride + (y+yoffset)]
   }
}

But if when compiling the code you know heightstride (say 1000) this can become something like this so the number of operations required to compute the array index is lower.

 var sum=0;
 var offset = x*1000;

 sum += weight[offset-1001] * previouslayer[offset-1001];
 sum += weight[offset-1000] * previouslayer[offset-1000];
 sum += weight[offset-999] * previouslayer[offset-999];

 sum += weight[offset-1] * previouslayer[offset-1];
 sum += weight[offset] * previouslayer[offset];
 sum += weight[offset+1] * previouslayer[offset+1];

 sum += weight[offset+999] * previouslayer[offset+999];
 sum += weight[offset+1000] * previouslayer[offset+1000];
 sum += weight[offset+1001] * previouslayer[offset+1001];

Brierwood