On 3/6/2014 4:43 PM, H. S. Teoh wrote:
> On Thu, Mar 06, 2014 at 01:26:46PM -0800, Walter Bright wrote:
>> A major goal for D in the short term is to reduce reliance in Phobos
>> on the GC. I was looking at std.string last night, and I noticed a
>> couple things:
>>
>> 1. The inputs are constrained to being strings. This is overly
>> restrictive, the inputs should be InputRanges.
>>
>> 2. The outputs should be a range, too. In fact, the string functions
>> should become algorithms. Then they won't need to allocate any
>> memory at all.
> [...]
>
> What about using output ranges?

A great question. I tend to regard output ranges as suitable for a container to expose. An algorithm reads an InputRange, and presents its output as another InputRange. This is so that algorithms can be easily chained together by the user, and the last algorithm in the chain would be std.algorithm.copy(OutputRange).

For example, we could implement toStringz() as an algorithm that looks like:

    auto toStringz(S)(S s) {
        return chain(s, repeat(0, 1))
    }

and use it like this:

    string s = ...;
    char[] buffer = ...;
    s.toStringz.copy(buffer);

Note how the algorithm version of toStringz does not allocate any memory. buffer would be the output range, but note how what it actually is is, and how its memory is allocated, is selected by the user.

(std.buffer.scopebuffer is ideal for this sort of usage.)

std.file is loaded with calls to toStringz(), each of which leaks memory quite unnecessarily. Using an algorithm version of toStringz(), along with scopebuffer, will neatly eliminated these leaks.

You might be tempted to think that these are just little leaks, who cares. But I recently wrote a D program that did tens of thousands of file operations, and those little leaks turned into a raging river.

On Thu, Mar 06, 2014 at 05:15:45PM -0800, Walter Bright wrote:
> On 3/6/2014 4:43 PM, H. S. Teoh wrote:
> >On Thu, Mar 06, 2014 at 01:26:46PM -0800, Walter Bright wrote:
> >>A major goal for D in the short term is to reduce reliance in Phobos on the GC. I was looking at std.string last night, and I noticed a couple things:
> >>
> >>1. The inputs are constrained to being strings. This is overly restrictive, the inputs should be InputRanges.
> >>
> >>2. The outputs should be a range, too. In fact, the string functions should become algorithms. Then they won't need to allocate any memory at all.
> >[...]
> >
> >What about using output ranges?
> 
> A great question. I tend to regard output ranges as suitable for a container to expose. An algorithm reads an InputRange, and presents its output as another InputRange. This is so that algorithms can be easily chained together by the user, and the last algorithm in the chain would be std.algorithm.copy(OutputRange).

After some thought, and also some recent experiences, I've come to the same conclusion.  Output ranges are basically sinks, which means they are no good for further chaining (attempting to do so is an exercise in frustration). So pretty much everything that generates or transforms data should return an input range, and output ranges should only be used when you're going to stop processing the data at that point, e.g., save it into a buffer, write to a file, etc..

Unfortunately, input ranges are somewhat tedious to write -- nice foreach loops have to be broken up into .empty, .front, .popFront, which is a lot of boilerplate code and not so nice in inner loops (though I suppose the idea is to improve compiler inlining to handle these cases). I wonder if a mid- to long-term goal for D would be to ease writing input ranges by moving some of the boilerplate into the language, or providing range builder facilities in Phobos. The most nagging part of writing input ranges in the current language is the inability to use foreach to generate the returned elements. (Well, you *can* do that to a buffer array and then return the array, but that kinda defeats the purpose of GC avoidance.) Some kind of built-in coroutine syntax with 'yield' would help things a LOT.


> For example, we could implement toStringz() as an algorithm that looks
> like:
> 
>     auto toStringz(S)(S s) {
>         return chain(s, repeat(0, 1))
>     }
> 
> and use it like this:
> 
>     string s = ...;
>     char[] buffer = ...;
>     s.toStringz.copy(buffer);
> 
> Note how the algorithm version of toStringz does not allocate any memory. buffer would be the output range, but note how what it actually is is, and how its memory is allocated, is selected by the user.

Yes, I like this. This is the right way to go.


[...]
> You might be tempted to think that these are just little leaks, who cares. But I recently wrote a D program that did tens of thousands of file operations, and those little leaks turned into a raging river.

Yeah, I'm currently working on a program that generates potentially huge numbers of n-dimensional coordinates, and currently the code does this using ranges that return array literals (ouch). This is pretty bad for performance and also for GC pressure, so I'm thinking to restructure the code some time in the near future to get rid of obligatory allocations, much like how you describe it above.


T

-- 
Customer support: the art of getting your clients to pay for your own incompetence.

On 3/6/2014 5:37 PM, H. S. Teoh wrote:
> Unfortunately, input ranges are somewhat tedious to write

I know. But we need to make the effort, at least for Phobos. The payoff is it makes user code much less effort.

On Friday, 7 March 2014 at 01:15:43 UTC, Walter Bright wrote:
> On 3/6/2014 4:43 PM, H. S. Teoh wrote:
>> What about using output ranges?
>
> A great question. I tend to regard output ranges as suitable for a container to expose. An algorithm reads an InputRange, and presents its output as another InputRange. This is so that algorithms can be easily chained together by the user, and the last algorithm in the chain would be std.algorithm.copy(OutputRange).

