www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - buffered input

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
I've had the opportunity today to put some solid hours of thinking into 
the relationship (better said the relatedness) of what would be called 
"buffered streams" and ranges. They have some commonalities and some 
differences, but it's been difficult to capture them. I think now I have 
a clear view, caused by a few recent discussions. One was the CSV reader 
discussed on the Phobos list; another was the discussion on defining the 
"right" std.xml.

First, let's start with the humblest abstraction of all - an input 
range, which only defines the troika empty/front/popFront with the known 
semantics.

An input range consumes input destructively and has a one-element 
horizon. It may as well considered a buffered stream with the buffer 
length exactly one.

Going from there, we may say that certain streaming can be done by using 
an input range of ubyte (or dchar for text). That would be the 
UTFpowered equivalent of getchar(). The readf function operates that way 
- it only needs to look one character ahead. Incidentally, the CSV 
format also requires lookahead of 1, so it also can operate on a range 
of dchar.

At this point we need to ask ourselves an essential question. Since we 
have this "input range" abstraction for a 1-element buffer, what would 
its n-elements buffer representation look like? How do we go from "input 
range of T" (which really is "unbuffered input range of T" to "buffered 
input range of T"?

Honestly, the answer was extremely unclear to me for the longest time. I 
thought that such a range would be an extension of the unbuffered one, 
e.g. a range that still offers T from front() but also offers some 
additional functions - e.g. a lookahead in the form of a random-access 
operator. I still think something can be defined along those lines, but 
today I came together with a design that is considerably simpler both 
for the client and the designer of the range.

I hereby suggest we define "buffered input range of T" any range R that 
satisfies the following conditions:

1. R is an input range of T[]

2. R defines a primitive shiftFront(size_t n). The semantics of the 
primitive is that, if r.front.length >= n, then shiftFront(n) discards 
the first n elements in r.front. Subsequently r.front will return a 
slice of the remaining elements.

3. R defines a primitive appendToFront(size_t n). Semantics: adds at 
most n more elements from the underlying stream and makes them available 
in addition to whatever was in front. For example if r.front.length was 
1024, after the call r.appendToFront(512) will have r.front have length 
1536 of which the first 1024 will be the old front and the rest will be 
newly-read elements (assuming that the stream had enough data). If n = 
0, this instructs the stream to add any number of elements at its own 
discretion.

This is it. I like many things about this design, although I still fear 
some fatal flaw may be found with it.

With these primitives a lot of good operating operating on buffered 
streams can be written efficiently. The range is allowed to reuse data 
in its buffers (unless that would contradict language invariants, e.g. 
if T is invariant), so if client code wants to stash away parts of the 
input, it needs to make a copy.

One great thing is that buffered ranges as defined above play very well 
with both ranges and built-in arrays - two quintessential parts of D. I 
look at this and say, "this all makes sense". For example the design 
could be generalized to operate on some random-access range other than 
the built-in array, but then I'm thinking, unless some advantage comes 
about, why not giving T[] a little special status? Probably everyone 
thinks of contiguous memory when thinking "buffers", so here 
generalization may be excessive (albeit meaningful).

Finally, this design is very easy to experiment with and causes no 
disruption to ranges. I can readily add the primitives to byLine and 
byChunk so we can see what streaming we can do that way.

What do you all think?


Andrei
Feb 04 2011
next sibling parent dsimcha <dsimcha yahoo.com> writes:
Interesting.  I was just writing LazyMap and AsyncBuf in 
std.parallelism, and I ran into these exact issues.  (A LazyMap computes 
a map lazily and in parallel and stores the result in a buffer.  An 
AsyncBuf reads from an unbuffered input range in a background thread and 
buffers the results for when you need them.  I wanted to optimize 
chaining LazyMaps and AsyncBufs for pipelining parallelism.)

I solved them with very ad-hoc way with lots of static if statements and 
encapsulation violation within the module.  One thing that would make a 
more principled approach in std.parallelism possible is a swapBuffer() 
primitive.  You provide the range with a new buffer to fill, and it 
gives you complete ownership of the old buffer.  This is basically how 
LazyMap/AsyncBuf pipelining works under the hood, though I never gave 
any serious consideration to the more general case.

On 2/5/2011 12:46 AM, Andrei Alexandrescu wrote:
 I've had the opportunity today to put some solid hours of thinking into
 the relationship (better said the relatedness) of what would be called
 "buffered streams" and ranges. They have some commonalities and some
 differences, but it's been difficult to capture them. I think now I have
 a clear view, caused by a few recent discussions. One was the CSV reader
 discussed on the Phobos list; another was the discussion on defining the
 "right" std.xml.

 First, let's start with the humblest abstraction of all - an input
 range, which only defines the troika empty/front/popFront with the known
 semantics.

 An input range consumes input destructively and has a one-element
 horizon. It may as well considered a buffered stream with the buffer
 length exactly one.

 Going from there, we may say that certain streaming can be done by using
 an input range of ubyte (or dchar for text). That would be the
 UTFpowered equivalent of getchar(). The readf function operates that way
 - it only needs to look one character ahead. Incidentally, the CSV
 format also requires lookahead of 1, so it also can operate on a range
 of dchar.

 At this point we need to ask ourselves an essential question. Since we
 have this "input range" abstraction for a 1-element buffer, what would
 its n-elements buffer representation look like? How do we go from "input
 range of T" (which really is "unbuffered input range of T" to "buffered
 input range of T"?

 Honestly, the answer was extremely unclear to me for the longest time. I
 thought that such a range would be an extension of the unbuffered one,
 e.g. a range that still offers T from front() but also offers some
 additional functions - e.g. a lookahead in the form of a random-access
 operator. I still think something can be defined along those lines, but
 today I came together with a design that is considerably simpler both
 for the client and the designer of the range.

 I hereby suggest we define "buffered input range of T" any range R that
 satisfies the following conditions:

 1. R is an input range of T[]

 2. R defines a primitive shiftFront(size_t n). The semantics of the
 primitive is that, if r.front.length >= n, then shiftFront(n) discards
 the first n elements in r.front. Subsequently r.front will return a
 slice of the remaining elements.

 3. R defines a primitive appendToFront(size_t n). Semantics: adds at
 most n more elements from the underlying stream and makes them available
 in addition to whatever was in front. For example if r.front.length was
 1024, after the call r.appendToFront(512) will have r.front have length
 1536 of which the first 1024 will be the old front and the rest will be
 newly-read elements (assuming that the stream had enough data). If n =
 0, this instructs the stream to add any number of elements at its own
 discretion.

 This is it. I like many things about this design, although I still fear
 some fatal flaw may be found with it.

 With these primitives a lot of good operating operating on buffered
 streams can be written efficiently. The range is allowed to reuse data
 in its buffers (unless that would contradict language invariants, e.g.
 if T is invariant), so if client code wants to stash away parts of the
 input, it needs to make a copy.

 One great thing is that buffered ranges as defined above play very well
 with both ranges and built-in arrays - two quintessential parts of D. I
 look at this and say, "this all makes sense". For example the design
 could be generalized to operate on some random-access range other than
 the built-in array, but then I'm thinking, unless some advantage comes
 about, why not giving T[] a little special status? Probably everyone
 thinks of contiguous memory when thinking "buffers", so here
 generalization may be excessive (albeit meaningful).

 Finally, this design is very easy to experiment with and causes no
 disruption to ranges. I can readily add the primitives to byLine and
 byChunk so we can see what streaming we can do that way.

 What do you all think?


 Andrei

Feb 04 2011
prev sibling next sibling parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
On 02/04/2011 11:46 PM, Andrei Alexandrescu wrote:
 I've had the opportunity today to put some solid hours of thinking into
 the relationship (better said the relatedness) of what would be called
 "buffered streams" and ranges. They have some commonalities and some
 differences, but it's been difficult to capture them. I think now I have
 a clear view, caused by a few recent discussions. One was the CSV reader
 discussed on the Phobos list; another was the discussion on defining the
 "right" std.xml.

 First, let's start with the humblest abstraction of all - an input
 range, which only defines the troika empty/front/popFront with the known
 semantics.

 An input range consumes input destructively and has a one-element
 horizon. It may as well considered a buffered stream with the buffer
 length exactly one.

 Going from there, we may say that certain streaming can be done by using
 an input range of ubyte (or dchar for text). That would be the
 UTFpowered equivalent of getchar(). The readf function operates that way
 - it only needs to look one character ahead. Incidentally, the CSV
 format also requires lookahead of 1, so it also can operate on a range
 of dchar.

 At this point we need to ask ourselves an essential question. Since we
 have this "input range" abstraction for a 1-element buffer, what would
 its n-elements buffer representation look like? How do we go from "input
 range of T" (which really is "unbuffered input range of T" to "buffered
 input range of T"?

 Honestly, the answer was extremely unclear to me for the longest time. I
 thought that such a range would be an extension of the unbuffered one,
 e.g. a range that still offers T from front() but also offers some
 additional functions - e.g. a lookahead in the form of a random-access
 operator. I still think something can be defined along those lines, but
 today I came together with a design that is considerably simpler both
 for the client and the designer of the range.

 I hereby suggest we define "buffered input range of T" any range R that
 satisfies the following conditions:

 1. R is an input range of T[]

 2. R defines a primitive shiftFront(size_t n). The semantics of the
 primitive is that, if r.front.length >= n, then shiftFront(n) discards
 the first n elements in r.front. Subsequently r.front will return a
 slice of the remaining elements.

Does shiftFront literally move element n to index 0 and so on? It seems to me that if you do, its going to have horrid performance, and if you don't, then you will eventually run into situations where appendToFront will require a wrap around, which loses you your contiguity, or a reallocation of the buffer.
Feb 04 2011
next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Ellery Newcomer" <ellery-newcomer utulsa.edu> wrote in message 
news:iiiu0g$2kmp$1 digitalmars.com...
 Does shiftFront literally move element n to index 0 and so on? It seems to 
 me that if you do, its going to have horrid performance, and if you don't, 
 then you will eventually run into situations where appendToFront will 
 require a wrap around, which loses you your contiguity, or a reallocation 
 of the buffer.

That's what I was wondering too. Would it be forced to internally do a bunch of "buf[x..$]~newStuff" and march itself through memory? Would it be sensible to use that interface for a circular buffer? If so, how would you even do it? On a separate note, I think a good way of testing the design (and end up getting something useful anyway) would be to try to use it to create a range that's automatically-buffered in a more traditional way. Ie, Given any input range 'myRange', "buffered(myRange, 2048)" (or something like that) would wrap it in a new input range that automatically buffers the next 2048 elements (asynchronously?) whenever its internal buffer is exhausted. Or something like that. It's late and I'm tired and I can't think anymore ;)
Feb 05 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/5/11 6:46 AM, spir wrote:
 On 02/05/2011 10:36 AM, Nick Sabalausky wrote:
 On a separate note, I think a good way of testing the design (and end up
 getting something useful anyway) would be to try to use it to create a
 range
 that's automatically-buffered in a more traditional way. Ie, Given any
 input
 range 'myRange', "buffered(myRange, 2048)" (or something like that) would
 wrap it in a new input range that automatically buffers the next 2048
 elements (asynchronously?) whenever its internal buffer is exhausted. Or
 something like that. It's late and I'm tired and I can't think anymore ;)

That's exactly what I'm expecting. Funnily enough, I was about to start a thread on the topic after reading related posts. My point was: "I'm not a specialist in efficiency (rather the opposite), I just know there is --theoretically-- relevant performance loss to expect from unbuffered input in various cases. Could we define a generic input-buffering primitive allowing people to benefit from others' competence? Just like Appender." Denis

The buffered range interface as I defined it supports infinite lookahead. The interface mentioned by Nick has lookahead between 1 and 2048. So I don't think my interface is appropriate for that. Infinite lookahead is a wonderful thing. Consider reading lines from a file. Essentially what you need to do is to keep on reading blocks of data until you see \n (possibly followed by some more stuff). Then you offer the client the line up to the \n. When the client wants a new line, you combine the leftover data you already have with new stuff you read. On occasion you need to move over leftovers, but if your internal buffers are large enough that is negligible (I actually tested this recently). Another example: consider dealing with line continuations in reading CSV files. Under certain conditions, you need to read one more line and stitch it with the existing one. This is easy with infinite lookahead, but quite elaborate with lookahead 1. Andrei
Feb 05 2011
next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:iijq99$1a5o$1 digitalmars.com...
 On 2/5/11 6:46 AM, spir wrote:
 On 02/05/2011 10:36 AM, Nick Sabalausky wrote:
 On a separate note, I think a good way of testing the design (and end up
 getting something useful anyway) would be to try to use it to create a
 range
 that's automatically-buffered in a more traditional way. Ie, Given any
 input
 range 'myRange', "buffered(myRange, 2048)" (or something like that) 
 would
 wrap it in a new input range that automatically buffers the next 2048
 elements (asynchronously?) whenever its internal buffer is exhausted. Or
 something like that. It's late and I'm tired and I can't think anymore 
 ;)

That's exactly what I'm expecting. Funnily enough, I was about to start a thread on the topic after reading related posts. My point was: "I'm not a specialist in efficiency (rather the opposite), I just know there is --theoretically-- relevant performance loss to expect from unbuffered input in various cases. Could we define a generic input-buffering primitive allowing people to benefit from others' competence? Just like Appender." Denis

The buffered range interface as I defined it supports infinite lookahead. The interface mentioned by Nick has lookahead between 1 and 2048. So I don't think my interface is appropriate for that. Infinite lookahead is a wonderful thing. Consider reading lines from a file. Essentially what you need to do is to keep on reading blocks of data until you see \n (possibly followed by some more stuff). Then you offer the client the line up to the \n. When the client wants a new line, you combine the leftover data you already have with new stuff you read. On occasion you need to move over leftovers, but if your internal buffers are large enough that is negligible (I actually tested this recently). Another example: consider dealing with line continuations in reading CSV files. Under certain conditions, you need to read one more line and stitch it with the existing one. This is easy with infinite lookahead, but quite elaborate with lookahead 1.

I think I can see how it might be worthwhile to discourage the traditional buffer interface I described in favor of the above. It wouldn't be as trivial to use as what people are used to, but I can see that it could avoid a lot of unnessisary copying, especially with other people's suggestion of allowing the user to provide their own buffer to be filled (and it seems easy enough to learn). But what about when you want a circular buffer? Ie, When you know a certain maximum lookahead is fine and you want to minimize memory usage and buffer-appends. Circular buffers don't do infinite lookahead so the interface maybe doesn't work as well. Plus you probably wouldn't want to provide an interface for slicing into the buffer, since the slice could straddle the wrap-around point which would require a new allocation (ie "return buffer[indexOfFront+sliceStart..$] ~ buffer[0..sliceLength-($-(frontIndex+sliceStart))]"). I guess maybe that would just call for another type of range.
Feb 05 2011
next sibling parent reply Don <nospam nospam.com> writes:
spir wrote:
 On 02/05/2011 10:44 PM, Nick Sabalausky wrote:
 "Andrei Alexandrescu"<SeeWebsiteForEmail erdani.org>  wrote in message
 news:iijq99$1a5o$1 digitalmars.com...
 On 2/5/11 6:46 AM, spir wrote:
 On 02/05/2011 10:36 AM, Nick Sabalausky wrote:
 On a separate note, I think a good way of testing the design (and 
 end up
 getting something useful anyway) would be to try to use it to create a
 range
 that's automatically-buffered in a more traditional way. Ie, Given any
 input
 range 'myRange', "buffered(myRange, 2048)" (or something like that)
 would
 wrap it in a new input range that automatically buffers the next 2048
 elements (asynchronously?) whenever its internal buffer is 
 exhausted. Or
 something like that. It's late and I'm tired and I can't think anymore
 ;)

