May 16, 2012
On Wednesday, 16 May 2012 at 17:48:52 UTC, Andrei Alexandrescu wrote:
> This is copiously clear to me, but the way I like to think about it is by extending the notion of range (with notions such as e.g. BufferedRange, LookaheadRange, and such)

I tried this in cgi.d somewhat recently. It ended up
only vaguely looking like a range.

    /**
       A slight difference from regular ranges is you can give it the maximum
       number of bytes to consume.

       IMPORTANT NOTE: the default is to consume nothing, so if you don't call
       consume() yourself and use a regular foreach, it will infinitely loop!
    */
   void popFront(size_t maxBytesToConsume = 0 /*size_t.max*/, size_t minBytesToSettleFor = 0) {}


I called that a "slight different" in the comment, but it is
actually a pretty major difference. In practice, it is nothing
like a regular range.

If I defaulted to size_t.max, you could foreach() it, but then
you don't really get to take advantage of the buffer, since it
is cleared out entirely for each iteration.

If it defaults to 0, you can put it in a foreach... but you
have to manually say how much of it is consumed, which no other
range does, meaning it won't work with std.algorithm or anything.


It sorta looks like a range, but isn't actually one at all.




I'm sure something better is possible, but I don't think the range
abstraction is a good fit for this use case.

Of course, providing optional ranges (like how file gives byChunk,
byLine, etc.) is probably a good idea.
May 16, 2012
On Wed, May 16, 2012 at 12:48:49PM -0500, Andrei Alexandrescu wrote:
> On 5/16/12 12:34 PM, Steven Schveighoffer wrote:
> >In other words, ranges aren't enough.
> 
> This is copiously clear to me, but the way I like to think about it is by extending the notion of range (with notions such as e.g. BufferedRange, LookaheadRange, and such) instead of developing an abstraction independent from ranges and then working on stitching that with ranges.
[...]

One direction that _could_ be helpful, perhaps, is to extend the concept of range to include, let's tentatively call it, a ChunkedRange. Basically a ChunkedRange implements the usual InputRange operations (empty, front, popfront) but adds the following new primitives:

- bool hasAtLeast(R)(R range, int n) - true if underlying range has at
  least n elements left;

- E[] frontN(R)(R range, int n) - returns a slice containing the front n
  elements from the range: this will buffer the next n elements from the
  range if they aren't already; repeated calls will just return the
  buffer;

- void popN(R)(R range, int n) - discards the first n elements from the
  buffer, thus causing the next call to frontN() to fetch more data if
  necessary.

These are all tentative names, of course. But the idea is that you can keep N elements of the range "in view" at a time, without having to individually read them out and save them in a second buffer, and you can advance this view once you're done with the current data and want to move on.

Existing range operations like popFrontN, take, takeExactly, drop, etc., can be extended to take advantage of the extra functionality of ChunkedRanges. (Perhaps popFrontN can even be merged with popN, since they amount to the same thing.)

Using a ChunkedRange allows you to write functions that parse a particular range and return a range of chunks (say, a deserializer that returns a range of objects given a range of bytes).

Thinking on it a bit further, perhaps we can call this a WindowedRange, since it somewhat resembles the sliding window protocol where you keep a "window" of sequential packet ids in an active buffer, and remove them from the buffer as they get ack'ed (consumed by popN). The buffer thus acts like a "window" into the next n elements in the range, which can be "slid forward" as data is consumed.


T

-- 
Having a smoking section in a restaurant is like having a peeing section in a swimming pool. -- Edward Burr
May 16, 2012
On Wed, 16 May 2012 15:38:02 -0400, H. S. Teoh <hsteoh@quickfur.ath.cx> wrote:

> On Wed, May 16, 2012 at 12:48:49PM -0500, Andrei Alexandrescu wrote:
>> On 5/16/12 12:34 PM, Steven Schveighoffer wrote:
>> >In other words, ranges aren't enough.
>>
>> This is copiously clear to me, but the way I like to think about it
>> is by extending the notion of range (with notions such as e.g.
>> BufferedRange, LookaheadRange, and such) instead of developing an
>> abstraction independent from ranges and then working on stitching
>> that with ranges.
> [...]
>
> One direction that _could_ be helpful, perhaps, is to extend the concept
> of range to include, let's tentatively call it, a ChunkedRange.
> Basically a ChunkedRange implements the usual InputRange operations
> (empty, front, popfront) but adds the following new primitives:
>
> - bool hasAtLeast(R)(R range, int n) - true if underlying range has at
>   least n elements left;
>
> - E[] frontN(R)(R range, int n) - returns a slice containing the front n
>   elements from the range: this will buffer the next n elements from the
>   range if they aren't already; repeated calls will just return the
>   buffer;
>
> - void popN(R)(R range, int n) - discards the first n elements from the
>   buffer, thus causing the next call to frontN() to fetch more data if
>   necessary.
>

