buffered input

Michel Fortin michel.fortin at michelf.com
Fri Feb 4 23:45:32 PST 2011


On 2011-02-05 00:46:40 -0500, Andrei Alexandrescu 
<SeeWebsiteForEmail at 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 at michelf.com
http://michelf.com/



More information about the Digitalmars-d mailing list