That's exactly what I'm expecting. Funnily enough, I was about to start a thread on the topic after reading related posts. My point was: "I'm not a specialist in efficiency (rather the opposite), I just know there is --theoretically-- relevant performance loss to expect from unbuffered input in various cases. Could we define a generic input-buffering primitive allowing people to benefit from others' competence? Just like Appender." Denis

The buffered range interface as I defined it supports infinite lookahead. The interface mentioned by Nick has lookahead between 1 and 2048. So I don't think my interface is appropriate for that. Infinite lookahead is a wonderful thing. Consider reading lines from a file. Essentially what you need to do is to keep on reading blocks of data until you see \n (possibly followed by some more stuff). Then you offer the client the line up to the \n. When the client wants a new line, you combine the leftover data you already have with new stuff you read. On occasion you need to move over leftovers, but if your internal buffers are large enough that is negligible (I actually tested this recently). Another example: consider dealing with line continuations in reading CSV files. Under certain conditions, you need to read one more line and stitch it with the existing one. This is easy with infinite lookahead, but quite elaborate with lookahead 1.

I think I can see how it might be worthwhile to discourage the traditional buffer interface I described in favor of the above. It wouldn't be as trivial to use as what people are used to, but I can see that it could avoid a lot of unnessisary copying, especially with other people's suggestion of allowing the user to provide their own buffer to be filled (and it seems easy enough to learn). But what about when you want a circular buffer? Ie, When you know a certain maximum lookahead is fine and you want to minimize memory usage and buffer-appends. Circular buffers don't do infinite lookahead so the interface maybe doesn't work as well. Plus you probably wouldn't want to provide an interface for slicing into the buffer, since the slice could straddle the wrap-around point which would require a new allocation (ie "return buffer[indexOfFront+sliceStart..$] ~ buffer[0..sliceLength-($-(frontIndex+sliceStart))]"). I guess maybe that would just call for another type of range.

Becomes too complicated, doesnt it? Denis

Circular buffers don't seem like an 'optional' use case to me. Most real I/O works that way. I think if the abstraction can't handle it, the abstraction is a failure.
Feb 05 2011
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/5/11 7:28 PM, Don wrote:
 spir wrote:
 On 02/05/2011 10:44 PM, Nick Sabalausky wrote:
 "Andrei Alexandrescu"<SeeWebsiteForEmail erdani.org> wrote in message
 news:iijq99$1a5o$1 digitalmars.com...
 On 2/5/11 6:46 AM, spir wrote:
 On 02/05/2011 10:36 AM, Nick Sabalausky wrote:
 On a separate note, I think a good way of testing the design (and
 end up
 getting something useful anyway) would be to try to use it to
 create a
 range
 that's automatically-buffered in a more traditional way. Ie, Given
 any
 input
 range 'myRange', "buffered(myRange, 2048)" (or something like that)
 would
 wrap it in a new input range that automatically buffers the next 2048
 elements (asynchronously?) whenever its internal buffer is
 exhausted. Or
 something like that. It's late and I'm tired and I can't think
 anymore
 ;)

That's exactly what I'm expecting. Funnily enough, I was about to start a thread on the topic after reading related posts. My point was: "I'm not a specialist in efficiency (rather the opposite), I just know there is --theoretically-- relevant performance loss to expect from unbuffered input in various cases. Could we define a generic input-buffering primitive allowing people to benefit from others' competence? Just like Appender." Denis

The buffered range interface as I defined it supports infinite lookahead. The interface mentioned by Nick has lookahead between 1 and 2048. So I don't think my interface is appropriate for that. Infinite lookahead is a wonderful thing. Consider reading lines from a file. Essentially what you need to do is to keep on reading blocks of data until you see \n (possibly followed by some more stuff). Then you offer the client the line up to the \n. When the client wants a new line, you combine the leftover data you already have with new stuff you read. On occasion you need to move over leftovers, but if your internal buffers are large enough that is negligible (I actually tested this recently). Another example: consider dealing with line continuations in reading CSV files. Under certain conditions, you need to read one more line and stitch it with the existing one. This is easy with infinite lookahead, but quite elaborate with lookahead 1.

I think I can see how it might be worthwhile to discourage the traditional buffer interface I described in favor of the above. It wouldn't be as trivial to use as what people are used to, but I can see that it could avoid a lot of unnessisary copying, especially with other people's suggestion of allowing the user to provide their own buffer to be filled (and it seems easy enough to learn). But what about when you want a circular buffer? Ie, When you know a certain maximum lookahead is fine and you want to minimize memory usage and buffer-appends. Circular buffers don't do infinite lookahead so the interface maybe doesn't work as well. Plus you probably wouldn't want to provide an interface for slicing into the buffer, since the slice could straddle the wrap-around point which would require a new allocation (ie "return buffer[indexOfFront+sliceStart..$] ~ buffer[0..sliceLength-($-(frontIndex+sliceStart))]"). I guess maybe that would just call for another type of range.

Becomes too complicated, doesnt it? Denis

Circular buffers don't seem like an 'optional' use case to me. Most real I/O works that way. I think if the abstraction can't handle it, the abstraction is a failure.

The abstraction does handle it implicitly, except that it doesn't fix the buffer size. If you ask for appendToFront() with large numbers without calling shiftFront() too, the size of the buffer will ultimately increase to accommodate the entire input. That's the infinite in infinite lookahead. Most uses, however, stick with front/popFront (i.e. let the range choose the buffer size and handle circularity transparently) and on occasion call appendToFront()/shiftFront(). Whenever a part of the buffer has been released by calling shiftFront(), the implementation may use it as a circular buffer. Circularity is all transparent, as I think it should be. But the power is there. Consider FIE* for contrast. The C API provides setbuf and setvbuf, but no way to otherwise take advantage of buffering - at all. This really hurts; you can only call fungetc() once and be guaranteed success - i.e. all FILE* offer L(1) capabilities no matter how big a buffer you set! Andrei
Feb 05 2011
parent reply "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:iil64l$1f6s$1 digitalmars.com...
 On 2/5/11 7:28 PM, Don wrote:
 Circular buffers don't seem like an 'optional' use case to me. Most real
 I/O works that way.
 I think if the abstraction can't handle it, the abstraction is a failure.

The abstraction does handle it implicitly, except that it doesn't fix the buffer size. If you ask for appendToFront() with large numbers without calling shiftFront() too, the size of the buffer will ultimately increase to accommodate the entire input. That's the infinite in infinite lookahead.

But what about when the window straddles the border? Ex: The circular buffer's internal size is 1000, the current starting point is 900 and the window (ie, front()) is 200. I guess that could work fine if front() is a random-access range, but if it's an array (which I think is what you proposed unless I misunderstood), then front() would have to return a new allocation: buf[900..$]~buf[0..100].
Feb 05 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/6/11 0:01 EST, Nick Sabalausky wrote:
 "Andrei Alexandrescu"<SeeWebsiteForEmail erdani.org>  wrote in message
 news:iil64l$1f6s$1 digitalmars.com...
 On 2/5/11 7:28 PM, Don wrote:
 Circular buffers don't seem like an 'optional' use case to me. Most real
 I/O works that way.
 I think if the abstraction can't handle it, the abstraction is a failure.

The abstraction does handle it implicitly, except that it doesn't fix the buffer size. If you ask for appendToFront() with large numbers without calling shiftFront() too, the size of the buffer will ultimately increase to accommodate the entire input. That's the infinite in infinite lookahead.

But what about when the window straddles the border? Ex: The circular buffer's internal size is 1000, the current starting point is 900 and the window (ie, front()) is 200. I guess that could work fine if front() is a random-access range, but if it's an array (which I think is what you proposed unless I misunderstood), then front() would have to return a new allocation: buf[900..$]~buf[0..100].

Say the buffer has 1000 elements of which the last 100 contain data (and the other 900 are past data that's not used). Then say this request comes: stream.appendToFront(150); At this point the stream may go two ways: 1. Append to the internal in-memory buffer, making it larger: _buf.length += 150; ... read into _buf[$ - 150 .. $] ... Now we have a buffer that has 1100 elements, of which the last 250 are used. 2. Move the data to the beginning of the buffer and then read 150 more elements starting at position 100: _buf[0 .. 100] = _buf[$ - 100 .. $]; ... read into _buf[100 .. 250] ... Now _buf has still 1000 elements, of which the first 250 contain data. How does the stream decide between 1 and 2? Clearly it's undesirable to grow the buffer too much and it's also undesirable to copy too much data. A simple approach is to establish a bound on losses, for example copy data only if size to copy is < 5% of the entire buffer. Andrei
Feb 06 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/6/11 12:42 PM, spir wrote:
 On 02/06/2011 04:25 PM, Andrei Alexandrescu wrote:
 Say the buffer has 1000 elements of which the last 100 contain data
 (and the
 other 900 are past data that's not used). Then say this request comes:

 stream.appendToFront(150);

 At this point the stream may go two ways:

 1. Append to the internal in-memory buffer, making it larger:

 _buf.length += 150;
 ... read into _buf[$ - 150 .. $] ...

 Now we have a buffer that has 1100 elements, of which the last 250 are
 used.

 2. Move the data to the beginning of the buffer and then read 150 more
 elements
 starting at position 100:

 _buf[0 .. 100] = _buf[$ - 100 .. $];
 ... read into _buf[100 .. 250] ...

 Now _buf has still 1000 elements, of which the first 250 contain data.

 How does the stream decide between 1 and 2? Clearly it's undesirable
 to grow
 the buffer too much and it's also undesirable to copy too much data. A
 simple
 approach is to establish a bound on losses, for example copy data only
 if size
 to copy is < 5% of the entire buffer.

Isn't absolute size also relevant, if not more? I mean, as long as buffer size is small (if not insignificant) in absolute value, compared to eg CPU cache or available RAM, may it be good strategy to grow it whatever the relative growth in proportion of current size?

Of course. But mathematically you want to find bounds as a fraction of the input size.
 Also: could a (truely) circular buffer help & solve the above copy
 problem, concretely?

Not if you want infinite lookahead, which I think is what any modern buffering system should offer. Andrei
Feb 06 2011
next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:iimnm6$1m4a$2 digitalmars.com...
 On 2/6/11 12:42 PM, spir wrote:
 Also: could a (truely) circular buffer help & solve the above copy
 problem, concretely?

Not if you want infinite lookahead, which I think is what any modern buffering system should offer.

Agreed, but not everything always needs infinite lookahead. And sometimes space guarantees are important.
Feb 06 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/6/11 4:13 PM, Nick Sabalausky wrote:
 "Andrei Alexandrescu"<SeeWebsiteForEmail erdani.org>  wrote in message
 news:iimnm6$1m4a$2 digitalmars.com...
 On 2/6/11 12:42 PM, spir wrote:
 Also: could a (truely) circular buffer help&  solve the above copy
 problem, concretely?

Not if you want infinite lookahead, which I think is what any modern buffering system should offer.

Agreed, but not everything always needs infinite lookahead. And sometimes space guarantees are important.

If you don't use infinite lookahead you won't consume infinite memory. You stand to consume more memory though but I believe we're not supposed to optimize for that. To implement O(n) buffering for n elements of lookahead you can use the circular buffer already present in std.range as backend, coupled with routines to replenish it. The disadvantage is that the client doesn't see true T[] buffers, it sees lookalike random-access ranges that use modulo operations for indexing. All in all this is an abstraction worth providing but not as general as discardFromFront() and appendToFront(). Andrei
Feb 06 2011
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/6/11 4:51 PM, spir wrote:
 On 02/06/2011 08:49 PM, Tomek Sowiński wrote:
 Andrei Alexandrescu napisał:

 Also: could a (truely) circular buffer help& solve the above copy
 problem, concretely?

Not if you want infinite lookahead, which I think is what any modern buffering system should offer.

Truely circular, probably not, but a wrap-around slice (circular view of length at most underlying.length) does offer that and solves the copy problem with style.

Right.

With fixed lookahead you can't do a lot of things - such as line continuation in C programs or CSV files. There are plenty of other examples. Generally I believe k-lookahead is a thing of the past and infinite-lookahead is where the future is. Andrei
Feb 06 2011
prev sibling parent spir <denis.spir gmail.com> writes:
On 02/06/2011 04:25 PM, Andrei Alexandrescu wrote:
 Say the buffer has 1000 elements of which the last 100 contain data (and the
 other 900 are past data that's not used). Then say this request comes:

 stream.appendToFront(150);

 At this point the stream may go two ways:

 1. Append to the internal in-memory buffer, making it larger:

 _buf.length += 150;
 ... read into _buf[$ - 150 .. $] ...

 Now we have a buffer that has 1100 elements, of which the last 250 are used.

 2. Move the data to the beginning of the buffer and then read 150 more elements
 starting at position 100:

 _buf[0 .. 100] = _buf[$ - 100 .. $];
 ... read into _buf[100 .. 250] ...

 Now _buf has still 1000 elements, of which the first 250 contain data.

 How does the stream decide between 1 and 2? Clearly it's undesirable to grow
 the buffer too much and it's also undesirable to copy too much data. A simple
 approach is to establish a bound on losses, for example copy data only if size
 to copy is < 5% of the entire buffer.

Isn't absolute size also relevant, if not more? I mean, as long as buffer size is small (if not insignificant) in absolute value, compared to eg CPU cache or available RAM, may it be good strategy to grow it whatever the relative growth in proportion of current size? Also: could a (truely) circular buffer help & solve the above copy problem, concretely? Denis -- _________________ vita es estrany spir.wikidot.com
Feb 06 2011
prev sibling parent spir <denis.spir gmail.com> writes:
On 02/06/2011 01:28 AM, Don wrote:
 spir wrote:
 On 02/05/2011 10:44 PM, Nick Sabalausky wrote:
 "Andrei Alexandrescu"<SeeWebsiteForEmail erdani.org> wrote in message
 news:iijq99$1a5o$1 digitalmars.com...
 On 2/5/11 6:46 AM, spir wrote:
 On 02/05/2011 10:36 AM, Nick Sabalausky wrote:
 On a separate note, I think a good way of testing the design (and end up
 getting something useful anyway) would be to try to use it to create a
 range
 that's automatically-buffered in a more traditional way. Ie, Given any
 input
 range 'myRange', "buffered(myRange, 2048)" (or something like that)
 would
 wrap it in a new input range that automatically buffers the next 2048
 elements (asynchronously?) whenever its internal buffer is exhausted. Or
 something like that. It's late and I'm tired and I can't think anymore
 ;)

That's exactly what I'm expecting. Funnily enough, I was about to start a thread on the topic after reading related posts. My point was: "I'm not a specialist in efficiency (rather the opposite), I just know there is --theoretically-- relevant performance loss to expect from unbuffered input in various cases. Could we define a generic input-buffering primitive allowing people to benefit from others' competence? Just like Appender." Denis

The buffered range interface as I defined it supports infinite lookahead. The interface mentioned by Nick has lookahead between 1 and 2048. So I don't think my interface is appropriate for that. Infinite lookahead is a wonderful thing. Consider reading lines from a file. Essentially what you need to do is to keep on reading blocks of data until you see \n (possibly followed by some more stuff). Then you offer the client the line up to the \n. When the client wants a new line, you combine the leftover data you already have with new stuff you read. On occasion you need to move over leftovers, but if your internal buffers are large enough that is negligible (I actually tested this recently). Another example: consider dealing with line continuations in reading CSV files. Under certain conditions, you need to read one more line and stitch it with the existing one. This is easy with infinite lookahead, but quite elaborate with lookahead 1.

I think I can see how it might be worthwhile to discourage the traditional buffer interface I described in favor of the above. It wouldn't be as trivial to use as what people are used to, but I can see that it could avoid a lot of unnessisary copying, especially with other people's suggestion of allowing the user to provide their own buffer to be filled (and it seems easy enough to learn). But what about when you want a circular buffer? Ie, When you know a certain maximum lookahead is fine and you want to minimize memory usage and buffer-appends. Circular buffers don't do infinite lookahead so the interface maybe doesn't work as well. Plus you probably wouldn't want to provide an interface for slicing into the buffer, since the slice could straddle the wrap-around point which would require a new allocation (ie "return buffer[indexOfFront+sliceStart..$] ~ buffer[0..sliceLength-($-(frontIndex+sliceStart))]"). I guess maybe that would just call for another type of range.

Becomes too complicated, doesnt it? Denis

Circular buffers don't seem like an 'optional' use case to me. Most real I/O works that way. I think if the abstraction can't handle it, the abstraction is a failure.

Sorry, I meant the way we start to draw the picture; not circular buffers, can see the point about them. Think Heywood's "view window" is a helpful image and a good modelling starting point. (maybe it's only me) Denis -- _________________ vita es estrany spir.wikidot.com
Feb 05 2011
prev sibling parent spir <denis.spir gmail.com> writes:
On 02/05/2011 10:44 PM, Nick Sabalausky wrote:
 "Andrei Alexandrescu"<SeeWebsiteForEmail erdani.org>  wrote in message
 news:iijq99$1a5o$1 digitalmars.com...
 On 2/5/11 6:46 AM, spir wrote:
 On 02/05/2011 10:36 AM, Nick Sabalausky wrote:
 On a separate note, I think a good way of testing the design (and end up
 getting something useful anyway) would be to try to use it to create a
 range
 that's automatically-buffered in a more traditional way. Ie, Given any
 input
 range 'myRange', "buffered(myRange, 2048)" (or something like that)
 would
 wrap it in a new input range that automatically buffers the next 2048
 elements (asynchronously?) whenever its internal buffer is exhausted. Or
 something like that. It's late and I'm tired and I can't think anymore
 ;)

