C++ / Why Iterators Got It All Wrong

[Moritz Maxeiner via Digitalmars-d]

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?

>
> 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?

>
> 3. Ranges can not move backward (auto b = a[-4 .. $].). This 
> means one can not implement dynamic `reversed`(flip) [1, 2] 
> operation for dimensions that have strides (universal or 
> canonical tensors). _Dynamic_ means that instead of construct a 
> new type with reversed order for a dimension, we just negate 
> the corresponding stride and move the cursor.

Right, that is indeed a limitation of the range abstraction 
(though a type could expose both functionality to move backwards 
_and_ the range API) and if you need that, it makes sense not to 
use ranges.

Thanks for the summary of issues :)