C++ / Why Iterators Got It All Wrong

[Ilya Yaroshenko via Digitalmars-d]

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

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.

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.

[1] 
http://docs.algorithm.dlang.io/latest/mir_ndslice_dynamic.html#.reversed
[2]  
https://docs.scipy.org/doc/numpy-dev/reference/generated/numpy.flip.html

Best regards,
Ilya