That's exactly what I'm expecting. Funnily enough, I was about to start a thread on the topic after reading related posts. My point was: "I'm not a specialist in efficiency (rather the opposite), I just know there is --theoretically-- relevant performance loss to expect from unbuffered input in various cases. Could we define a generic input-buffering primitive allowing people to benefit from others' competence? Just like Appender." Denis

The buffered range interface as I defined it supports infinite lookahead. The interface mentioned by Nick has lookahead between 1 and 2048. So I don't think my interface is appropriate for that. Infinite lookahead is a wonderful thing. Consider reading lines from a file. Essentially what you need to do is to keep on reading blocks of data until you see \n (possibly followed by some more stuff). Then you offer the client the line up to the \n. When the client wants a new line, you combine the leftover data you already have with new stuff you read. On occasion you need to move over leftovers, but if your internal buffers are large enough that is negligible (I actually tested this recently). Another example: consider dealing with line continuations in reading CSV files. Under certain conditions, you need to read one more line and stitch it with the existing one. This is easy with infinite lookahead, but quite elaborate with lookahead 1.

I think I can see how it might be worthwhile to discourage the traditional buffer interface I described in favor of the above. It wouldn't be as trivial to use as what people are used to, but I can see that it could avoid a lot of unnessisary copying, especially with other people's suggestion of allowing the user to provide their own buffer to be filled (and it seems easy enough to learn). But what about when you want a circular buffer? Ie, When you know a certain maximum lookahead is fine and you want to minimize memory usage and buffer-appends. Circular buffers don't do infinite lookahead so the interface maybe doesn't work as well. Plus you probably wouldn't want to provide an interface for slicing into the buffer, since the slice could straddle the wrap-around point which would require a new allocation (ie "return buffer[indexOfFront+sliceStart..$] ~ buffer[0..sliceLength-($-(frontIndex+sliceStart))]"). I guess maybe that would just call for another type of range.

Becomes too complicated, doesnt it? Denis -- _________________ vita es estrany spir.wikidot.com
Feb 05 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 02/05/2011 10:36 AM, Nick Sabalausky wrote:
 On a separate note, I think a good way of testing the design (and end up
 getting something useful anyway) would be to try to use it to create a range
 that's automatically-buffered in a more traditional way. Ie, Given any input
 range 'myRange', "buffered(myRange, 2048)" (or something like that) would
 wrap it in a new input range that automatically buffers the next 2048
 elements (asynchronously?) whenever its internal buffer is exhausted. Or
 something like that. It's late and I'm tired and I can't think anymore ;)

That's exactly what I'm expecting. Funnily enough, I was about to start a thread on the topic after reading related posts. My point was: "I'm not a specialist in efficiency (rather the opposite), I just know there is --theoretically-- relevant performance loss to expect from unbuffered input in various cases. Could we define a generic input-buffering primitive allowing people to benefit from others' competence? Just like Appender." Denis -- _________________ vita es estrany spir.wikidot.com
Feb 05 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 02/05/2011 08:22 AM, Ellery Newcomer wrote:
 2. R defines a primitive shiftFront(size_t n). The semantics of the
 primitive is that, if r.front.length >= n, then shiftFront(n) discards
 the first n elements in r.front. Subsequently r.front will return a
 slice of the remaining elements.

Does shiftFront literally move element n to index 0 and so on? It seems to me that if you do, its going to have horrid performance, and if you don't, then you will eventually run into situations where appendToFront will require a wrap around, which loses you your contiguity, or a reallocation of the buffer.

Is this really what it means? I naively understood "discards" as meaning buf = buf[n..$]; or similar. Denis -- _________________ vita es estrany spir.wikidot.com
Feb 05 2011
prev sibling next sibling parent so <so so.do> writes:
 Does shiftFront literally move element n to index 0 and so on? It seems  
 to me that if you do, its going to have horrid performance, and if you  
 don't, then you will eventually run into situations where appendToFront  
 will require a wrap around, which loses you your contiguity, or a  
 reallocation of the buffer.

I think it is basically popFrontN(), and appendToFront() a just append.
Feb 05 2011
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/5/11 2:22 AM, Ellery Newcomer wrote:
 Does shiftFront literally move element n to index 0 and so on? It seems
 to me that if you do, its going to have horrid performance, and if you
 don't, then you will eventually run into situations where appendToFront
 will require a wrap around, which loses you your contiguity, or a
 reallocation of the buffer.

No, it's a mere internal operation bufpos += n or so. Andrei
Feb 05 2011
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 06 Feb 2011 10:25:15 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 How does the stream decide between 1 and 2? Clearly it's undesirable to  
 grow the buffer too much and it's also undesirable to copy too much  
 data. A simple approach is to establish a bound on losses, for example  
 copy data only if size to copy is < 5% of the entire buffer.

I think also, you should test to see if appending will copy the data anyways (i.e. reallocate). We may need to add a runtime function for this. -Steve
Feb 07 2011
prev sibling next sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2011-02-05 00:46:40 -0500, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:

 I've had the opportunity today to put some solid hours of thinking into 
 the relationship (better said the relatedness) of what would be called 
 "buffered streams" and ranges. They have some commonalities and some 
 differences, but it's been difficult to capture them. I think now I 
 have a clear view, caused by a few recent discussions. One was the CSV 
 reader discussed on the Phobos list; another was the discussion on 
 defining the "right" std.xml.
 
 First, let's start with the humblest abstraction of all - an input 
 range, which only defines the troika empty/front/popFront with the 
 known semantics.
 
 An input range consumes input destructively and has a one-element 
 horizon. It may as well considered a buffered stream with the buffer 
 length exactly one.
 
 Going from there, we may say that certain streaming can be done by 
 using an input range of ubyte (or dchar for text). That would be the 
 UTFpowered equivalent of getchar(). The readf function operates that 
 way - it only needs to look one character ahead. Incidentally, the CSV 
 format also requires lookahead of 1, so it also can operate on a range 
 of dchar.
 
 At this point we need to ask ourselves an essential question. Since we 
 have this "input range" abstraction for a 1-element buffer, what would 
 its n-elements buffer representation look like? How do we go from 
 "input range of T" (which really is "unbuffered input range of T" to 
 "buffered input range of T"?
 
 Honestly, the answer was extremely unclear to me for the longest time. 
 I thought that such a range would be an extension of the unbuffered 
 one, e.g. a range that still offers T from front() but also offers some 
 additional functions - e.g. a lookahead in the form of a random-access 
 operator. I still think something can be defined along those lines, but 
 today I came together with a design that is considerably simpler both 
 for the client and the designer of the range.
 
 I hereby suggest we define "buffered input range of T" any range R that 
 satisfies the following conditions:
 
 1. R is an input range of T[]
 
 2. R defines a primitive shiftFront(size_t n). The semantics of the 
 primitive is that, if r.front.length >= n, then shiftFront(n) discards 
 the first n elements in r.front. Subsequently r.front will return a 
 slice of the remaining elements.
 
 3. R defines a primitive appendToFront(size_t n). Semantics: adds at 
 most n more elements from the underlying stream and makes them 
 available in addition to whatever was in front. For example if 
 r.front.length was 1024, after the call r.appendToFront(512) will have 
 r.front have length 1536 of which the first 1024 will be the old front 
 and the rest will be newly-read elements (assuming that the stream had 
 enough data). If n = 0, this instructs the stream to add any number of 
 elements at its own discretion.
 
 This is it. I like many things about this design, although I still fear 
 some fatal flaw may be found with it.
 
 With these primitives a lot of good operating operating on buffered 
 streams can be written efficiently. The range is allowed to reuse data 
 in its buffers (unless that would contradict language invariants, e.g. 
 if T is invariant), so if client code wants to stash away parts of the 
 input, it needs to make a copy.
 
 One great thing is that buffered ranges as defined above play very well 
 with both ranges and built-in arrays - two quintessential parts of D. I 
 look at this and say, "this all makes sense". For example the design 
 could be generalized to operate on some random-access range other than 
 the built-in array, but then I'm thinking, unless some advantage comes 
 about, why not giving T[] a little special status? Probably everyone 
 thinks of contiguous memory when thinking "buffers", so here 
 generalization may be excessive (albeit meaningful).
 
 Finally, this design is very easy to experiment with and causes no 
 disruption to ranges. I can readily add the primitives to byLine and 
 byChunk so we can see what streaming we can do that way.
 
 What do you all think?

One thing I'm wondering is whether it'd be more efficient if we could provide our own buffer to be filled. In cases where you want to preserve the data, this could let you avoid double-copying: first copy in the temporary buffer and then at the permanent storage location. If you need the data only temporarily however providing your buffer to be filled might be less efficient for a range that can't avoid copying to the temporary buffer for some reason.. Overall, it looks like a good design. It's quite low-level, but that's not a bad thing. I'll have to think a little to see how I could integrate it into my XML parser (which only deal with complete files in memory at this time). Being able to say "fill this buffer" would certainly make things easier for me. -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Feb 04 2011
next sibling parent reply spir <denis.spir gmail.com> writes:
On 02/05/2011 08:45 AM, Michel Fortin wrote:
 One thing I'm wondering is whether it'd be more efficient if we could provide
 our own buffer to be filled. In cases where you want to preserve the data, this
 could let you avoid double-copying: first copy in the temporary buffer and then
 at the permanent storage location. If you need the data only temporarily
 however providing your buffer to be filled might be less efficient for a range
 that can't avoid copying to the temporary buffer for some reason..

Does this also makes sense when one needs to iterate over a whole set of source data via buferred input rangeS? I mean the same buffer can be reused, avoiding repeted allocation (or is this wrong or irrelevant?). Deins -- _________________ vita es estrany spir.wikidot.com
Feb 05 2011
parent Michel Fortin <michel.fortin michelf.com> writes:
On 2011-02-05 07:01:24 -0500, spir <denis.spir gmail.com> said:

 On 02/05/2011 08:45 AM, Michel Fortin wrote:
 One thing I'm wondering is whether it'd be more efficient if we could provide
 our own buffer to be filled. In cases where you want to preserve the data, this
 could let you avoid double-copying: first copy in the temporary buffer and then
 at the permanent storage location. If you need the data only temporarily
 however providing your buffer to be filled might be less efficient for a range
 that can't avoid copying to the temporary buffer for some reason..

Does this also makes sense when one needs to iterate over a whole set of source data via buferred input rangeS? I mean the same buffer can be reused, avoiding repeted allocation (or is this wrong or irrelevant?).

As I said in my post, whether a temporary buffer or a user-supplied buffer is better depends on whether you plan to store the data beyond the temporary buffer's lifetime or not. If you just iterate to calculate the SHA1 hash, the temporary buffer is fine (and possibly better depending on the range's implementation). If you iterate to calculate the SHA1 hash *and* also want to store the file in memory, then it's better if you can provide your own buffer which can point directly to the permanent storage location and bypass copying to the temporary buffer (if the range's implementation allows it). -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Feb 05 2011
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/5/11 2:45 AM, Michel Fortin wrote:
 One thing I'm wondering is whether it'd be more efficient if we could
 provide our own buffer to be filled. In cases where you want to preserve
 the data, this could let you avoid double-copying: first copy in the
 temporary buffer and then at the permanent storage location. If you need
 the data only temporarily however providing your buffer to be filled
 might be less efficient for a range that can't avoid copying to the
 temporary buffer for some reason..

Generally when one says "I want the stream to copy data straight into my buffers" this is the same as "I want the stream to be unbuffered". So if you want to provide your own buffers to be filled, we need to discuss refining the design of unbuffered input - for example by adding an optional routine for bulk transfer to input ranges. Andrei
Feb 05 2011
parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2011-02-05 10:02:47 -0500, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:

 Generally when one says "I want the stream to copy data straight into 
 my buffers" this is the same as "I want the stream to be unbuffered". 
 So if you want to provide your own buffers to be filled, we need to 
 discuss refining the design of unbuffered input - for example by adding 
 an optional routine for bulk transfer to input ranges.

You're right, this is a different thing. My major gripe with ranges at this time is that it's almost impossible to design an algorithm that can take slices *or* make copies depending on whether the range supports slicing or not, and whether the slices are stable (not going to be mutated when popping elements from the range). At least not without writing two implementations of it. I reread your initial post to get a clearer idea of what it meant. It seems to me that your buffered range design could be made to fix that hole. If the data you want to parse is all in memory, the buffered range could simply use the original array as its buffer; shiftFront would simply just the whole array to remove the first n elements while appendToFront would do nothing (as the buffer already contains all of the content). And if the data is immutable, then it's safe to just take a slice of it to preserve it instead of doing a copy. So you can't really be more efficient than that, it's just great. As for getting the data in bulk directly so you can avoid needless copies... I think the same optimization is possible with a buffered range. All you need is a buffered range that doesn't reuse the buffer, presumably one of immutable(T)[]. With it, you can slice at will without fear of the data being overwritten at a later time. So my rereading of your proposal convinced me. Go ahead, I can't wait to use it. :-) -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Feb 05 2011
parent Michel Fortin <michel.fortin michelf.com> writes:
On 2011-02-05 11:41:18 -0500, Michel Fortin <michel.fortin michelf.com> said:

 If the data you want to parse is all in memory, the buffered range 
 could simply use the original array as its buffer; shiftFront would 
 simply just the whole array to remove the first n elements while 
 appendToFront would do nothing (as the buffer already contains all of 
 the content).

