C++ / Why Iterators Got It All Wrong

jmh530 via Digitalmars-d digitalmars-d at puremagic.com
Wed Sep 6 14:44:01 PDT 2017


On Wednesday, 6 September 2017 at 20:24:05 UTC, Enamex wrote:
> On Sunday, 3 September 2017 at 09:24:03 UTC, Ilya Yaroshenko 
> wrote:
>> 1. Contiguous tensors. Their data is located contiguously in 
>> memory. Single dense memory chunk. All strides between 
>> subs-tensors can be computed from lengths.
>>
>> 2. Canonical tensors. Only data for one dimension is dense, 
>> other dimensions has strides that can not be computed from 
>> lengths. BLAS matrixes are canonical tensors: they have two 
>> lengths and one stride.
>>
>> 3. Universal tensors. Each dimension has a stride. Numpy 
>> ndarrays are universal tensors.
>
> Can you elaborate?

IMO, it's something that still needs to get explained better in 
the documentation. I haven't tried to because I'm not 100% on it.

Below is as best as I have figured things out:

All Slices in mir can have an iterator, lengths, and strides.

The lengths are always N-dimensional and contain information on 
the shape of the Slice. So for instance, if the lengths are [3, 
4], then N=2 and it is a 2-dimensional slice, with 3 rows and 4 
columns.

I left out packs...which are an added complication. Packs can be 
used to make slices of slices. For the above Slice, the default 
would simply be that the packs are [1], which means that there is 
no slice of slicing going on. If the packs were now [1, 1] (the 
sum of packs must equal N), then that is like saying you now have 
a slice of slices. In this case, slice[0] would be a row instead 
of a scalar. This is what allows you to iterate by row or by 
column.

So when you're thinking about contiguous, canonical, and 
universal. The way that lengths and packs work is the same for 
all of them. The difference is in the strides. Contiguous slices 
don't have a strides vector. Canonical slices have a strides 
vector with a length of N-1. Universal slices have a strides 
vector of length N.

So how are the strides used and why do they matter? I'm not sure 
I grok this part 100%, so I'll do my best. Strides tell you how 
much difference there is between the units of each array. So for 
instance, if my slice (call it a) has lengths [2, 3, 4] with 
strides [12, 4, 1], then a[0] is a [3, 4] matrix, which is where 
the 12 comes from. To move the pointer to the start of the next 
[3, 4] matrix (a[1]), requires moving 12 of whatever the type is. 
This would be a universal slice because it has N=3 lengths and 
strides. So if you call a._strides, then it would give you [12, 
4, 1]. If a were canonical, calling _strides would give you [12, 
4] because _strides for canonical slices have length N-1. Now if 
a were contiguous instead of universal and you call _strides on 
it, then it would give you [], because contiguous slices have no 
strides.

The memory footprint of the slice appears different for these 
with a and a[0] of universal being larger than canonical and 
contiguous. This largely reflects the storage of the strides data.

Similarly, a[0] has _strides [4, 1] for universal, [4] for 
canonical, and [] for contiguous. Mir is written in such a way 
that a[0] the same regardless of the SliceKind. For the most 
part, this means that it isn't really obvious that there is a 
difference between them. It matters in some underlying functions, 
but I haven't needed to do much other than sometimes convert a 
contiguous slice to universal (though it's not always clear to me 
why, I just do it).


More information about the Digitalmars-d mailing list