On such ranges, what would popFront and front do?  I'm assuming since frontN and popN are referring to how many elements, and since the most logical definition for elements is bytes, that front gets the next byte, and popFront discards the next byte.  This seems useless to me.

I still don't get the need to "add" this to ranges.  The streaming API works fine on its own.

But there is an omission with your proposed API regardless -- reading data is a mutating event.  It destructively mutates the underlying data stream so that you cannot get the data again.  This means you must double-buffer data in order to support frontN and popN that are not necessary with a simple read API.

For example:

auto buf = new ubyte[1000000];
stream.read(buf);

does not need to first buffer the data inside the stream and then copy it to buf, it can read it from the OS *directly* into buf.

-Steve
May 16, 2012
On Wed, May 16, 2012 at 04:15:22PM -0400, Steven Schveighoffer wrote:
> On Wed, 16 May 2012 15:38:02 -0400, H. S. Teoh <hsteoh@quickfur.ath.cx> wrote:
[...]
> >One direction that _could_ be helpful, perhaps, is to extend the concept of range to include, let's tentatively call it, a ChunkedRange. Basically a ChunkedRange implements the usual InputRange operations (empty, front, popfront) but adds the following new primitives:
> >
> >- bool hasAtLeast(R)(R range, int n) - true if underlying range has at
> >  least n elements left;
> >
> >- E[] frontN(R)(R range, int n) - returns a slice containing the front n
> >  elements from the range: this will buffer the next n elements from the
> >  range if they aren't already; repeated calls will just return the
> >  buffer;
> >
> >- void popN(R)(R range, int n) - discards the first n elements from the
> >  buffer, thus causing the next call to frontN() to fetch more data if
> >  necessary.
> >
> 
> On such ranges, what would popFront and front do?  I'm assuming since frontN and popN are referring to how many elements, and since the most logical definition for elements is bytes, that front gets the next byte, and popFront discards the next byte.  This seems useless to me.

How so? It's still useful for implementing readByte, for example.


> I still don't get the need to "add" this to ranges.  The streaming API works fine on its own.
> 
> But there is an omission with your proposed API regardless -- reading data is a mutating event.  It destructively mutates the underlying data stream so that you cannot get the data again.  This means you must double-buffer data in order to support frontN and popN that are not necessary with a simple read API.
> 
> For example:
> 
> auto buf = new ubyte[1000000];
> stream.read(buf);
> 
> does not need to first buffer the data inside the stream and then copy it to buf, it can read it from the OS *directly* into buf.
[...]

The idea is that by asking for N elements at a time instead of calling front/popFront N times, the underlying implementation can optimize the request by creating a buffer of size N and have the OS read exactly N bytes directly into that buffer.

	// Reads 1,000,000 bytes into newly allocated buffer and returns
	// buffer.
	auto buf = stream.frontN(1_000_000);

	// Since 1,000,000 bytes is already read into the buffer, this
	// simply returns a slice of the same buffer:
	auto buf2 = stream.frontN(1_000_000);
	assert(buf is buf2);

	// This consumes the buffer:
	stream.popN(1_000_000);

	// This will read another 1,000,000 bytes into a new buffer
	auto buf3 = stream.frontN(1_000_000);

	// This returns the same buffer as buf3 since we already have
	// the data available.
	auto buf4 = stream.frontN(1_000_000);


T