Oops, please change "shiftFront would simply just the whole array" to "shiftFront would simply slice the whole array" -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Feb 05 2011
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 05 Feb 2011 10:02:47 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 2/5/11 2:45 AM, Michel Fortin wrote:
 One thing I'm wondering is whether it'd be more efficient if we could
 provide our own buffer to be filled. In cases where you want to preserve
 the data, this could let you avoid double-copying: first copy in the
 temporary buffer and then at the permanent storage location. If you need
 the data only temporarily however providing your buffer to be filled
 might be less efficient for a range that can't avoid copying to the
 temporary buffer for some reason..

Generally when one says "I want the stream to copy data straight into my buffers" this is the same as "I want the stream to be unbuffered". So if you want to provide your own buffers to be filled, we need to discuss refining the design of unbuffered input - for example by adding an optional routine for bulk transfer to input ranges.

I may want to store 1% of a very large file. You are saying I must either a) unbuffer the entire file (handling the buffering on my own) or b) take the penalty and double copy the data. I want c) temporarily use my buffer for buffering until I say to stop. The range interface doesn't make this easy... -Steve
Feb 07 2011
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday 04 February 2011 21:46:40 Andrei Alexandrescu wrote:
 I've had the opportunity today to put some solid hours of thinking into
 the relationship (better said the relatedness) of what would be called
 "buffered streams" and ranges. They have some commonalities and some
 differences, but it's been difficult to capture them. I think now I have
 a clear view, caused by a few recent discussions. One was the CSV reader
 discussed on the Phobos list; another was the discussion on defining the
 "right" std.xml.
 
 First, let's start with the humblest abstraction of all - an input
 range, which only defines the troika empty/front/popFront with the known
 semantics.
 
 An input range consumes input destructively and has a one-element
 horizon. It may as well considered a buffered stream with the buffer
 length exactly one.
 
 Going from there, we may say that certain streaming can be done by using
 an input range of ubyte (or dchar for text). That would be the
 UTFpowered equivalent of getchar(). The readf function operates that way
 - it only needs to look one character ahead. Incidentally, the CSV
 format also requires lookahead of 1, so it also can operate on a range
 of dchar.
 
 At this point we need to ask ourselves an essential question. Since we
 have this "input range" abstraction for a 1-element buffer, what would
 its n-elements buffer representation look like? How do we go from "input
 range of T" (which really is "unbuffered input range of T" to "buffered
 input range of T"?
 
 Honestly, the answer was extremely unclear to me for the longest time. I
 thought that such a range would be an extension of the unbuffered one,
 e.g. a range that still offers T from front() but also offers some
 additional functions - e.g. a lookahead in the form of a random-access
 operator. I still think something can be defined along those lines, but
 today I came together with a design that is considerably simpler both
 for the client and the designer of the range.
 
 I hereby suggest we define "buffered input range of T" any range R that
 satisfies the following conditions:
 
 1. R is an input range of T[]
 
 2. R defines a primitive shiftFront(size_t n). The semantics of the
 primitive is that, if r.front.length >= n, then shiftFront(n) discards
 the first n elements in r.front. Subsequently r.front will return a
 slice of the remaining elements.
 
 3. R defines a primitive appendToFront(size_t n). Semantics: adds at
 most n more elements from the underlying stream and makes them available
 in addition to whatever was in front. For example if r.front.length was
 1024, after the call r.appendToFront(512) will have r.front have length
 1536 of which the first 1024 will be the old front and the rest will be
 newly-read elements (assuming that the stream had enough data). If n =
 0, this instructs the stream to add any number of elements at its own
 discretion.
 
 This is it. I like many things about this design, although I still fear
 some fatal flaw may be found with it.
 
 With these primitives a lot of good operating operating on buffered
 streams can be written efficiently. The range is allowed to reuse data
 in its buffers (unless that would contradict language invariants, e.g.
 if T is invariant), so if client code wants to stash away parts of the
 input, it needs to make a copy.
 
 One great thing is that buffered ranges as defined above play very well
 with both ranges and built-in arrays - two quintessential parts of D. I
 look at this and say, "this all makes sense". For example the design
 could be generalized to operate on some random-access range other than
 the built-in array, but then I'm thinking, unless some advantage comes
 about, why not giving T[] a little special status? Probably everyone
 thinks of contiguous memory when thinking "buffers", so here
 generalization may be excessive (albeit meaningful).
 
 Finally, this design is very easy to experiment with and causes no
 disruption to ranges. I can readily add the primitives to byLine and
 byChunk so we can see what streaming we can do that way.
 
 What do you all think?

Hmm. I think that I'd have to have an actual implementation to mess around with to say much. My general take on buffered input is that I don't want to worry about it. I want it to be buffered so that it's more efficient, but I don't want to have to care about it in how I use it. I would have expected a buffered input range to be exactly the same as an input range except that it doesn't really just pull in one character behind the scenes. It pulls in 1024 or whatever when popFront() would result in the end of the buffer being reached, and you just get the first one with front. The API doesn't reflect the fact that it's buffered at all except perhaps in how you initialize it (by telling how big the buffer is, though generally I don't want to have to care about that either). Now, there may be some sort of use case where you actually need to care about the buffering, so using buffered data in the way that I was thinking wouldn't really work. But if so, that's not the sort of use case that I normally run into. Regardless, a more normal range could be built on top of what you're suggesting, and it could do essentially what I was thinking buffered ranges would do. So, perhaps doing what you're suggesting and building what I was thinking of on top of that would be the way to go. That way, if you actually care about messing with the buffer, you can, but if not, you just use it normally and the buffering is dealt with underneath. - Jonathan M Davis
Feb 05 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/5/11 5:09 AM, Jonathan M Davis wrote:
 Hmm. I think that I'd have to have an actual implementation to mess around with
 to say much. My general take on buffered input is that I don't want to worry
 about it. I want it to be buffered so that it's more efficient, but I don't
want to
 have to care about it in how I use it. I would have expected a buffered input
 range to be exactly the same as an input range except that it doesn't really
 just pull in one character behind the scenes. It pulls in 1024 or whatever when
 popFront() would result in the end of the buffer being reached, and you just
get
 the first one with front. The API doesn't reflect the fact that it's buffered
