On Thursday, 17 July 2014 at 22:27:52 UTC, Dicebot wrote:
> On Thursday, 17 July 2014 at 22:21:54 UTC, Brad Anderson wrote:
>> Well the idea is that you then copy into an output range with whatever allocation strategy you want at the end. There is quite a bit of overlap I think. Not complete overlap and OutputRange accepting functions will still be needed but I think we should prefer the lazy approach where possible.
>
> It is not always possible - sometimes resulting range element must be already "cooked" object. I do agree it is a powerful default when feasible though. At the same time simple output range overloads is much faster to add.

From what I'm getting is that we might have the chance here to redefine memory usage, as was pointed out by Teoh et al. Reduce allocations as much as possible, avoiding a problem in the first place is better than solving it. It's worth thinking in this direction, cos the GC / RC issue will always boil down to the fact that there is a price to be paid.

On Thu, Jul 17, 2014 at 10:27:51PM +0000, Dicebot via Digitalmars-d wrote:
> On Thursday, 17 July 2014 at 22:21:54 UTC, Brad Anderson wrote:
> >Well the idea is that you then copy into an output range with whatever allocation strategy you want at the end. There is quite a bit of overlap I think. Not complete overlap and OutputRange accepting functions will still be needed but I think we should prefer the lazy approach where possible.
> 
> It is not always possible - sometimes resulting range element must be already "cooked" object.

Example?


> I do agree it is a powerful default when feasible though. At the same time simple output range overloads is much faster to add.