While I prefer this approach most of the time, I fear it has a performance cost over sink-style algorithms (whether they use an output range or build an array result). I guess the question is whether this cost is generally offset by gains in the memory allocation code or not.

> For example, we could implement toStringz() as an algorithm that looks like:
>
>     auto toStringz(S)(S s) {
>         return chain(s, repeat(0, 1))
>     }

std.range.only is more suitable than `repeat` here (and I don't know if `chain` would let you chain a range of characters with a range of integers):

auto toStringz(S)(S s)
    if (is(Unqual!(ElementType!S) == dchar)) {
    return s.chain('\0'.only());
}

Either way, perhaps the most serious problem is that when using `copy` to write the result to an array, both UTF decoding and re-encoding takes place (the result is always a range of `dchar`).

H. S. Teoh:

> Some kind of built-in coroutine syntax with
> 'yield' would help things a LOT.

Some persons have quickly shot down this idea that I have suggested:
https://d.puremagic.com/issues/show_bug.cgi?id=11880

Bye,
bearophile

On 3/6/2014 5:54 PM, Jakob Ovrum wrote:
> While I prefer this approach most of the time, I fear it has a performance cost
> over sink-style algorithms (whether they use an output range or build an array
> result). I guess the question is whether this cost is generally offset by gains
> in the memory allocation code or not.

std.buffer.scopebuffer was developed for that purpose, and as the discussion on why it is the way it is shows, it was developed with extensive use of a profiler to ensure there was no speed compromise from using it.


>> For example, we could implement toStringz() as an algorithm that looks like:
>>
>>     auto toStringz(S)(S s) {
>>         return chain(s, repeat(0, 1))
>>     }
>
> std.range.only is more suitable than `repeat` here

Yes, I missed that. I'm still learning about the proper way to use ranges.


> (and I don't know if `chain`
> would let you chain a range of characters with a range of integers):

My code fragment is untested and pretty much off the cuff. A real version would be a bit more complex, as you suggest.


> Either way, perhaps the most serious problem is that when using `copy` to write
> the result to an array, both UTF decoding and re-encoding takes place (the
> result is always a range of `dchar`).

I know. I struggled with that myself, and I object to the design decision that auto-decodes and auto-encodes any ranges that deal with char's. It automatically turns fast code into molasses. I wound up casting everything to ubytes, ugh.

But it's too late to change that now, sigh.

On 3/6/2014 8:37 PM, H. S. Teoh wrote:
>
> Unfortunately, input ranges are somewhat tedious to write -- nice
> foreach loops have to be broken up into .empty, .front, .popFront, which
> is a lot of boilerplate code and not so nice in inner loops (though I
> suppose the idea is to improve compiler inlining to handle these cases).
> I wonder if a mid- to long-term goal for D would be to ease writing
> input ranges by moving some of the boilerplate into the language, or
> providing range builder facilities in Phobos. The most nagging part of
> writing input ranges in the current language is the inability to use
> foreach to generate the returned elements. (Well, you *can* do that to a
> buffer array and then return the array, but that kinda defeats the
> purpose of GC avoidance.) Some kind of built-in coroutine syntax with
> 'yield' would help things a LOT.
>

Yes, this has been #1 on my wishlist for ranges for some time. We really need a way to make input ranges (maybe even forward ranges if we're clever enough about it) via "coroutines" that, like C#'s coroutines, are automatically converted behind-the-scenes into stackless fibers (ie, into state machines).

A while back, I tried doing a library solution for this via regular fibers, but there turned out to be a lot of overhead due to the fiber's context-switching [1].

We need to take inspiration from two things: C's "protothreads" library[2], and (as I said) C#'s coroutines. Both of those are fantastic IMO. In both cases, the body of a coroutine is automagically transformed into a big switch statement. Yield statements then become roughly "return tuple([yielded value], [resume point]); case [resume point]:...". And then invoking the coroutine again automatically passes in the last [resume point] returned so the big switch() can jump straight to where it left off. The main difference in our case would be that we'd also auto-generate all the boilerplate rigging for this to be an input range.

[1] http://semitwist.com/articles/article/view/combine-coroutines-and-input-ranges-for-dead-simple-d-iteration

[2] C's "protothreads" library: http://dunkels.com/adam/pt/expansion.html

These are good ideas, but for now we need to just bite the bullet and fix Phobos.

On 3/6/2014 10:59 PM, Walter Bright wrote:
> These are good ideas, but for now we need to just bite the bullet and
> fix Phobos.

Agreed.

07-Mar-2014 01:26, Walter Bright пишет:
> A major goal for D in the short term is to reduce reliance in Phobos on
> the GC. I was looking at std.string last night, and I noticed a couple
> things:
>
> 1. The inputs are constrained to being strings. This is overly
> restrictive, the inputs should be InputRanges.

Fun is most of std.algorithm is special-cased on strings. So we have double volume of crap.


-- 
Dmitry Olshansky