-- 
English has the lovely word "defenestrate", meaning "to execute by throwing someone out a window", or more recently "to remove Windows from a computer and replace it with something useful". :-) -- John Cowan
May 16, 2012
On 05/16/12 21:38, H. S. Teoh wrote:
> On Wed, May 16, 2012 at 12:48:49PM -0500, Andrei Alexandrescu wrote:
>> On 5/16/12 12:34 PM, Steven Schveighoffer wrote:
>>> In other words, ranges aren't enough.
>>
>> This is copiously clear to me, but the way I like to think about it is by extending the notion of range (with notions such as e.g. BufferedRange, LookaheadRange, and such) instead of developing an abstraction independent from ranges and then working on stitching that with ranges.
> [...]
> 
> One direction that _could_ be helpful, perhaps, is to extend the concept of range to include, let's tentatively call it, a ChunkedRange. Basically a ChunkedRange implements the usual InputRange operations (empty, front, popfront) but adds the following new primitives:
> 
> - bool hasAtLeast(R)(R range, int n) - true if underlying range has at
>   least n elements left;
> 
> - E[] frontN(R)(R range, int n) - returns a slice containing the front n
>   elements from the range: this will buffer the next n elements from the
>   range if they aren't already; repeated calls will just return the
>   buffer;
> 
> - void popN(R)(R range, int n) - discards the first n elements from the
>   buffer, thus causing the next call to frontN() to fetch more data if
>   necessary.
> 
> These are all tentative names, of course. But the idea is that you can keep N elements of the range "in view" at a time, without having to individually read them out and save them in a second buffer, and you can advance this view once you're done with the current data and want to move on.
> 
> Existing range operations like popFrontN, take, takeExactly, drop, etc., can be extended to take advantage of the extra functionality of ChunkedRanges. (Perhaps popFrontN can even be merged with popN, since they amount to the same thing.)
> 
> Using a ChunkedRange allows you to write functions that parse a particular range and return a range of chunks (say, a deserializer that returns a range of objects given a range of bytes).
> 
> Thinking on it a bit further, perhaps we can call this a WindowedRange, since it somewhat resembles the sliding window protocol where you keep a "window" of sequential packet ids in an active buffer, and remove them from the buffer as they get ack'ed (consumed by popN). The buffer thus acts like a "window" into the next n elements in the range, which can be "slid forward" as data is consumed.

Right now, everybody reinvents this, with a slightly different interface... It's really obvious, needed and just has to be standardized.

A few notes:

hasAtLeast is redundant as it can be better expressed as .length; what would be the point of wrapping 'r.length>=n'? An '.available' property would be useful to find eg out how much can be consumed w/o blocking, but that one should return a size_t too.

'E[] frontN' should have a version that returns all available elements; i called it '@property E[] fronts()' here. It's more efficient that way and doesn't rely on the compiler to inline and optimize the limit checks away.

PopN -- well, its signature here is 'void popFronts(size_t n)', other than that, there's no difference.

Similar things are necessary for output ranges. Here, what i needed was:

   void put(ref E el)
   void puts(E[] els)
   @property size_t free() // Not the most intuitive name w/o context;
                           // returns the number of E's that can be 'put()'
                           // w/o blocking.

Note that all of this doesn't address the consume-variable-sized-chunks issue. But that can now be efficiently handled by another layer on top.


On 05/16/12 22:15, Steven Schveighoffer wrote:
> I still don't get the need to "add" this to ranges.  The streaming API works fine on its own.

This is not an argument against a streaming API (at least not for me), but for efficient ranges. With the API above I can shift tens of gigabytes of data per second between threads. And still use the 'std' range API and everything that works with it...

> But there is an omission with your proposed API regardless -- reading data is a mutating event.  It destructively mutates the underlying data stream so that you cannot get the data again.  This means you must double-buffer data in order to support frontN and popN that are not necessary with a simple read API.
> 
> For example:
> 
> auto buf = new ubyte[1000000];
> stream.read(buf);
> 
> does not need to first buffer the data inside the stream and then copy it to buf, it can read it from the OS *directly* into buf.

Sometimes having the buffer managed by 'stream' and 'read()' returning a slice
into it works (this is what 'fronts' above does). Reusing a caller managed
buffer can be useful in other cases, yes.

artur
May 16, 2012
> One direction that _could_ be helpful, perhaps, is to extend the concept
> of range to include, let's tentatively call it, a ChunkedRange.
> Basically a ChunkedRange implements the usual InputRange operations
> (empty, front, popfront) but adds the following new primitives:
>
> - bool hasAtLeast(R)(R range, int n) - true if underlying range has at
>   least n elements left;

I think it would be better to have a function that would return
the number of elements left.

> - E[] frontN(R)(R range, int n) - returns a slice containing the front n
>   elements from the range: this will buffer the next n elements from the
>   range if they aren't already; repeated calls will just return the
>   buffer;
>
> - void popN(R)(R range, int n) - discards the first n elements from the
>   buffer, thus causing the next call to frontN() to fetch more data if
>   necessary.