As Brad said, it's far easier to go from lazy to eager than the other way round, e.g., by sticking .array at the end, or .copy(buf) where buf is allocated according to whatever scheme the user chooses. Since buf is declared by the user, the user is free to use whatever allocation mechanism he wishes, the string algorithm doesn't know nor care what it is (and it shouldn't need to).


T

-- 
What do you mean the Internet isn't filled with subliminal messages? What about all those buttons marked "submit"??

On Thu, Jul 17, 2014 at 06:32:58PM +0000, Dicebot via Digitalmars-d wrote:
> On Thursday, 17 July 2014 at 18:22:11 UTC, H. S. Teoh via Digitalmars-d wrote:
> >Actually, I've realized that output ranges are really only useful when you want to store the final result. For data in mid-processing, you really want to be exporting an input (or higher) range interface instead, because functions that take output ranges are not composable.  And for storing final results, you just use std.algorithm.copy, so there's really no need for many functions to take an output range at all.
> 
> Plain algorithm ranges rarely need to allocate at all so those are somewhat irrelevant to the topic. What I am speaking about are variety of utility functions like this:
> 
> S detab(S)(S s, size_t tabSize = 8)
>     if (isSomeString!S)
> 
> this allocates result string. Proper alternative:
> 
> S detab(S)(ref S output, size_t tabSize = 8)
>     if (isSomeString!S);
> 
> plus
> 
> void detab(S, OR)(OR output, size_t tab_Size = 8)
>     if (   isSomeString!S
>         && isSomeString!(ElementType!OR)
>        )

I think you're missing the input parameter. :)

	void detab(S, OR)(S s, OR output, size_t tabSize = 8) { ... }

I argue that you can just turn it into this:

	auto withoutTabs(S)(S s, size_t tabSize = 8)
	{
		static struct Result {
			... // implementation here
		}
		static assert(isInputRange!Result);
		return Result(s, tabSize);
	}

	auto myInput = "...";
	auto detabbedInput = myInput.withoutTabs.array;

	// Or:
	MyOutputRange sink;	// allocate using whatever scheme you want
	myInput.withoutTabs.copy(sink);

The algorithm itself doesn't need to know where the result will end up -- sink could be stdout, in which case no allocation is needed at all.


Or are you talking about in-place modification of the input string? That's a different kettle o' fish.


T

-- 
EMACS = Extremely Massive And Cumbersome System

On 7/17/2014 3:16 PM, Dicebot wrote:
> On Thursday, 17 July 2014 at 22:06:01 UTC, Brad Anderson wrote:
>> I agreed with this for awhile but following the conversation here
>> <https://github.com/D-Programming-Language/phobos/pull/2149> I'm more inclined
>> to think we should be adding lazy versions of functions where possible rather
>> than versions with OutputRange parameters. It's more flexible that way and can
>> result in even fewer allocations than even OutputRange parameters would have
>> (i.e. you can have chains of lazy operations and only allocate on the final
>> step, or not at all in some cases).
>>
>> Laziness isn't appropriate or possible everywhere but it's much easier to go
>> from lazy to eager than the other way around.
>>
>>> [...]
>
> This is not comparable. Lazy input range based solutions do not make it possible
> to change allocation strategy, they simply defer the allocation point. Ideally
> both are needed.

They move the allocation point to the top level, rather than the bottom or intermediate level.

On 7/17/2014 4:01 PM, H. S. Teoh via Digitalmars-d wrote:
> As Brad said, it's far easier to go from lazy to eager than the other
> way round, e.g., by sticking .array at the end, or .copy(buf) where buf
> is allocated according to whatever scheme the user chooses. Since buf is
> declared by the user, the user is free to use whatever allocation
> mechanism he wishes, the string algorithm doesn't know nor care what it
> is (and it shouldn't need to).

Yup. It enables separating the allocation strategy from the algorithm.

On 7/17/2014 11:32 AM, Dicebot wrote:
> Plain algorithm ranges rarely need to allocate at all so those are somewhat
> irrelevant to the topic. What I am speaking about are variety of utility
> functions like this:
>
> S detab(S)(S s, size_t tabSize = 8)
>      if (isSomeString!S)
>
> this allocates result string. Proper alternative:
>
> S detab(S)(ref S output, size_t tabSize = 8)
>      if (isSomeString!S);
>
> plus
>
> void detab(S, OR)(OR output, size_t tab_Size = 8)
>      if (   isSomeString!S
>          && isSomeString!(ElementType!OR)
>         )

That algorithm takes a string and writes to an output range. This is not very composable. For example, what if one has an input range of chars, rather than a string? And what if one wants to tack more processing on the end?

A better interface is the one used by the byChar, byWchar, and byDchar ranges recently added to std.utf. Those accept an input range, and present an input range as "output". They are very composable, and can be stuck in anywhere in a character processing pipeline. They do no allocations, and are completely lazy.

The byChar algorithm in particular can serve as an outline for how to do a detab algorithm, most of the code can be reused for that.

On Thu, Jul 17, 2014 at 10:33:26PM -0700, Walter Bright via Digitalmars-d wrote:
> On 7/17/2014 3:16 PM, Dicebot wrote:
> >On Thursday, 17 July 2014 at 22:06:01 UTC, Brad Anderson wrote:
> >>I agreed with this for awhile but following the conversation here <https://github.com/D-Programming-Language/phobos/pull/2149> I'm more inclined to think we should be adding lazy versions of functions where possible rather than versions with OutputRange parameters. It's more flexible that way and can result in even fewer allocations than even OutputRange parameters would have (i.e. you can have chains of lazy operations and only allocate on the final step, or not at all in some cases).
> >>
> >>Laziness isn't appropriate or possible everywhere but it's much easier to go from lazy to eager than the other way around.
> >>
> >>>[...]
> >
> >This is not comparable. Lazy input range based solutions do not make it possible to change allocation strategy, they simply defer the allocation point. Ideally both are needed.
> 
> They move the allocation point to the top level, rather than the bottom or intermediate level.

Deferring the allocation point to the top level has the advantage of letting high-level user code decide what the allocation strategy should be, rather than percolating that decision down the call graph to every low-level function.

Of course, it's not always possible to defer this, such as if you need to tell a container which allocator to use. But IMO this should be pushed up to higher-level code whenever possible.


T

-- 
Why can't you just be a nonconformist like everyone else? -- YHL

On 7/17/2014 11:17 AM, H. S. Teoh via Digitalmars-d wrote:
> I don't think it will affect existing code (esp. given Walter's stance
> on breaking changes!). Probably the old GC-based string functions will
> still be around for backwards-compatibility. Perhaps some of them might
> be replaced with non-GC versions where it can be done transparently, but
> I'd expect you'd need to rewrite your string code to take advantage of
> the new range-based stuff. Hopefully the rewrites will be minimal (e.g.,
> pass in an output range as argument instead of getting a returned
> string, replace allocation-based code with a UFCS chain, etc.). The
> ideal scenario may very well be as simple as tacking on
> `.copy(myBuffer)` at the end of a UFCS chain. :-P

Boss, dat's pretty much de plan, de plan!

On 7/17/2014 10:47 PM, H. S. Teoh via Digitalmars-d wrote:
> Deferring the allocation point to the top level has the advantage of
> letting high-level user code decide what the allocation strategy should
> be, rather than percolating that decision down the call graph to every
> low-level function.

Exactly.

> Of course, it's not always possible to defer this, such as if you need
> to tell a container which allocator to use. But IMO this should be
> pushed up to higher-level code whenever possible.

Andrei's allocator scheme addresses this. It will also allow such decisions to be made at the high level.

On Thursday, 17 July 2014 at 09:57:09 UTC, currysoup wrote:
> Just from watching a few of the DConf 2014 talks, if you want performance you avoid the GC at all costs (even if that means allocating into huge predefined buffers). Once you're going to these lengths to avoid garbage collection it begs the question, why are you even using this language?

In D you have a choice to use GC or not use it. You would want to not use if you have a severe performance problem, which may or may not exist.
There's no guarantee another language is a silver bullet and will magically solve all problems.