protocol for using InputRanges

[Walter Bright]

On 3/25/2014 2:29 PM, Andrei Alexandrescu wrote:
>> We want to appeal to the high performance coders. To maximize
>> performance, ranges should be optimized to the inner loop case, which is:
>>
>>      while (!r.empty) { auto e = r.front; ... e ...; r.popFront(); }
>
> Actually generic code often prefers:
>
> while (!r.empty) { ... r.front ...; r.popFront(); }
>
> That saves copying r.front if it returns by ref.

Yes, I agree. The idiom foreach (ref e; r) { ... } must also work.


>> Since front is guaranteed to succeed if !empty, this puts a requirement
>> on many ranges that they have a non-trivial constructor that 'primes the
>> pump'. Of course, priming may fail, and so construction may throw, which
>> is not good design.
>
> Again, I disagree with this assertion.

The throwing part, or the not good design part?


>> Next, priming requires a buffer in the range.
> Priming has nothing do to with the range being buffered. The entire design of
> ranges is a one-element buffer.
>> Buffers add size, making them slower to copy, and will often require
>> another field saying if the buffer has data in it or not, further
>> bumping the size.
> That's an argument for adding an unbuffered range abstraction.

I don't know how that would fit into the ecosystem.

In any case, with the protocol I suggest, the designer of the range is free to 
distribute the functionality into the three functions, however it makes best 
sense. With arbitrarily calling any in any order, then all three need to have 
some sort of signalling mechanism between them.


>> All this saves for the user is one call to empty for the entire
>> algorithm, at a cost incurred with every iteration. I.e. it selects O(n)
>> to save O(1).
>
> I don't understand how that O() reasoning works.

I meant adding extra signalling with every iteration of the loop, rather than 
requiring the user to call empty before front.


>> B) I want to be able to call front multiple times in a row, and expect
>> to get the same value.
>
> Correct.
>
>> This can force the range to incorporate a one element buffer and a flag
>> indicating the status of that buffer.
>
> It may, but many ranges naturally work that way (e.g. arrays).

Sure, but there are far more range types than arrays.


>> The range instance gets bigger and
>> more expensive to copy, and the cost of manipulating the flag and the
>> buffer is added to every loop iteration. Note that the user of a range
>> can trivially use:
>>       auto e = r.front;
>>       ... using e multiple times ...
>> instead.
>
> That would pessimize code using arrays of large structs.

You're already requiring copying with the buffering requirement. And besides, if 
I was creating a range of expensive-to-copy objects, I would add a layer of 
indirection to cheapen it.


> The proposed protocol pessimizes arrays of large structs

Not really more than the existing protocol does (i.e. required buffering).

> and will trip the unwary if calling r.front again returns something else.

I'm not proposing that calling them wrongly would make things unsafe. But I 
don't think it's unreasonable to expect the protocol to be followed, just like 
file open/read/close.


> I don't think the proposal is good.

I don't like being in the position of when I need high performance code, I have 
to implement my own ranges & algorithms, or telling customers they need to do so.