I like the idea of frontN and popN. But is there any reason why
a type that defines those (let's call it a stream) should also
be a range? I would prefer to have a type that just defines those
two functions, a function that returns the number of available
elements and a functions that tells whether we are at the end of
stream. If you need a range of elements with a blocking popFront,
it's easy to build one on top of it. You can write a functions
that takes any stream and returns a range of element. I think
that's better than  having to write front, popFront, and empty
for every stream.
May 16, 2012
On Wed, 16 May 2012 16:30:43 -0400, H. S. Teoh <hsteoh@quickfur.ath.cx> wrote:

> On Wed, May 16, 2012 at 04:15:22PM -0400, Steven Schveighoffer wrote:
>> On Wed, 16 May 2012 15:38:02 -0400, H. S. Teoh
>> <hsteoh@quickfur.ath.cx> wrote:
> [...]
>> >One direction that _could_ be helpful, perhaps, is to extend the  
>> concept
>> >of range to include, let's tentatively call it, a ChunkedRange.
>> >Basically a ChunkedRange implements the usual InputRange operations
>> >(empty, front, popfront) but adds the following new primitives:
>> >
>> >- bool hasAtLeast(R)(R range, int n) - true if underlying range has at
>> >  least n elements left;
>> >
>> >- E[] frontN(R)(R range, int n) - returns a slice containing the front  
>> n
>> >  elements from the range: this will buffer the next n elements from  
>> the
>> >  range if they aren't already; repeated calls will just return the
>> >  buffer;
>> >
>> >- void popN(R)(R range, int n) - discards the first n elements from the
>> >  buffer, thus causing the next call to frontN() to fetch more data if
>> >  necessary.
>> >
>>
>> On such ranges, what would popFront and front do?  I'm assuming since
>> frontN and popN are referring to how many elements, and since the most
>> logical definition for elements is bytes, that front gets the next
>> byte, and popFront discards the next byte.  This seems useless to me.
>
> How so? It's still useful for implementing readByte, for example.

readByte is covered by frontN(1).  Why the need for front()?

Let me answer that question for you -- so it can be treated as a normal range.  But nobody will want to do that.

i.e. copy to appender will read one byte at a time into the array.

>> I still don't get the need to "add" this to ranges.  The streaming API
>> works fine on its own.
>>
>> But there is an omission with your proposed API regardless --
>> reading data is a mutating event.  It destructively mutates the
>> underlying data stream so that you cannot get the data again.  This
>> means you must double-buffer data in order to support frontN and
>> popN that are not necessary with a simple read API.
>>
>> For example:
>>
>> auto buf = new ubyte[1000000];
>> stream.read(buf);
>>
>> does not need to first buffer the data inside the stream and then
>> copy it to buf, it can read it from the OS *directly* into buf.
> [...]
>
> The idea is that by asking for N elements at a time instead of calling
> front/popFront N times, the underlying implementation can optimize the
> request by creating a buffer of size N and have the OS read exactly N
> bytes directly into that buffer.
>
> 	// Reads 1,000,000 bytes into newly allocated buffer and returns
> 	// buffer.
> 	auto buf = stream.frontN(1_000_000);

OK, so stream is providing data via return value and allocation.

> 	// Since 1,000,000 bytes is already read into the buffer, this
> 	// simply returns a slice of the same buffer:
> 	auto buf2 = stream.frontN(1_000_000);

Is buf2 mutable?  If so, this is no good, buf could have mutated this data.  But this can be fixed by making the return value of frontN be const(ubyte)[].

> 	assert(buf is buf2);
>
> 	// This consumes the buffer:
> 	stream.popN(1_000_000);

What does "consume" mean, discard?  Obviously not "reuse", due to line below...

> 	// This will read another 1,000,000 bytes into a new buffer
> 	auto buf3 = stream.frontN(1_000_000);

OK, you definitely lost me here, this will not fly.  The whole point of buffering is to avoid having to reallocate on every read.  If you have to allocate every read, "buffering" is going to have a negative impact on performance!

-Steve
May 16, 2012
On Wed, 16 May 2012 16:38:54 -0400, Artur Skawina <art.08.09@gmail.com> wrote:

> On 05/16/12 22:15, Steven Schveighoffer wrote:
>> I still don't get the need to "add" this to ranges.  The streaming API works fine on its own.
>
> This is not an argument against a streaming API (at least not for me), but
> for efficient ranges. With the API above I can shift tens of gigabytes of
> data per second between threads. And still use the 'std' range API and
> everything that works with it...

But you never would want to.  Don't get me wrong, the primitives here could work for a streaming API (I haven't implemented it that way, but it could be made to work).  But the idea that it must *also* be a std.range input range makes zero sense.

To me, this is as obvious as not supporting linklist[index];  Sure, it can be done, but who would ever use it?