at
 all except perhaps in how you initialize it (by telling how big the buffer is,
 though generally I don't want to have to care about that either).

Transparent buffering sounds sensible but in fact it robs you of important capabilities. It essentially forces you to use grammars with lookahead 1 for all input operations. Being able to peek forward into the stream without committing to read from it allows you to e.g. do operations like "does this stream start with a specific word" etc. As soon Andrei
Feb 05 2011
next sibling parent "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:iijpp7$197f$1 digitalmars.com...
 On 2/5/11 5:09 AM, Jonathan M Davis wrote:
 Hmm. I think that I'd have to have an actual implementation to mess 
 around with
 to say much. My general take on buffered input is that I don't want to 
 worry
 about it. I want it to be buffered so that it's more efficient, but I 
 don't want to
 have to care about it in how I use it. I would have expected a buffered 
 input
 range to be exactly the same as an input range except that it doesn't 
 really
 just pull in one character behind the scenes. It pulls in 1024 or 
 whatever when
 popFront() would result in the end of the buffer being reached, and you 
 just get
 the first one with front. The API doesn't reflect the fact that it's 
 buffered at
 all except perhaps in how you initialize it (by telling how big the 
 buffer is,
 though generally I don't want to have to care about that either).

Transparent buffering sounds sensible but in fact it robs you of important capabilities. It essentially forces you to use grammars with lookahead 1 for all input operations. Being able to peek forward into the stream without committing to read from it allows you to e.g. do operations like "does this stream start with a specific word" etc. As soon

That shouldn't be a problem for the cases where a lookahead of 1 is all that's needed. So both types can exist (with the traditional/automatic type most likely built on top of Andrei's type). Thus, I think the only question is "Are the appropriate use-cases for the traditional/automatic type minor enough and infrequent enough to actively discourage it by not providing it?" That I can't answer.
Feb 05 2011
prev sibling next sibling parent reply spir <denis.spir gmail.com> writes:
On 02/05/2011 11:00 PM, Nick Sabalausky wrote:
 Transparent buffering sounds sensible but in fact it robs you of important
  capabilities. It essentially forces you to use grammars with lookahead 1
  for all input operations. Being able to peek forward into the stream
  without committing to read from it allows you to e.g. do operations like
  "does this stream start with a specific word" etc. As soon


that's needed. So both types can exist (with the traditional/automatic type most likely built on top of Andrei's type). Thus, I think the only question is "Are the appropriate use-cases for the traditional/automatic type minor enough and infrequent enough to actively discourage it by not providing it?" That I can't answer.

And what about backtracking (eg for parsing the source)? Denis -- _________________ vita es estrany spir.wikidot.com
Feb 05 2011
parent "Nick Sabalausky" <a a.a> writes:
"spir" <denis.spir gmail.com> wrote in message 
news:mailman.1321.1296950957.4748.digitalmars-d puremagic.com...
 On 02/05/2011 11:00 PM, Nick Sabalausky wrote:
 Transparent buffering sounds sensible but in fact it robs you of 
 important
  capabilities. It essentially forces you to use grammars with 
 lookahead 1
  for all input operations. Being able to peek forward into the stream
  without committing to read from it allows you to e.g. do operations 
 like
  "does this stream start with a specific word" etc. As soon


that's needed. So both types can exist (with the traditional/automatic type most likely built on top of Andrei's type). Thus, I think the only question is "Are the appropriate use-cases for the traditional/automatic type minor enough and infrequent enough to actively discourage it by not providing it?" That I can't answer.

And what about backtracking (eg for parsing the source)?

Like I said, there are certainly cases where a lookahead of 1 isn't sufficient, and for those, something more like Andrei's proposal can be used. (FWIW, LR doesn't usually need backtracking. That's more typically an LL thing. Not that LL is any less important, though. Of course, if the lexical grammer supports non-consuming lookahead, then you'd still need lookahead >1 no matter what parsing algorithm is used.)
Feb 05 2011
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/5/11 12:59 PM, Tomek Sowiński wrote:
 Andrei Alexandrescu napisał:

 Transparent buffering sounds sensible but in fact it robs you of
 important capabilities. It essentially forces you to use grammars with
 lookahead 1 for all input operations. Being able to peek forward into
 the stream without committing to read from it allows you to e.g. do
 operations like "does this stream start with a specific word" etc. As soon

Broken sentence?

Sorry. Well it was nothing interesting anyway. Andrei
Feb 05 2011
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday 05 February 2011 12:57:21 Jonathan M Davis wrote:
 On Saturday 05 February 2011 07:16:45 Andrei Alexandrescu wrote:
 On 2/5/11 5:09 AM, Jonathan M Davis wrote:
 Hmm. I think that I'd have to have an actual implementation to mess
 around with to say much. My general take on buffered input is that I
 don't want to worry about it. I want it to be buffered so that it's
 more efficient, but I don't want to have to care about it in how I use
 it. I would have expected a buffered input range to be exactly the
 same as an input range except that it doesn't really just pull in one
 character behind the scenes. It pulls in 1024 or whatever when
 popFront() would result in the end of the buffer being reached, and
 you just get the first one with front. The API doesn't reflect the
 fact that it's buffered at all except perhaps in how you initialize it
 (by telling how big the buffer is, though generally I don't want to
 have to care about that either).

Transparent buffering sounds sensible but in fact it robs you of important capabilities. It essentially forces you to use grammars with lookahead 1 for all input operations. Being able to peek forward into the stream without committing to read from it allows you to e.g. do operations like "does this stream start with a specific word" etc. As soon

The thing is though that if I want to be iterating over a string which is buffered (from a file or stream or whatever), I want front to be immutable(char) or char, not immutable(char)[] or char[]. I can see how having an interface which allows startsWith to efficiently check whether the buffered string starts with a particular string makes good sense, but generally, as far as I'm concerned, that's startsWith's problem. How would I even begin to use a buffered range of string[] as a string? Normally, when I've used buffered anything, it's been purely for efficiency reasons. All I've cared about is having a stream or file or whatever. The fact that reading it from the file (or wherever it came from) in a buffered manner is more efficient means that I want it buffered, but that hasn't had any effect on how I've used it. If I want x characters from the file, I ask for x characters. It's the buffered object's problem how many reads that does or doesn't do. You must be thinking of a use case which I don't normal think of or am not aware of. In my experience, buffering has always been an implementation detail that you use because it's more efficient, but you don't worry about it beyond creating a buffered stream rather than an unbuffered one.

Okay. I think that I've been misunderstanding some stuff here. I forgot that we were dealing with input ranges rather than forward ranges, and many range functions just don't work with input ranges, since they lack save(). Bleh. Okay. Honestly, what I'd normally want to be dealing with when reading a stream or file is a buffered forward range which is implemented in a manner which minimized copies. Having to deal with a input range, let alone what Andrei is suggesting here would definitely be annoying to say the least. Couldn't we do something which created a new buffer each time that it read in data from a file, and then it could be a forward range with infinite look-ahead. The cost of creating a new buffer would likely be minimal, if not outright neglible, in comparison to reading in the data from a file, and having multiple buffers would allow it to be a forward range. Perhaps, the creation of a new buffer could even be skipped if save had never been called and therefore no external references to the buffer would exist - at least as long as we're talking about bytes or characters or other value types. Maybe there's some major flaw in that basic idea. I don't know. But Andrei's suggestion sounds like a royal pain for basic I/O. If that's all I had to deal with when trying to lazily read in a file and process it, I'd just use readText() instead, since it would just be way easier to use. But that's not exactly ideal, because it doesn't work well with large files. Maybe Andrei's idea is great to have and maybe it _should_ be in Phobos, but I really think that we need a higher level abstraction that makes a stream into a forward range so that it's actually simple to use buffered I/O. As efficient as Andrei's suggestion may be, it sure sounds like a royal pain to use - especially in comparison to readText(). So, maybe I'm still misunderstanding or missing something here, but what _I_ want to see for I/O streams is a _forward_ range which is buffered and which reads in the file or whatever the data comes from in a lazy manner. The more I think about it, the less I like input ranges. They're just so painfully restrictive. They may be necessary at times, but I'd _much_ prefer to deal with forward ranges. On a related note, perhaps we should add a function to some subset of ranges which is called something like frontN() and returns a T[] (or perhaps a range over type T) when the range is a range over type T. That way, you could grab a whole chunk at once without taking it out of the range or having to process the range element by element. It wouldn't even need to be a random access range. It would just need enough lookahead to grab the first n elements. So, I don't know what the best solution to this problem is, but I'd _really_ like one which makes buffered I/O _simple_, and while Andrei's solution may be a great building block, it is _not_ simple. - Jonathan M Davis
Feb 06 2011
next sibling parent Michel Fortin <michel.fortin michelf.com> writes:
On 2011-02-06 03:22:08 -0500, Jonathan M Davis <jmdavisProg gmx.com> said:

 So, maybe I'm still misunderstanding or missing something here, but what _I_
 want to see for I/O streams is a _forward_ range which is buffered and which
 reads in the file or whatever the data comes from in a lazy manner. The more I
 think about it, the less I like input ranges. They're just so painfully
 restrictive. They may be necessary at times, but I'd _much_ prefer to deal with
 forward ranges.

It's true that forward ranges are much easier to deal with. That said, if the underlying abstraction does not support saving a position to return to it later (think of a network stream), implementing them is rather impractical, even though it might be possible with buffering. But still, let's let's see how we could implement a forward range on top of the buffered range abstraction could be done: 1. Wrap the buffered range in a data structure that keeps track of the absolute offset for the first element in the range and contains a sorted list of offsets representing all the forward ranges iterating on it. 2. Make is so that each time the smallest offset in the list is advanced you call shiftFront to to remove from the buffer the no longer referenced elements; and each time an offset goes beyond what's available in the buffer you call appendToFront to make elements up to that index available in the buffer. This ensures the buffer always cover all of the offsets in the list. To make this efficient, the list must be kept sorted at all times. 3. Then you can create forward ranges as reference to that data structure: all they have to do is maintain their offset in the list. Creating a new range would just create another offset in the list and ensures the buffer is preserved. When the range advances or gets destroyed it updates or destroy its offset in the list accordingly. This way the buffer always covers all forward ranges. While it is indeed possible to do what you want, it's hardly a good abstraction to build an efficient parsing algorithm. There's just too much bookkeeping to do. And you must be sure saved ranges get destroyed as soon as possible to avoid the buffer from growing too much, something you usually don't have to care about with forward ranges. -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Feb 06 2011
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/6/11 3:22 EST, Jonathan M Davis wrote:
 Okay. I think that I've been misunderstanding some stuff here. I forgot that we
 were dealing with input ranges rather than forward ranges, and many range
 functions just don't work with input ranges, since they lack save(). Bleh.

 Okay. Honestly, what I'd normally want to be dealing with when reading a stream
 or file is a buffered forward range which is implemented in a manner which
 minimized copies. Having to deal with a input range, let alone what Andrei is
 suggesting here would definitely be annoying to say the least.

 Couldn't we do something which created a new buffer each time that it read in
 data from a file, and then it could be a forward range with infinite
look-ahead.
 The cost of creating a new buffer would likely be minimal, if not outright
 neglible, in comparison to reading in the data from a file, and having multiple
 buffers would allow it to be a forward range. Perhaps, the creation of a new
 buffer could even be skipped if save had never been called and therefore no
 external references to the buffer would exist - at least as long as we're
talking
 about bytes or characters or other value types.

APIs predicated on the notion that I/O is very expensive and extra overheads are not measurable have paid dearly for it (e.g. C++'s iostreams).
 Maybe there's some major flaw in that basic idea. I don't know. But Andrei's
 suggestion sounds like a royal pain for basic I/O. If that's all I had to deal
 with when trying to lazily read in a file and process it, I'd just use
readText()
 instead, since it would just be way easier to use.

Clearly reading the entire file in an in-memory structure simplifies things. But the proposed streaming interface is extremely convenient as it always was; the two added APIs help people who need extra flexibility without hurting efficiency. If you want to read a file in Java: http://www.java-tips.org/java-se-tips/java.io/how-to-read-file-in-java.html In C (with many caveats): http://www.phanderson.com/files/file_read.html In D: foreach (line; File("name").byLine()) { ... } I plan to add a simpler API: foreach (line; File.byLine("name")) { ... } To read fixed-sized chunks, use byChunk. This covers the vast majority of file I/O needs. There are two limitations of the current APIs: 1. You can't add a new line to the existing line (or a buffer to the existing buffer) if you sometimes want to process multiple lines as a logical unit (some programs and file formats need that, as well as composing streams). 2. You can't comfortably read data of user-specified size if that size varies. This is the case for e.g. binary formats where you need to read "doped chunks", i.e. chunks prefixed by their lengths. My proposal addresses 1 and makes 2 possible. Andrei
Feb 06 2011
prev sibling next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Andrei:

 I've had the opportunity today to put some solid hours of thinking into 
 the relationship (better said the relatedness) of what would be called 
 "buffered streams" and ranges.

This is an important part of the range design. This range is useful for other things too, like: - increasing efficiency of some lazy operations, as already done in Clojure. A buffer is meant to be CPU cache friendly, increasing performance of numeric code too. - Buffered I/O - The chunked lazy parallel map dsimcha is working on - Creating a chunked interface in Phobos for DBMSs See some of my posts about it: http://www.digitalmars.com/d/archives/digitalmars/D/Vectorized_Laziness_100525.html http://www.digitalmars.com/d/archives/digitalmars/D/Re_Vectorized_Laziness_100676.html http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.com&group=digitalmars.D&artnum=103882 http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=125876 Bye, bearophile
Feb 05 2011
prev sibling next sibling parent reply spir <denis.spir gmail.com> writes:
On 02/05/2011 11:09 AM, Jonathan M Davis wrote:
 Hmm. I think that I'd have to have an actual implementation to mess around with
 to say much. My general take on buffered input is that I don't want to worry
 about it. I want it to be buffered so that it's more efficient, but I don't
want to
 have to care about it in how I use it. I would have expected a buffered input
 range to be exactly the same as an input range except that it doesn't really
 just pull in one character behind the scenes. It pulls in 1024 or whatever when
 popFront() would result in the end of the buffer being reached, and you just
get
 the first one with front. The API doesn't reflect the fact that it's buffered
at
 all except perhaps in how you initialize it (by telling how big the buffer is,
 though generally I don't want to have to care about that either).
 [...]
 Regardless, a more normal range could be built on top of what you're
suggesting,
 and it could do essentially what I was thinking buffered ranges would do. So,
 perhaps doing what you're suggesting and building what I was thinking of on top
 of that would be the way to go. That way, if you actually care about messing
 with the buffer, you can, but if not, you just use it normally and the
buffering
 is dealt with underneath.

Exactly. I would love something like: auto bufInputRange (R) (R inputRange, size_t capacity=0) if (...) Meaning one can specify (max) buffering capacity; else there is a standard (re)sizing scheme. Just like dyn array (re)sizing. Side-question to specialists: What should actual buf capacity depend on? Denis -- _________________ vita es estrany spir.wikidot.com
Feb 05 2011
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/5/11 6:57 AM, spir wrote:
 On 02/05/2011 11:09 AM, Jonathan M Davis wrote:
 Hmm. I think that I'd have to have an actual implementation to mess
 around with
 to say much. My general take on buffered input is that I don't want to
 worry
 about it. I want it to be buffered so that it's more efficient, but I
 don't want to
 have to care about it in how I use it. I would have expected a
 buffered input
 range to be exactly the same as an input range except that it doesn't
 really
 just pull in one character behind the scenes. It pulls in 1024 or
 whatever when
 popFront() would result in the end of the buffer being reached, and
 you just get
 the first one with front. The API doesn't reflect the fact that it's
 buffered at
 all except perhaps in how you initialize it (by telling how big the
 buffer is,
 though generally I don't want to have to care about that either).
 [...]
 Regardless, a more normal range could be built on top of what you're
 suggesting,
 and it could do essentially what I was thinking buffered ranges would
 do. So,
 perhaps doing what you're suggesting and building what I was thinking
 of on top
 of that would be the way to go. That way, if you actually care about
 messing
 with the buffer, you can, but if not, you just use it normally and the
 buffering
 is dealt with underneath.

Exactly. I would love something like: auto bufInputRange (R) (R inputRange, size_t capacity=0) if (...) Meaning one can specify (max) buffering capacity; else there is a standard (re)sizing scheme. Just like dyn array (re)sizing. Side-question to specialists: What should actual buf capacity depend on? Denis

My design would allow you to build a buffered input range from an input range, but only with infinite capacity. Andrei
Feb 05 2011
prev sibling parent spir <denis.spir gmail.com> writes:
On 02/05/2011 04:27 PM, Andrei Alexandrescu wrote:
 On 2/5/11 6:57 AM, spir wrote:

 Exactly. I would love something like:
 auto bufInputRange (R) (R inputRange, size_t capacity=0) if (...)
 Meaning one can specify (max) buffering capacity; else there is a
 standard (re)sizing scheme. Just like dyn array (re)sizing.

 Side-question to specialists: What should actual buf capacity depend on?


 Denis

My design would allow you to build a buffered input range from an input range, but only with infinite capacity. Andrei

All right, point taken. Denis -- _________________ vita es estrany spir.wikidot.com
Feb 05 2011
prev sibling next sibling parent reply Tomek =?ISO-8859-2?Q?Sowi=F1ski?= <just ask.me> writes:
Andrei Alexandrescu napisa=B3:

 I hereby suggest we define "buffered input range of T" any range R that=20
 satisfies the following conditions:
=20
 1. R is an input range of T[]
=20
 2. R defines a primitive shiftFront(size_t n). The semantics of the=20
 primitive is that, if r.front.length >=3D n, then shiftFront(n) discards=

 the first n elements in r.front. Subsequently r.front will return a=20
 slice of the remaining elements.
=20
 3. R defines a primitive appendToFront(size_t n). Semantics: adds at=20
 most n more elements from the underlying stream and makes them available=

 in addition to whatever was in front. For example if r.front.length was=20
 1024, after the call r.appendToFront(512) will have r.front have length=20
 1536 of which the first 1024 will be the old front and the rest will be=20
 newly-read elements (assuming that the stream had enough data). If n =3D=

 0, this instructs the stream to add any number of elements at its own=20
 discretion.

I don't see a clear need for the two to be separate. Could they fold into p= opFront(n, m) meaning shiftFront(n); appendToFront(m) ? Nullary popFront() = discards all and loads any number it pleases.
 This is it. I like many things about this design, although I still fear=20
 some fatal flaw may be found with it.

 With these primitives a lot of good operating operating on buffered=20
 streams can be written efficiently. The range is allowed to reuse data=20
 in its buffers (unless that would contradict language invariants, e.g.=20
 if T is invariant), so if client code wants to stash away parts of the=20
 input, it needs to make a copy.

Some users would benefit if they could just pass in a buffer and say "fill'= er up".
 One great thing is that buffered ranges as defined above play very well=20
 with both ranges and built-in arrays - two quintessential parts of D. I=20
 look at this and say, "this all makes sense". For example the design=20
 could be generalized to operate on some random-access range other than=20
 the built-in array, but then I'm thinking, unless some advantage comes=20
 about, why not giving T[] a little special status? Probably everyone=20
 thinks of contiguous memory when thinking "buffers", so here=20
 generalization may be excessive (albeit meaningful).

Contiguous, yes. But I'd rather see front() exposing, say, a circular buffe= r so that appendToFront(n) reallocates only when n > buf.length. --=20 Tomek
Feb 05 2011
next sibling parent reply Jean Crystof <a a.a> writes:
Tomek Sowiski Wrote:

 Andrei Alexandrescu napisa:
 
 I hereby suggest we define "buffered input range of T" any range R that 
 satisfies the following conditions:
 
 1. R is an input range of T[]
 
 2. R defines a primitive shiftFront(size_t n). The semantics of the 
 primitive is that, if r.front.length >= n, then shiftFront(n) discards 
 the first n elements in r.front. Subsequently r.front will return a 
 slice of the remaining elements.
 
 3. R defines a primitive appendToFront(size_t n). Semantics: adds at 
 most n more elements from the underlying stream and makes them available 
 in addition to whatever was in front. For example if r.front.length was 
 1024, after the call r.appendToFront(512) will have r.front have length 
 1536 of which the first 1024 will be the old front and the rest will be 
 newly-read elements (assuming that the stream had enough data). If n = 
 0, this instructs the stream to add any number of elements at its own 
 discretion.

I don't see a clear need for the two to be separate. Could they fold into popFront(n, m) meaning shiftFront(n); appendToFront(m) ? Nullary popFront() discards all and loads any number it pleases.
 This is it. I like many things about this design, although I still fear 
 some fatal flaw may be found with it.

 With these primitives a lot of good operating operating on buffered 
 streams can be written efficiently. The range is allowed to reuse data 
 in its buffers (unless that would contradict language invariants, e.g. 
 if T is invariant), so if client code wants to stash away parts of the 
 input, it needs to make a copy.

Some users would benefit if they could just pass in a buffer and say "fill'er up".
 One great thing is that buffered ranges as defined above play very well 
 with both ranges and built-in arrays - two quintessential parts of D. I 
 look at this and say, "this all makes sense". For example the design 
 could be generalized to operate on some random-access range other than 
 the built-in array, but then I'm thinking, unless some advantage comes 
 about, why not giving T[] a little special status? Probably everyone 
 thinks of contiguous memory when thinking "buffers", so here 
 generalization may be excessive (albeit meaningful).

Contiguous, yes. But I'd rather see front() exposing, say, a circular buffer so that appendToFront(n) reallocates only when n > buf.length.

I find this discussion interesting. There's one idea for an application I'd like to try at some point. Basically a facebook chat thingie, but with richer gaming features. The expected audience will be 10 - 100K simultaneous clients connecting to a single server. Not sure if DOM or SAX will be better. After seeing the Tango's XML benchmarks I was convinced that the implementation platform will be D1/Tango, but now it looks like Phobos is also getting there, propably even outperforming Tango by a clear margin. Since even looking at Tango's documentation has intellectual property problems and likely causes taint, I could make an independent benchmark comparing the two and their interfaces later. But I propaply need to avoid going into too much details, otherwise the Phobos developers wouldn't be able to read it without changing their license. From what I've read so far, the proposed design looks very much like what Tango has now in their I/O framework. But probably Phobos's TLS default and immutable strings improve multithreaded performance even more.
Feb 05 2011
parent "Nick Sabalausky" <a a.a> writes:
"Jean Crystof" <a a.a> wrote in message 
news:iijl2t$10np$1 digitalmars.com...
 Tomek Sowiski Wrote:

 Andrei Alexandrescu napisa:

 I hereby suggest we define "buffered input range of T" any range R that
 satisfies the following conditions:

 1. R is an input range of T[]

 2. R defines a primitive shiftFront(size_t n). The semantics of the
 primitive is that, if r.front.length >= n, then shiftFront(n) discards
 the first n elements in r.front. Subsequently r.front will return a
 slice of the remaining elements.

 3. R defines a primitive appendToFront(size_t n). Semantics: adds at
 most n more elements from the underlying stream and makes them 
 available
 in addition to whatever was in front. For example if r.front.length was
 1024, after the call r.appendToFront(512) will have r.front have length
 1536 of which the first 1024 will be the old front and the rest will be
 newly-read elements (assuming that the stream had enough data). If n =
 0, this instructs the stream to add any number of elements at its own
 discretion.

I don't see a clear need for the two to be separate. Could they fold into popFront(n, m) meaning shiftFront(n); appendToFront(m) ? Nullary popFront() discards all and loads any number it pleases.
 This is it. I like many things about this design, although I still fear
 some fatal flaw may be found with it.

 With these primitives a lot of good operating operating on buffered
 streams can be written efficiently. The range is allowed to reuse data
 in its buffers (unless that would contradict language invariants, e.g.
 if T is invariant), so if client code wants to stash away parts of the
 input, it needs to make a copy.

Some users would benefit if they could just pass in a buffer and say "fill'er up".
 One great thing is that buffered ranges as defined above play very well
 with both ranges and built-in arrays - two quintessential parts of D. I
 look at this and say, "this all makes sense". For example the design
 could be generalized to operate on some random-access range other than
 the built-in array, but then I'm thinking, unless some advantage comes
 about, why not giving T[] a little special status? Probably everyone
 thinks of contiguous memory when thinking "buffers", so here
 generalization may be excessive (albeit meaningful).

Contiguous, yes. But I'd rather see front() exposing, say, a circular buffer so that appendToFront(n) reallocates only when n > buf.length.

I find this discussion interesting. There's one idea for an application I'd like to try at some point. Basically a facebook chat thingie, but with richer gaming features. The expected audience will be 10 - 100K simultaneous clients connecting to a single server. Not sure if DOM or SAX will be better. After seeing the Tango's XML benchmarks I was convinced that the implementation platform will be D1/Tango, but now it looks like Phobos is also getting there, propably even outperforming Tango by a clear margin.

I don'r mean to derail the topic, but if I were aiming for that many simultaneous users I wouldn't even consider using XML at all. Despite MS's, Java's and AJAX's infatuation with it, XML is really only appropriate in two situations: 1. When memory/bandwidth/speed/etc don't matter and 2. When you don't have a choice in the matter.
Feb 05 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/5/11 8:41 AM, Tomek Sowiski wrote:
 Andrei Alexandrescu napisa:

 I hereby suggest we define "buffered input range of T" any range R
 that satisfies the following conditions:

 1. R is an input range of T[]

 2. R defines a primitive shiftFront(size_t n). The semantics of
 the primitive is that, if r.front.length>= n, then shiftFront(n)
 discards the first n elements in r.front. Subsequently r.front will
 return a slice of the remaining elements.

 3. R defines a primitive appendToFront(size_t n). Semantics: adds
 at most n more elements from the underlying stream and makes them
 available in addition to whatever was in front. For example if
 r.front.length was 1024, after the call r.appendToFront(512) will
 have r.front have length 1536 of which the first 1024 will be the
 old front and the rest will be newly-read elements (assuming that
 the stream had enough data). If n = 0, this instructs the stream to
 add any number of elements at its own discretion.

I don't see a clear need for the two to be separate. Could they fold into popFront(n, m) meaning shiftFront(n); appendToFront(m) ? Nullary popFront() discards all and loads any number it pleases.

I think combining the two into one hurts usability as often you want to do one without the other.
 This is it. I like many things about this design, although I still
 fear some fatal flaw may be found with it.

 With these primitives a lot of good operating operating on
 buffered streams can be written efficiently. The range is allowed
 to reuse data in its buffers (unless that would contradict language
 invariants, e.g. if T is invariant), so if client code wants to
 stash away parts of the input, it needs to make a copy.

Some users would benefit if they could just pass in a buffer and say "fill'er up".

Correct. That observation applies to unbuffered input as well.
 One great thing is that buffered ranges as defined above play very
 well with both ranges and built-in arrays - two quintessential
 parts of D. I look at this and say, "this all makes sense". For
 example the design could be generalized to operate on some
 random-access range other than the built-in array, but then I'm
 thinking, unless some advantage comes about, why not giving T[] a
 little special status? Probably everyone thinks of contiguous
 memory when thinking "buffers", so here generalization may be
 excessive (albeit meaningful).

Contiguous, yes. But I'd rather see front() exposing, say, a circular buffer so that appendToFront(n) reallocates only when n> buf.length.

I think circularity is an implementation detail that is poor as a client-side abstraction. Andrei
Feb 05 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/5/11 1:18 PM, Tomek Sowiński wrote:
 Andrei Alexandrescu napisał:

 I don't see a clear need for the two to be separate. Could they fold
 into popFront(n, m) meaning shiftFront(n); appendToFront(m) ? Nullary
 popFront() discards all and loads any number it pleases.

I think combining the two into one hurts usability as often you want to do one without the other.

OK, but if you go this way, what would popFront() do?

Discard everything in the current buffer and fill a new buffer. The new size depends on the stream; for byLine a new line would be read, for byChunk(4096) 4096 more bytes would be read.
 Some users would benefit if they could just pass in a buffer and say
 "fill'er up".

Correct. That observation applies to unbuffered input as well.

Right.
 Contiguous, yes. But I'd rather see front() exposing, say, a circular
 buffer so that appendToFront(n) reallocates only when n>
 buf.length.

I think circularity is an implementation detail that is poor as a client-side abstraction.

I fear efficiency will get abstracted out. Say this is my internal buffer (pipes indicate front() slice): [ooo|oooooo|oo] Now I do appendToFront(3) -- how do you expose the expected front() without moving data?

You do end up moving data, but proportionally little if the buffer is large enough. Andrei
Feb 05 2011
prev sibling next sibling parent Tomek =?ISO-8859-2?Q?Sowi=F1ski?= <just ask.me> writes:
Tomek Sowi=F1ski napisa=B3:

 Contiguous, yes. But I'd rather see front() exposing, say, a circular buf=

 reallocates only when n > buf.length.

I meant: when n + front.length > buf.length. --=20 Tomek
Feb 05 2011
prev sibling next sibling parent Tomek =?UTF-8?B?U293acWEc2tp?= <just ask.me> writes:
Andrei Alexandrescu napisa=C5=82:

 Transparent buffering sounds sensible but in fact it robs you of=20
 important capabilities. It essentially forces you to use grammars with=20
 lookahead 1 for all input operations. Being able to peek forward into=20
 the stream without committing to read from it allows you to e.g. do=20
 operations like "does this stream start with a specific word" etc. As soon

Broken sentence?
Feb 05 2011
prev sibling next sibling parent Tomek =?UTF-8?B?U293acWEc2tp?= <just ask.me> writes:
Andrei Alexandrescu napisa=C5=82:

 I don't see a clear need for the two to be separate. Could they fold
 into popFront(n, m) meaning shiftFront(n); appendToFront(m) ? Nullary
 popFront() discards all and loads any number it pleases. =20

I think combining the two into one hurts usability as often you want to=20 do one without the other.

OK, but if you go this way, what would popFront() do?
 Some users would benefit if they could just pass in a buffer and say
 "fill'er up". =20

Correct. That observation applies to unbuffered input as well.

Right.
 Contiguous, yes. But I'd rather see front() exposing, say, a circular
 buffer so that appendToFront(n) reallocates only when n>
 buf.length.
 =20

I think circularity is an implementation detail that is poor as a=20 client-side abstraction.

I fear efficiency will get abstracted out. Say this is my internal buffer (= pipes indicate front() slice): [ooo|oooooo|oo] Now I do appendToFront(3) -- how do you expose the expected front() without= moving data? --=20 Tomek
Feb 05 2011
prev sibling next sibling parent Tomek =?UTF-8?B?U293acWEc2tp?= <just ask.me> writes:
Jean Crystof napisa=C5=82:

 I find this discussion interesting. There's one idea for an application I=

icher gaming features. The expected audience will be 10 - 100K simultaneous= clients connecting to a single server. Not sure if DOM or SAX will be bett= er. After seeing the Tango's XML benchmarks I was convinced that the implem= entation platform will be D1/Tango, but now it looks like Phobos is also ge= tting there, propably even outperforming Tango by a clear margin. Thanks for having faith ;-)
 Since even looking at Tango's documentation has intellectual property pro=

ing the two and their interfaces later. But I propaply need to avoid going = into too much details, otherwise the Phobos developers wouldn't be able to = read it without changing their license.=20 That would be helpful.
 From what I've read so far, the proposed design looks very much like what=

d immutable strings improve multithreaded performance even more. Well, immutability doesn't help much because a buffer must be written to. Speaking of multithreading, I was thinking of an implementation where an in= ternal thread is doing I/O. It loads data in front of the current front() s= lice, as much as the internal buffer can hold. The motivation is to overlap= content processing and I/O operations so that less time is spent in total.= Although there is some interaction overhead: locking, syncing caches so th= at cores see the same buffer. --=20 Tomek
Feb 05 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday 05 February 2011 07:16:45 Andrei Alexandrescu wrote:
 On 2/5/11 5:09 AM, Jonathan M Davis wrote:
 Hmm. I think that I'd have to have an actual implementation to mess
 around with to say much. My general take on buffered input is that I
 don't want to worry about it. I want it to be buffered so that it's more
 efficient, but I don't want to have to care about it in how I use it. I
 would have expected a buffered input range to be exactly the same as an
 input range except that it doesn't really just pull in one character
 behind the scenes. It pulls in 1024 or whatever when popFront() would
 result in the end of the buffer being reached, and you just get the
 first one with front. The API doesn't reflect the fact that it's
 buffered at all except perhaps in how you initialize it (by telling how
 big the buffer is, though generally I don't want to have to care about
 that either).

Transparent buffering sounds sensible but in fact it robs you of important capabilities. It essentially forces you to use grammars with lookahead 1 for all input operations. Being able to peek forward into the stream without committing to read from it allows you to e.g. do operations like "does this stream start with a specific word" etc. As soon

The thing is though that if I want to be iterating over a string which is buffered (from a file or stream or whatever), I want front to be immutable(char) or char, not immutable(char)[] or char[]. I can see how having an interface which allows startsWith to efficiently check whether the buffered string starts with a particular string makes good sense, but generally, as far as I'm concerned, that's startsWith's problem. How would I even begin to use a buffered range of string[] as a string? Normally, when I've used buffered anything, it's been purely for efficiency reasons. All I've cared about is having a stream or file or whatever. The fact that reading it from the file (or wherever it came from) in a buffered manner is more efficient means that I want it buffered, but that hasn't had any effect on how I've used it. If I want x characters from the file, I ask for x characters. It's the buffered object's problem how many reads that does or doesn't do. You must be thinking of a use case which I don't normal think of or am not aware of. In my experience, buffering has always been an implementation detail that you use because it's more efficient, but you don't worry about it beyond creating a buffered stream rather than an unbuffered one. - Jonathan M Davis
Feb 05 2011
prev sibling next sibling parent reply Heywood Floyd <soul8o8 gmail.com> writes:
Nice!
And evenin'!



Layman's view:
- - - - - - - - - - -
(I'm serious, please don't take my post too seriously. I'm not a heavy =
user of D and I don't want to pollute. I know in NGs exposure means =
influence and I babble a lot. Still, my thoughts, or rather reactions, =
could be of interest, I assume, or I wouldn't be writing this : )


I'm not sure how these buffered input ranges are supposed to be used =
(some mockup sample code would be very cool!), but it seems to me, and =
please correct me if I'm wrong, that it's very desirable for these =
ranges to be interchangeable?

As in, you've built some library that passes around ranges, but then =
some part of it is slow and needs buffered ones. Isn't the point that =
you can then swap out your ranges for buffered ones here and there, but =
continue to have a functioning library?

Reusability, generics, bend the spoon neo and all that?

If not, then ok.

But if yes, then I think these buffered ranges look very troublesome! =
Naughty even!



* * *



Then there's the sneaky break of consistency of the D semantics.

Even if these ranges are not intended to be interchangeable, still, =
changing the (human langauge) semantics that the input ranges already =
define is not good! This makes D a difficult language to get an =
intuitive feel for, I think.

By the definition of input ranges, the word "front" symbolizes the first =
_element_ in a forwards facing queue of elements.

| 1:st |     	<-- front()
| 2:nd |   v-- hidden --v
| 3:rd |
| .....  |
| n:th | <-- "back"

..as front() returns a T.

Then follows that popFront() means "discard the first _element_, so that =
the element that was second now becomes first." And if we can agree to =
that, then shiftFront() is possibly very confusing, and so is =
appendToFront(). They sound like they operate on the first element!=20

So it seems these buffered ranges have redefined the semantics for the =
word "front", as meaning "the view window into the front part of the =
queue". Sneaky!

I mean, imagine being new with D and skimming through the API docs for =
ranges, and picking up these function names at a glance. You'd be =
setting yourself up for one of those =
"aaahaa-now-I-get-why-I-didn't-get-it"-moments for sure. Hmmm.

Still, front() could very well refer to the "front part"=97to a list of =
elements (or the "view window"), and first() could refer to the first =
element. Actually, that would make the most sense! Then an input range =
would be first()/popFirst()/empty(), and a buffered one would have all =
those, but also amend something like front(n)/widenFront(n)/popFront(n), =
but yeah, erhm.

I call for stricter and more consistent semantics!
Decide what "front" means when talking about ranges, and stick to it!
(And I'm talking about human language semantics, not what a function (or =
"primitive"?) does.)

Erh, I tried to sound resolute there. Not my thing really.



* * *



Besides that, "shiftFront" got me thinking about sliding windows, and =
that would actually be cool! As in

| 1st |   '\	     <-- first()
| 2nd |   |-- front() // "view window"
| 3rd |  ./
| 4th | v-- hidden --v
| 5th |
| ...... |
| n:th |

and then calling shiftFront(2) would shift the view window 2 elements =
forward (thus fetching 2 and discarding 2). Seems like a useful feature =
when parsing some encoding with variable point width and known distance =
to the "event horizon", no? As in

code.viewDistance =3D 8;
do{
	auto p =3D code.front()
	if(isLongPoint(p)){
		processLong(p)
		code.shiftFront(8);
	}else if(isPoint(p)){
		process(p)
		code.shiftFront(4);
	}else break;
}while(p);

or something like that.

But the semantic that "shiftFront" would mean the same as popFront(), =
but on a list of elements? Confusing! Surely, at least popFront(n)...

Hm, yeah
Ok I'm all out of coffee!!!
Thanks for your time!
BR
/HF
Feb 05 2011
next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Heywood Floyd" <soul8o8 gmail.com> wrote in message 
news:mailman.1318.1296941395.4748.digitalmars-d puremagic.com...
As in, you've built some library that passes around ranges, but then some 
part of it is slow and needs buffered ones. Isn't the point that you can 
then swap out your ranges for buffered ones here and there, but continue to 
have a functioning library?

The problem with that is that in many many cases it forces unnessisary copying. We can get much better performance with this slightly more "hands-on" version. But that said, if the traditional "hands-free automatic buffering" really is all you need, then such a thing [should] be easily to construct out of the Andrei's style of buffered range.
Then follows that popFront() means "discard the first _element_, so that 
the element that was second now becomes first." And if we can agree to 
that, then shiftFront() is possibly very confusing, and so is 
appendToFront(). They sound like they operate on the first element!

I completely agree. The names of those functions confused the hell out of me until I read Andrei's descriptions of them. Now I understand what they do...but I still don't understand their names at all.
Feb 05 2011
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/5/11 5:22 PM, Nick Sabalausky wrote:
 "Heywood Floyd"<soul8o8 gmail.com>  wrote in message
 news:mailman.1318.1296941395.4748.digitalmars-d puremagic.com...
 As in, you've built some library that passes around ranges, but then some
 part of it is slow and needs buffered ones. Isn't the point that you can
 then swap out your ranges for buffered ones here and there, but continue to
 have a functioning library?

The problem with that is that in many many cases it forces unnessisary copying. We can get much better performance with this slightly more "hands-on" version. But that said, if the traditional "hands-free automatic buffering" really is all you need, then such a thing [should] be easily to construct out of the Andrei's style of buffered range.
 Then follows that popFront() means "discard the first _element_, so that
 the element that was second now becomes first." And if we can agree to
 that, then shiftFront() is possibly very confusing, and so is
 appendToFront(). They sound like they operate on the first element!

I completely agree. The names of those functions confused the hell out of me until I read Andrei's descriptions of them. Now I understand what they do...but I still don't understand their names at all.

Better names are always welcome! Andrei
Feb 05 2011
next sibling parent Adam D. Ruppe <destructionator gmail.com> writes:
This sounds similar to how my network code works. I called
the functions fetchMore() to append to the buffer and eat(int n)
to advance the front position.
Feb 05 2011
prev sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:iil3lv$1bb1$1 digitalmars.com...
 On 2/5/11 5:22 PM, Nick Sabalausky wrote:
 "Heywood Floyd"<soul8o8 gmail.com>  wrote in message
 news:mailman.1318.1296941395.4748.digitalmars-d puremagic.com...
 As in, you've built some library that passes around ranges, but then 
 some
 part of it is slow and needs buffered ones. Isn't the point that you can
 then swap out your ranges for buffered ones here and there, but continue 
 to
 have a functioning library?

The problem with that is that in many many cases it forces unnessisary copying. We can get much better performance with this slightly more "hands-on" version. But that said, if the traditional "hands-free automatic buffering" really is all you need, then such a thing [should] be easily to construct out of the Andrei's style of buffered range.
 Then follows that popFront() means "discard the first _element_, so that
 the element that was second now becomes first." And if we can agree to
 that, then shiftFront() is possibly very confusing, and so is
 appendToFront(). They sound like they operate on the first element!

I completely agree. The names of those functions confused the hell out of me until I read Andrei's descriptions of them. Now I understand what they do...but I still don't understand their names at all.

Better names are always welcome!

Borrowing slightly from Adam: discard and fetch?
Feb 05 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/6/11 6:01 EST, Tomek Sowiski wrote:
 Nick Sabalausky napisa:

 discard and fetch?

I like that.

What's missing is the part that they refer to front. Maybe discardFromFront() and fetchToFront()? But then I like discardFromFront() and appendToFront() better - the latter is about as long and more informative. Don't forget that these are relatively rarely used. Andrei
Feb 06 2011
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/6/11 8:57 PM, Robert Jacques wrote:
 On Sun, 06 Feb 2011 10:43:47 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 On 2/6/11 6:01 EST, Tomek Sowiński wrote:
 Nick Sabalausky napisał:

 discard and fetch?

I like that.

What's missing is the part that they refer to front. Maybe discardFromFront() and fetchToFront()? But then I like discardFromFront() and appendToFront() better - the latter is about as long and more informative. Don't forget that these are relatively rarely used. Andrei

Actually, I don't think these functions would be relatively rarely used. I don't see that many people using a buffered input's popFront. Instead I see shiftFront in its place and an appendToFront call has to be made whenever buffer.front.empty.

Both byLine and byChunk are buffered inputs, are often used, and will have seldom use for the added functions. Andrei
Feb 06 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/6/11 10:37 PM, Robert Jacques wrote:
 On Sun, 06 Feb 2011 21:53:01 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 On 2/6/11 8:57 PM, Robert Jacques wrote:
 On Sun, 06 Feb 2011 10:43:47 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 On 2/6/11 6:01 EST, Tomek Sowiński wrote:
 Nick Sabalausky napisał:

 discard and fetch?

I like that.

What's missing is the part that they refer to front. Maybe discardFromFront() and fetchToFront()? But then I like discardFromFront() and appendToFront() better - the latter is about as long and more informative. Don't forget that these are relatively rarely used. Andrei

Actually, I don't think these functions would be relatively rarely used. I don't see that many people using a buffered input's popFront. Instead I see shiftFront in its place and an appendToFront call has to be made whenever buffer.front.empty.

Both byLine and byChunk are buffered inputs, are often used, and will have seldom use for the added functions. Andrei

Yes, but byLine is a higher order meta-range designed primarily for end users. I believe that internally, byLine would use shiftFront/appendToFront, as would virtually all library code. I do apologize for thinking only as a library writer, but you need to remember those of us writing the JSON, XML, separated value, etc parsers too, when designing the api.

I understand. Ultimately such widely used parsers would be themselves encapsulated in library (Phobos?) modules. The general idea is that straight reading tasks only need very simple code, and more sophisticated reading tasks would need to use a couple more primitives. That's not that bad, is it? Andrei
Feb 06 2011
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/6/11 9:47 PM, Torarin wrote:
 2011/2/7 Robert Jacques<sandford jhu.edu>:
 On Sun, 06 Feb 2011 10:43:47 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org>  wrote:

 On 2/6/11 6:01 EST, Tomek Sowiński wrote:
 Nick Sabalausky napisał:

 discard and fetch?

I like that.

What's missing is the part that they refer to front. Maybe discardFromFront() and fetchToFront()? But then I like discardFromFront() and appendToFront() better - the latter is about as long and more informative. Don't forget that these are relatively rarely used. Andrei

Actually, I don't think these functions would be relatively rarely used. I don't see that many people using a buffered input's popFront. Instead I see shiftFront in its place and an appendToFront call has to be made whenever buffer.front.empty.

Why not popFront if empty? Maybe you could use appendToFront if you knew that you needed to expand the stream's buffer, but that doesn't sound like a common case. Torarin

Exactly. Consider line continuations. Most of the time you read one line at a time and everything goes swell. On occasion you'll have a line continuation convention (line ends with a backslash, unmatched quote etc.) and you need to expand the current buffer to gobble the next line. Andrei
Feb 06 2011
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/6/11 10:59 PM, Robert Jacques wrote:
 On Sun, 06 Feb 2011 21:47:48 -0500, Torarin <torarind gmail.com> wrote:

 2011/2/7 Robert Jacques <sandford jhu.edu>:
 On Sun, 06 Feb 2011 10:43:47 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 On 2/6/11 6:01 EST, Tomek Sowiński wrote:
 Nick Sabalausky napisał:

 discard and fetch?

I like that.

What's missing is the part that they refer to front. Maybe discardFromFront() and fetchToFront()? But then I like discardFromFront() and appendToFront() better - the latter is about as long and more informative. Don't forget that these are relatively rarely used. Andrei

Actually, I don't think these functions would be relatively rarely used. I don't see that many people using a buffered input's popFront. Instead I see shiftFront in its place and an appendToFront call has to be made whenever buffer.front.empty.

Why not popFront if empty?

Because even reading UTF-8 requires more than 1-byte of information. Basically, any routine that processes a raw stream is going to have to handle the case where what they're processing straddles the buffer boundary. Now, if the routine wraps the raw stream in some higher-order range, such as byLine, which guarantees them that none of their inputs straddle, great. But it would be negligent to neglect those coders writing the higher-level ranges.

They aren't being neglected. If you need to get more stuff in the current unit of work, use appendToFront(). Let's restart this. What do you want to do that you can't do with the proposed API? Andrei
Feb 06 2011
prev sibling parent spir <denis.spir gmail.com> writes:
On 02/06/2011 04:11 AM, Andrei Alexandrescu wrote:
 On 2/5/11 5:22 PM, Nick Sabalausky wrote:
 "Heywood Floyd"<soul8o8 gmail.com> wrote in message
 news:mailman.1318.1296941395.4748.digitalmars-d puremagic.com...
 As in, you've built some library that passes around ranges, but then some
 part of it is slow and needs buffered ones. Isn't the point that you can
 then swap out your ranges for buffered ones here and there, but continue to
 have a functioning library?

The problem with that is that in many many cases it forces unnessisary copying. We can get much better performance with this slightly more "hands-on" version. But that said, if the traditional "hands-free automatic buffering" really is all you need, then such a thing [should] be easily to construct out of the Andrei's style of buffered range.
 Then follows that popFront() means "discard the first _element_, so that
 the element that was second now becomes first." And if we can agree to
 that, then shiftFront() is possibly very confusing, and so is
 appendToFront(). They sound like they operate on the first element!

I completely agree. The names of those functions confused the hell out of me until I read Andrei's descriptions of them. Now I understand what they do...but I still don't understand their names at all.

Better names are always welcome!

If append actually appends into buffer (what I understand as of now), then appendToBuf(er). For shiftFront, maybe eatSlice? popFrontSlice would be very good (esp as opposed to a hypothetical poBackSlice), to hint the operation happens at head (because "pop" alone means at back). But as others have said "front" in the context of ranges has now an established sense of "first" (just like "head" or "car" for lists, by the way), or maybe more exactly "current". Denis -- _________________ vita es estrany spir.wikidot.com
Feb 06 2011
prev sibling parent spir <denis.spir gmail.com> writes:
On 02/05/2011 11:22 PM, Nick Sabalausky wrote:
 "Heywood Floyd"<soul8o8 gmail.com>  wrote in message
 news:mailman.1318.1296941395.4748.digitalmars-d puremagic.com...
 As in, you've built some library that passes around ranges, but then some
 part of it is slow and needs buffered ones. Isn't the point that you can
 then swap out your ranges for buffered ones here and there, but continue to
 have a functioning library?

The problem with that is that in many many cases it forces unnessisary copying. We can get much better performance with this slightly more "hands-on" version. But that said, if the traditional "hands-free automatic buffering" really is all you need, then such a thing [should] be easily to construct out of the Andrei's style of buffered range.
 Then follows that popFront() means "discard the first _element_, so that
 the element that was second now becomes first." And if we can agree to
 that, then shiftFront() is possibly very confusing, and so is
 appendToFront(). They sound like they operate on the first element!

I completely agree. The names of those functions confused the hell out of me until I read Andrei's descriptions of them. Now I understand what they do...but I still don't understand their names at all.

Same here; thought: "maybe he meant shiftBuf() & appendToBuf(), or such?". (Then, as nobody reacted about that point, thought: "You're the stupid one; shut your mouth!") I also agree with Heywood about first() / popFirst(). Then, shiftFront() / appendToFront() would be less confusing --but still hard to guess (for me). I wonder if his "view window" is the whole or part of the buffer. Well... (Else, I actually share most of Heywood's views, I guess, at least at first read.) Denis -- _________________ vita es estrany spir.wikidot.com
Feb 05 2011
prev sibling next sibling parent Torarin <torarind gmail.com> writes:
2011/2/5 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org>:
 I hereby suggest we define "buffered input range of T" any range R that
 satisfies the following conditions:

 1. R is an input range of T[]

 2. R defines a primitive shiftFront(size_t n). The semantics of the
 primitive is that, if r.front.length >= n, then shiftFront(n) discards the
 first n elements in r.front. Subsequently r.front will return a slice of the
 remaining elements.

 3. R defines a primitive appendToFront(size_t n). Semantics: adds at most n
 more elements from the underlying stream and makes them available in
 addition to whatever was in front. For example if r.front.length was 1024,
 after the call r.appendToFront(512) will have r.front have length 1536 of
 which the first 1024 will be the old front and the rest will be newly-read
 elements (assuming that the stream had enough data). If n = 0, this
 instructs the stream to add any number of elements at its own discretion.

This is really cool. I realise now that appendToFront fills the gap in the design providing only shiftFront/advance. I also thought their names were well-chosen. Torarin
Feb 05 2011
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Sat, 05 Feb 2011 17:22:01 -0500, Nick Sabalausky <a a.a> wrote:

 "Heywood Floyd" <soul8o8 gmail.com> wrote in message
 news:mailman.1318.1296941395.4748.digitalmars-d puremagic.com...
 As in, you've built some library that passes around ranges, but then  
 some
 part of it is slow and needs buffered ones. Isn't the point that you can
 then swap out your ranges for buffered ones here and there, but  
 continue to
 have a functioning library?

The problem with that is that in many many cases it forces unnessisary copying. We can get much better performance with this slightly more "hands-on" version. But that said, if the traditional "hands-free automatic buffering" really is all you need, then such a thing [should] be easily to construct out of the Andrei's style of buffered range.
 Then follows that popFront() means "discard the first _element_, so that
 the element that was second now becomes first." And if we can agree to
 that, then shiftFront() is possibly very confusing, and so is
 appendToFront(). They sound like they operate on the first element!

I completely agree. The names of those functions confused the hell out of me until I read Andrei's descriptions of them. Now I understand what they do...but I still don't understand their names at all.

See point of Andrei's post: 1. R is an input range of T[] Which means that front returns an array, not a single element. So they sound like they operate on the first element, because that's exactly what they do. Conceptually, you need to think of buffered inputs as range of ranges, not a range of elements.
Feb 05 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 02/05/2011 06:42 PM, Heywood Floyd wrote:
 Nice!
 And evenin'!



 Layman's view:
 - - - - - - - - - - -
 (I'm serious, please don't take my post too seriously. I'm not a heavy user of
D and I don't want to pollute. I know in NGs exposure means influence and I
babble a lot. Still, my thoughts, or rather reactions, could be of interest, I
assume, or I wouldn't be writing this : )


 I'm not sure how these buffered input ranges are supposed to be used (some
mockup sample code would be very cool!), but it seems to me, and please correct
me if I'm wrong, that it's very desirable for these ranges to be
interchangeable?

 As in, you've built some library that passes around ranges, but then some part
of it is slow and needs buffered ones. Isn't the point that you can then swap
out your ranges for buffered ones here and there, but continue to have a
functioning library?

 Reusability, generics, bend the spoon neo and all that?

 If not, then ok.

 But if yes, then I think these buffered ranges look very troublesome! Naughty
even!



 * * *



 Then there's the sneaky break of consistency of the D semantics.

 Even if these ranges are not intended to be interchangeable, still, changing
the (human langauge) semantics that the input ranges already define is not
good! This makes D a difficult language to get an intuitive feel for, I think.

 By the definition of input ranges, the word "front" symbolizes the first
_element_ in a forwards facing queue of elements.

 | 1:st |     	<-- front()
 | 2:nd |   v-- hidden --v
 | 3:rd |
 | .....  |
 | n:th |<-- "back"

 ..as front() returns a T.

 Then follows that popFront() means "discard the first _element_, so that the
element that was second now becomes first." And if we can agree to that, then
shiftFront() is possibly very confusing, and so is appendToFront(). They sound
like they operate on the first element!

 So it seems these buffered ranges have redefined the semantics for the word
"front", as meaning "the view window into the front part of the queue". Sneaky!

 I mean, imagine being new with D and skimming through the API docs for ranges,
and picking up these function names at a glance. You'd be setting yourself up
for one of those "aaahaa-now-I-get-why-I-didn't-get-it"-moments for sure. Hmmm.

 Still, front() could very well refer to the "front part"—to a list of
elements (or the "view window"), and first() could refer to the first element.
Actually, that would make the most sense! Then an input range would be
first()/popFirst()/empty(), and a buffered one would have all those, but also
amend something like front(n)/widenFront(n)/popFront(n), but yeah, erhm.

+++ (everything above)
 I call for stricter and more consistent semantics!
 Decide what "front" means when talking about ranges, and stick to it!
 (And I'm talking about human language semantics, not what a function (or
"primitive"?) does.)

 Erh, I tried to sound resolute there. Not my thing really.

pleased to see there is at least one other programmer still considering that "semantic" applies to human thoughts, rather than machine process...
 * * *



 Besides that, "shiftFront" got me thinking about sliding windows, and that
would actually be cool! As in

 | 1st |   '\	<-- first()
 | 2nd |   |-- front() // "view window"
 | 3rd |  ./
 | 4th | v-- hidden --v
 | 5th |
 | ...... |
 | n:th |

There is an off-by-one error between 1st & first, I guess ;-) What's your "view window"? Is it buffer, or the needed amount of lookahead, or what else? How would you draw the buffer, on the first picture or the one above? "Sliding window" is, for me, the mental picture my brain intuitively forms when thinking at buffered input. But the sliding move may not be smooth (element per element), instead could happen as is most practical or efficient; as long as it remains a point not exposed on the interface (or only on request by client code). Meaning there would be an independant index pointing to current/first/front element, in the buffer or the window, & automagically maintained when sliding happens (index -= offset).
 and then calling shiftFront(2) would shift the view window 2 elements forward
(thus fetching 2 and discarding 2). Seems like a useful feature when parsing
some encoding with variable point width and known distance to the "event
horizon", no? As in

 code.viewDistance = 8;
 do{
 	auto p = code.front()
 	if(isLongPoint(p)){
 		processLong(p)
 		code.shiftFront(8);
 	}else if(isPoint(p)){
 		process(p)
 		code.shiftFront(4);
 	}else break;
 }while(p);

 or something like that.

 But the semantic that "shiftFront" would mean the same as popFront(), but on a
list of elements? Confusing! Surely, at least popFront(n)...

 Hm, yeah
 Ok I'm all out of coffee!!!
 Thanks for your time!
 BR
 /HF

Veeery interesting message, thank you. I share your care for correct naming. And the rest, actually. Wish you would post regularly. Denis -- _________________ vita es estrany spir.wikidot.com
Feb 05 2011
prev sibling next sibling parent Tomek =?ISO-8859-2?B?U293afFza2k=?= <just ask.me> writes:
Andrei Alexandrescu napisa=B3:

 I fear efficiency will get abstracted out. Say this is my internal buff=


 [ooo|oooooo|oo]

 Now I do appendToFront(3) -- how do you expose the expected front() wit=


=20
 You do end up moving data, but proportionally little if the buffer is=20
 large enough.

It still matters for frequent big munches. I'd like a minimum memory option= if that's neccessary. --=20 Tomek
Feb 05 2011
prev sibling next sibling parent Tomek =?ISO-8859-2?B?U293afFza2k=?= <just ask.me> writes:
Nick Sabalausky napisa=B3:

 discard and fetch?

I like that.
Feb 06 2011
prev sibling next sibling parent Tomek =?ISO-8859-2?B?U293afFza2k=?= <just ask.me> writes:
Andrei Alexandrescu napisa=B3:

 Also: could a (truely) circular buffer help & solve the above copy
 problem, concretely? =20

Not if you want infinite lookahead, which I think is what any modern=20 buffering system should offer.

Truely circular, probably not, but a wrap-around slice (circular view of le= ngth at most underlying.length) does offer that and solves the copy problem= with style. --=20 Tomek
Feb 06 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 02/06/2011 08:49 PM, Tomek Sowiński wrote:
 Andrei Alexandrescu napisał:

 Also: could a (truely) circular buffer help&  solve the above copy
 problem, concretely?

Not if you want infinite lookahead, which I think is what any modern buffering system should offer.

Truely circular, probably not, but a wrap-around slice (circular view of length at most underlying.length) does offer that and solves the copy problem with style.

Right. _________________ vita es estrany spir.wikidot.com
Feb 06 2011
prev sibling next sibling parent Tomek =?ISO-8859-2?B?U293afFza2k=?= <just ask.me> writes:
Andrei Alexandrescu napisa=B3:

 Truely circular, probably not, but a wrap-around slice (circular view
 of length at most underlying.length) does offer that and solves the
 copy problem with style. =20

Right. =20

With fixed lookahead you can't do a lot of things - such as line=20 continuation in C programs or CSV files. There are plenty of other=20 examples. Generally I believe k-lookahead is a thing of the past and=20 infinite-lookahead is where the future is.

Amen. But I don't see how wrap-around slices stand in the way. When you nee= d more capacity, resize the internal buffer array and let front() expose a = new wrap-around slice. Just like you'd do with T[]. The only difference is = you don't care if a fetch goes over the edge. --=20 Tomek
Feb 06 2011
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Sun, 06 Feb 2011 10:43:47 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 2/6/11 6:01 EST, Tomek Sowiński wrote:
 Nick Sabalausky napisał:

 discard and fetch?

I like that.

What's missing is the part that they refer to front. Maybe discardFromFront() and fetchToFront()? But then I like discardFromFront() and appendToFront() better - the latter is about as long and more informative. Don't forget that these are relatively rarely used. Andrei

Actually, I don't think these functions would be relatively rarely used. I don't see that many people using a buffered input's popFront. Instead I see shiftFront in its place and an appendToFront call has to be made whenever buffer.front.empty.
Feb 06 2011
prev sibling next sibling parent Torarin <torarind gmail.com> writes:
2011/2/7 Robert Jacques <sandford jhu.edu>:
 On Sun, 06 Feb 2011 10:43:47 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 On 2/6/11 6:01 EST, Tomek Sowi=C5=84ski wrote:
 Nick Sabalausky napisa=C5=82:

 discard and fetch?

I like that.

What's missing is the part that they refer to front. Maybe discardFromFront() and fetchToFront()? But then I like discardFromFront(=


 and appendToFront() better - the latter is about as long and more
 informative.

 Don't forget that these are relatively rarely used.


 Andrei

Actually, I don't think these functions would be relatively rarely used. =

 don't see that many people using a buffered input's popFront. Instead I s=

 shiftFront in its place and an appendToFront call has to be made whenever
 buffer.front.empty.

Why not popFront if empty? Maybe you could use appendToFront if you knew that you needed to expand the stream's buffer, but that doesn't sound like a common case. Torarin
Feb 06 2011
prev sibling next sibling parent Torarin <torarind gmail.com> writes:
2011/2/7 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org>:
 On 2/6/11 9:47 PM, Torarin wrote:
 2011/2/7 Robert Jacques<sandford jhu.edu>:
 On Sun, 06 Feb 2011 10:43:47 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> =A0wrote:

 On 2/6/11 6:01 EST, Tomek Sowi=F1ski wrote:
 Nick Sabalausky napisa=B3:

 discard and fetch?

I like that.

What's missing is the part that they refer to front. Maybe discardFromFront() and fetchToFront()? But then I like discardFromFront() and appendToFront() better - the latter is about as long and more informative. Don't forget that these are relatively rarely used. Andrei

Actually, I don't think these functions would be relatively rarely used=



 I
 don't see that many people using a buffered input's popFront. Instead I
 see
 shiftFront in its place and an appendToFront call has to be made whenev=



 buffer.front.empty.

Why not popFront if empty? Maybe you could use appendToFront if you knew that you needed to expand the stream's buffer, but that doesn't sound like a common case. Torarin

Exactly. Consider line continuations. Most of the time you read one line =

 a time and everything goes swell. On occasion you'll have a line
 continuation convention (line ends with a backslash, unmatched quote etc.=

 and you need to expand the current buffer to gobble the next line.


 Andrei

Yes, it's really convenient. You don't have to start messing with your own buffer, and you avoid the temptation of doing one-element reads. What seems more unlikely is using it on an empty front, though. Torarin
Feb 06 2011
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Sun, 06 Feb 2011 21:53:01 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 2/6/11 8:57 PM, Robert Jacques wrote:
 On Sun, 06 Feb 2011 10:43:47 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 On 2/6/11 6:01 EST, Tomek Sowiński wrote:
 Nick Sabalausky napisał:

 discard and fetch?

I like that.

What's missing is the part that they refer to front. Maybe discardFromFront() and fetchToFront()? But then I like discardFromFront() and appendToFront() better - the latter is about as long and more informative. Don't forget that these are relatively rarely used. Andrei

Actually, I don't think these functions would be relatively rarely used. I don't see that many people using a buffered input's popFront. Instead I see shiftFront in its place and an appendToFront call has to be made whenever buffer.front.empty.

Both byLine and byChunk are buffered inputs, are often used, and will have seldom use for the added functions. Andrei

Yes, but byLine is a higher order meta-range designed primarily for end users. I believe that internally, byLine would use shiftFront/appendToFront, as would virtually all library code. I do apologize for thinking only as a library writer, but you need to remember those of us writing the JSON, XML, separated value, etc parsers too, when designing the api.
Feb 06 2011
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Sun, 06 Feb 2011 21:47:48 -0500, Torarin <torarind gmail.com> wrote:

 2011/2/7 Robert Jacques <sandford jhu.edu>:
 On Sun, 06 Feb 2011 10:43:47 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 On 2/6/11 6:01 EST, Tomek Sowiński wrote:
 Nick Sabalausky napisał:

 discard and fetch?

I like that.

What's missing is the part that they refer to front. Maybe discardFromFront() and fetchToFront()? But then I like discardFromFront() and appendToFront() better - the latter is about as long and more informative. Don't forget that these are relatively rarely used. Andrei

Actually, I don't think these functions would be relatively rarely used. I don't see that many people using a buffered input's popFront. Instead I see shiftFront in its place and an appendToFront call has to be made whenever buffer.front.empty.

Why not popFront if empty?

Because even reading UTF-8 requires more than 1-byte of information. Basically, any routine that processes a raw stream is going to have to handle the case where what they're processing straddles the buffer boundary. Now, if the routine wraps the raw stream in some higher-order range, such as byLine, which guarantees them that none of their inputs straddle, great. But it would be negligent to neglect those coders writing the higher-level ranges.
Feb 06 2011
prev sibling next sibling parent Torarin <torarind gmail.com> writes:
2011/2/7 Robert Jacques <sandford jhu.edu>:
 On Sun, 06 Feb 2011 21:47:48 -0500, Torarin <torarind gmail.com> wrote:

 2011/2/7 Robert Jacques <sandford jhu.edu>:
 On Sun, 06 Feb 2011 10:43:47 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 On 2/6/11 6:01 EST, Tomek Sowi=C5=84ski wrote:
 Nick Sabalausky napisa=C5=82:

 discard and fetch?

I like that.

What's missing is the part that they refer to front. Maybe discardFromFront() and fetchToFront()? But then I like discardFromFront() and appendToFront() better - the latter is about as long and more informative. Don't forget that these are relatively rarely used. Andrei

Actually, I don't think these functions would be relatively rarely used=



 I
 don't see that many people using a buffered input's popFront. Instead I
 see
 shiftFront in its place and an appendToFront call has to be made whenev=



 buffer.front.empty.

Why not popFront if empty?

Because even reading UTF-8 requires more than 1-byte of information. Basically, any routine that processes a raw stream is going to have to handle the case where what they're processing straddles the buffer bounda=

 Now, if the routine wraps the raw stream in some higher-order range, such=

 byLine, which guarantees them that none of their inputs straddle, great. =

 it would be negligent to neglect those coders writing the higher-level
 ranges.

But popFront also reads more than 1 byte. Unless you call appendToFront with a larger value than the current buffer size, unless I have misunderstood, they should end up doing the same thing. Torarin
Feb 06 2011
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Sun, 06 Feb 2011 23:01:12 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 2/6/11 10:59 PM, Robert Jacques wrote:
 On Sun, 06 Feb 2011 21:47:48 -0500, Torarin <torarind gmail.com> wrote:

 2011/2/7 Robert Jacques <sandford jhu.edu>:
 On Sun, 06 Feb 2011 10:43:47 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 On 2/6/11 6:01 EST, Tomek Sowiński wrote:
 Nick Sabalausky napisał:

 discard and fetch?

I like that.

What's missing is the part that they refer to front. Maybe discardFromFront() and fetchToFront()? But then I like discardFromFront() and appendToFront() better - the latter is about as long and more informative. Don't forget that these are relatively rarely used. Andrei

Actually, I don't think these functions would be relatively rarely used. I don't see that many people using a buffered input's popFront. Instead I see shiftFront in its place and an appendToFront call has to be made whenever buffer.front.empty.

Why not popFront if empty?

Because even reading UTF-8 requires more than 1-byte of information. Basically, any routine that processes a raw stream is going to have to handle the case where what they're processing straddles the buffer boundary. Now, if the routine wraps the raw stream in some higher-order range, such as byLine, which guarantees them that none of their inputs straddle, great. But it would be negligent to neglect those coders writing the higher-level ranges.

They aren't being neglected. If you need to get more stuff in the current unit of work, use appendToFront(). Let's restart this. What do you want to do that you can't do with the proposed API? Andrei

Nothing. I like the API and it makes things like byChunk actually usable in my mind. My objection was to your 'relatively rarely used' comment and the implications of that with regard to API design. I have also just realized that made a typo when talking about appendToFront; I meant a call to appendToFront would be common when your working slice of .front has run out, but you're not ready to call shiftFront (because you're in the middle of parsing something, etc). The way I stated it, a call to popFront and a call to appendToFront would be (mostly) equivalent. Which may has confused people. Sorry.
Feb 06 2011
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 05 Feb 2011 00:46:40 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 I've had the opportunity today to put some solid hours of thinking into  
 the relationship (better said the relatedness) of what would be called  
 "buffered streams" and ranges. They have some commonalities and some  
 differences, but it's been difficult to capture them. I think now I have  
 a clear view, caused by a few recent discussions. One was the CSV reader  
 discussed on the Phobos list; another was the discussion on defining the  
 "right" std.xml.

[snip]
 What do you all think?

I haven't read many of the responses, but I'll say again what I've always said. The range concept does not fit streams very well. I think a range can be built on a stream, but I think a buffered stream should be it's own type (similar to how you laid it out a few weeks ago). IMO, a stream should be a simple class hierarchy that defines input/output and buffering. Then ranges can be built on top of the stream to interface with other parts of phobos. Now, I think as an *input parameter* for algorithms that wish to work with streams (or other ranges), a range of T[] is most appropriate. -Steve
Feb 07 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/7/11 7:53 AM, Steven Schveighoffer wrote:
 On Sat, 05 Feb 2011 00:46:40 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 I've had the opportunity today to put some solid hours of thinking
 into the relationship (better said the relatedness) of what would be
 called "buffered streams" and ranges. They have some commonalities and
 some differences, but it's been difficult to capture them. I think now
 I have a clear view, caused by a few recent discussions. One was the
 CSV reader discussed on the Phobos list; another was the discussion on
 defining the "right" std.xml.

[snip]
 What do you all think?

I haven't read many of the responses, but I'll say again what I've always said. The range concept does not fit streams very well. I think a range can be built on a stream, but I think a buffered stream should be it's own type (similar to how you laid it out a few weeks ago). IMO, a stream should be a simple class hierarchy that defines input/output and buffering. Then ranges can be built on top of the stream to interface with other parts of phobos.

One good thing about the current proposal is that it integrates seamlessly with that one. Andrei
Feb 07 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 02/07/2011 02:01 PM, Steven Schveighoffer wrote:
 On Sat, 05 Feb 2011 10:02:47 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 On 2/5/11 2:45 AM, Michel Fortin wrote:
 One thing I'm wondering is whether it'd be more efficient if we could
 provide our own buffer to be filled. In cases where you want to preserve
 the data, this could let you avoid double-copying: first copy in the
 temporary buffer and then at the permanent storage location. If you need
 the data only temporarily however providing your buffer to be filled
 might be less efficient for a range that can't avoid copying to the
 temporary buffer for some reason..

Generally when one says "I want the stream to copy data straight into my buffers" this is the same as "I want the stream to be unbuffered". So if you want to provide your own buffers to be filled, we need to discuss refining the design of unbuffered input - for example by adding an optional routine for bulk transfer to input ranges.

I may want to store 1% of a very large file. You are saying I must either a) unbuffer the entire file (handling the buffering on my own) or b) take the penalty and double copy the data. I want c) temporarily use my buffer for buffering until I say to stop. The range interface doesn't make this easy...

This looks very similar to a possible current use case of mine. (lookahead on demand --> possible backtracking) Denis -- _________________ vita es estrany spir.wikidot.com
Feb 07 2011
prev sibling parent Kagamin <spam here.lot> writes:
Andrei Alexandrescu Wrote:

 With these primitives a lot of good operating operating on buffered 
 streams can be written efficiently. The range is allowed to reuse data 
 in its buffers (unless that would contradict language invariants, e.g. 
 if T is invariant), so if client code wants to stash away parts of the 
 input, it needs to make a copy.

This surely satisfies most needs for buffered input. I'm thinking about adaptive caller which can do tricks based on the stream content. Say, strings are usually serialized as |length|data| so the caller can preallocate buffer of exact length and fill it directly. Will unbuffered file stream bypass system cache? If yes, you'll have poor performance if the file is already in cache. If no, you'll have double copy if the caller wants to save the data: from system cache to the range's buffer and from the range's buffer to the caller's buffer.
Feb 07 2011