protocol for using InputRanges

[Andrei Alexandrescu]

I thought I had only 1-2 comments, but I have a few more.

On 3/25/14, 1:15 PM, Walter Bright wrote:
> 1. the protocol is COMPLETELY undocumented and undefined.

s/COMPLETELY/loosely/

> Since ranges+algorithms are central to D, this is a very serious
> problem.

Agreed.

> 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. A bunch of algos in std 
do that.

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

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

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

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

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

> The big problem with (A) and (B) is these costs become present in every
> range, despite being rarely needed and having simple alternatives. This
> is the wrong place to put cost and complexity. The user should be making
> these decisions based on his needs.
>
> Hence, I propose that the protocol for using input ranges be defined as:
>
>      while (!r.empty) { auto e = r.front; ... e ...; r.popFront(); }
>
> This makes it possible to build pipelines that are firehoses with no
> kinks or constrictions in them. It optimizes for the inner loop case,
> not boundary cases.

The proposed protocol pessimizes arrays of large structs and will trip 
the unwary if calling r.front again returns something else. I don't 
think the proposal is good.


Andrei