-Steve
May 16, 2012
On 5/16/12 1:00 PM, Steven Schveighoffer wrote:
> What I think we would end up with is a streaming API with range
> primitives tacked on.
>
> - empty is clunky, but possible to implement. However, it may become
> invalid (think of reading a file that is being appended to by another
> process).
> - popFront and front do not have any clear definition of what they refer
> to. The only valid thing I can think of is bytes, and then nobody will
> use them.
>
> That's hardly saying it's "range based". I refuse to believe that people
> will be thrilled by having to 'pre-configure' each front and popFront
> call in order to get work done. If you want to try and convince me, I'm
> willing to listen, but so far I haven't seen anything that looks at all
> appetizing.

Where the two meet is in the notion of buffered streams. Ranges are by default buffered, i.e. user code can call front() several times without an intervening popFront() and get the same thing. So a range has by definition a buffer of at least one element.

That makes the range interface unsuitable for strictly UNbuffered streams. On the other hand, a range could no problem offer OPTIONAL unbuffered reads (the existence of a buffer does not preclude availability of unbuffered transfers).

So to tie it all nicely I think we need:

1. A STRICTLY UNBUFFERED streaming abstraction

2. A notion of range that supports unbuffered transfers.


Andrei
May 16, 2012
On Wed, May 16, 2012 at 04:52:09PM -0400, Steven Schveighoffer wrote:
> On Wed, 16 May 2012 16:30:43 -0400, H. S. Teoh <hsteoh@quickfur.ath.cx> wrote:
> 
> >On Wed, May 16, 2012 at 04:15:22PM -0400, Steven Schveighoffer wrote:
> >>On Wed, 16 May 2012 15:38:02 -0400, H. S. Teoh <hsteoh@quickfur.ath.cx> wrote:
> >[...]
> >>>One direction that _could_ be helpful, perhaps, is to extend the concept of range to include, let's tentatively call it, a ChunkedRange.  Basically a ChunkedRange implements the usual InputRange operations (empty, front, popfront) but adds the following new primitives:
> >>>
> >>>- bool hasAtLeast(R)(R range, int n) - true if underlying range has
> >>>  at least n elements left;
> >>>
> >>>- E[] frontN(R)(R range, int n) - returns a slice containing the
> >>>  front n elements from the range: this will buffer the next n
> >>>  elements from the range if they aren't already; repeated calls
> >>>  will just return the buffer;
> >>>
> >>>- void popN(R)(R range, int n) - discards the first n elements from
> >>>  the buffer, thus causing the next call to frontN() to fetch more
> >>>  data if necessary.
> >>>
> >>
> >>On such ranges, what would popFront and front do?  I'm assuming since frontN and popN are referring to how many elements, and since the most logical definition for elements is bytes, that front gets the next byte, and popFront discards the next byte.  This seems useless to me.
> >
> >How so? It's still useful for implementing readByte, for example.
> 
> readByte is covered by frontN(1).  Why the need for front()?
> 
> Let me answer that question for you -- so it can be treated as a normal range.  But nobody will want to do that.
> 
> i.e. copy to appender will read one byte at a time into the array.

If this new type of range is recognized by std.range, then the relevant algorithms can be made to recognize the existence of frontN and make good use of it, instead of iterating front N times. Then front() can still be used by stuff that really only wants a single byte at a time.


[...]
> >The idea is that by asking for N elements at a time instead of calling front/popFront N times, the underlying implementation can optimize the request by creating a buffer of size N and have the OS read exactly N bytes directly into that buffer.
> >
> >	// Reads 1,000,000 bytes into newly allocated buffer and returns
> >	// buffer.
> >	auto buf = stream.frontN(1_000_000);
> 
> OK, so stream is providing data via return value and allocation.
> 
> >	// Since 1,000,000 bytes is already read into the buffer, this
> >	// simply returns a slice of the same buffer:
> >	auto buf2 = stream.frontN(1_000_000);
> 
> Is buf2 mutable?  If so, this is no good, buf could have mutated this data.  But this can be fixed by making the return value of frontN be const(ubyte)[].
> 
> >	assert(buf is buf2);
> >
> >	// This consumes the buffer:
> >	stream.popN(1_000_000);
> 
> What does "consume" mean, discard?  Obviously not "reuse", due to line below...

Yes, discard. That's what popFront does right now for a single element.


> >	// This will read another 1,000,000 bytes into a new buffer
> >	auto buf3 = stream.frontN(1_000_000);
> 
> OK, you definitely lost me here, this will not fly.  The whole point of buffering is to avoid having to reallocate on every read.  If you have to allocate every read, "buffering" is going to have a negative impact on performance!
[...]

I thought the whole point of buffering is to avoid excessive roundtrips to disk I/O.

Though you do have a point that allocating on every read is a bad idea.


T

-- 
Why is it that all of the instruments seeking intelligent life in the universe are pointed away from Earth? -- Michael Beibl