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