C++ / Why Iterators Got It All Wrong

[Moritz Maxeiner via Digitalmars-d]

On Sunday, 3 September 2017 at 14:19:19 UTC, Ilya Yaroshenko 
wrote:
> On Sunday, 3 September 2017 at 12:35:16 UTC, Moritz Maxeiner 
> wrote:
>> On Sunday, 3 September 2017 at 09:24:03 UTC, Ilya Yaroshenko 
>> wrote:
>>> On Sunday, 3 September 2017 at 02:43:51 UTC, Moritz Maxeiner 
>>> wrote:
>>>> On Sunday, 3 September 2017 at 02:08:20 UTC, Ilya Yaroshenko 
>>>> wrote:
>>>>> On Tuesday, 29 August 2017 at 12:50:08 UTC, Robert M. Münch 
>>>>> wrote:
>>>>>> Maybe of interest: 
>>>>>> https://www.think-cell.com/en/career/talks/iterators/#1
>>>>>>
>>>>>> I haven't read everything, so not sure if it worth to take 
>>>>>> a look.
>>>>>
>>>>> Iterators has no proper alternative when one need to 
>>>>> implement generic tensor library like Mir Algorithm [1].
>>>>
>>>> Out of curiosity: Could you elaborate on what the issues are 
>>>> with using a range based API internally (if it's 
>>>> performance, the "why")?
>>>
>>> There are three general kinds of dynamic dense tensors. Mir 
>>> implements all of them:
>>>
>>> 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.
>>>
>>> Finite random access range Issues:
>>>
>>> 1. Main API issue is that full featured random access range 
>>> (RAR) API (with slicing, and all opIndex* operators like 
>>> `[]*=` ) is much larger comparing with unbounded random 
>>> access iterator (the same API as pointer).
>>
>> Won't you have to implement opIndex* operators either way in 
>> order to use the `a[]` syntax? The main difference I can see 
>> should be that you'd also have to implement the InputRange 
>> (front,popFront,empty), ForwardRange (save), and 
>> BidirectionalRange (back,popBack) members, which if you don't 
>> need them, is indeed understandably too much?
>
> front,
> popFront,
> empty,
> save,
> back,
> popBack,
> opIndexOpAssign,
> 2 x opIndex(.opSlice) for rhs scalars and ranges
> 2 x opIndexAssign(.opSlice) for rhs scalars and ranges
> 2 x opIndexOpAssign(.opSlice) for rhs scalars and ranges
>
> Plus, because of range topology slicing may be slower good to 
> add this ones:
>
> popFrontN
> popFrontExactly,
> popBackN
> popBackExactly,
>
> and maybe i forgot something ...

Didn't know about the *N *Exactly ones, but yeah, it's a lot. 
Though unless you aren't interesting in the `a[]` syntax, you 
can't avoid opIndex*.

>
>>>
>>> 2. Random access range holds its length. Yes, Phobos has 
>>> infinity ranges (mir hasn't), but the practice is that almost 
>>> any RAR constructed using Phobos has length and you can not 
>>> strip when type is constructed. Anyway, infinity RAR is just 
>>> a pointer/iterator that can move forward but can not move 
>>> backward. Tensors hold their own lengths for each dimensions, 
>>> so range's length is just a useless payload.
>>
>> I'm not sure what you mean here. Is this still about accessing 
>> the elements of one tensor? If so, what do Phobos' ranges have 
>> to do with your tensor type's API?
>
> ndslice is:
> 1. Slice structure with a huge amount of features from mir 
> algorithm
> 2. multidimensional RAR: .front!0, front!1, .front!(N - 1) and 
> all other generalized RAR primitves including multidimensional 
> index [1, 2, 3, ...] and slicing [1 .. 4, 3 .. $].
> 3. Common one dimensional RAR on top of outer most dimension. 
> So one can use Phobos funcitons for Slice structure. For 
> example, a matrix will be iterated row-by-row.
>
> But this paragraph was about another issue:
>
> struct BLASMatrixTypeBasedOnRanges
> {
>    double[] _data; // arrays is the simplest RAR
>    size_t rows, cols;
>    size_t stride;
> }

Now I get what you mean, you were talking about not using the 
dynamic arrays built into the language (which indeed carry their 
length for safety purposes), not about exposing range API here; 
you're right, you don't need to use a dynamic array here, as you 
already have the length encoded another way (it would be 
wasteful), but strictly speaking D's builtin dynamic arrays are 
not ranges (as they are neither aggregate types nor do they have 
the range functions baked into the language). They only become 
ranges when you import the appropriate free functions from Phobos 
(or define some yourself).

>
> sizeof(YourBLASMatrixTypeBasedOnRanges) == size_t.sizeof * 5;
>
> in other hand:
>
> sizeof(Slice!(Canonical, [2], double*)) == size_t.sizeof * 4;
>
> Ranges requires for 25% more space for canonical matrixes then 
> iterators.

We do have to differentiate between a container and the API with 
which to iterate over its elements.
D's dynamic arrays (a pointer+length) require more space then 
using only a raw pointer, of course. If that's more than an 
iterator depends on the type of iterator you use. Most common 
iterator implementations I know consist of a begin and an end 
pointer, essentially requiring the same space as D's dynamic 
arrays.
In the case you describe, though, we aren't talking about the 
iteration API, we are talking about what's used internally for 
storage.