On 10/17/2012 12:11 AM, Jonathan M Davis wrote:
> On Wednesday, October 17, 2012 00:04:49 Timon Gehr wrote:
>> On 10/16/2012 09:47 PM, jerro wrote:
>>>> Hmm. There *is* a delegate being passed to map(). Would that cause
>>>> problems? Theoretically it shouldn't, but as you said, if dmd isn't
>>>> handling it correctly that could cause problems.
>>>
>>> I'm looking at the disassembly of cprod (http://pastebin.com/ngTax6B8)
>>> and there doesn't seem to be a call to _d_allocmemory in it. AFAIK it
>>> should be if the memory for the variables that the delegate uses was
>>> allocated on the heap?
>>
>> It should certainly allocate a closure. However, we don't want hidden
>> allocations in Phobos, so an alternate implementation strategy that
>> captures the input by value would be preferable anyway.
>> The bug should be reported in each case.
>
> The allocation of closures is pretty much inevitable when we have delegates
> and/or non-static Voldemort types.
>
> - Jonathan M Davis
>

Unless there are compiler bugs of course. Anyway, that is why I was
suggesting to use an alternate implementation strategy.

The following code is free of allocations if the compiler implementation is correct:

auto cprod(R1,R2)(R1 A, R2 B) {
    return zip(sequence!"n"(cast(size_t)0), A.save, B.save, repeat(A), repeat(B))
        .map!(function(a) => chain(
              zip(repeat(a[1]), take(a[4].save,a[0])),
              zip(take(a[3].save,a[0]+1), repeat(a[2]))
        )).joiner;
}

It also works around the issue. (note that I got rid of some UFCS
calls. The reason is that we don't know whether R1 and/or R2 actually have a member named 'take' or 'repeat' that would hijack the function we
want to call.)


(But you also need to (potentially) escape them in order to trigger the
allocation, so delegates and non-static structs are even useful when
allocating is not an option.)

On Wed, Oct 17, 2012 at 01:09:09AM +0200, Timon Gehr wrote: [...]
> The following code is free of allocations if the compiler implementation is correct:
> 
> auto cprod(R1,R2)(R1 A, R2 B) {
>     return zip(sequence!"n"(cast(size_t)0), A.save, B.save,
> repeat(A), repeat(B))
>         .map!(function(a) => chain(
>               zip(repeat(a[1]), take(a[4].save,a[0])),
>               zip(take(a[3].save,a[0]+1), repeat(a[2]))
>         )).joiner;
> }
> 
> It also works around the issue. (note that I got rid of some UFCS calls. The reason is that we don't know whether R1 and/or R2 actually have a member named 'take' or 'repeat' that would hijack the function we want to call.)
[...]

Hmph. I seem to be running into one compiler bug after another. Using the above code, which solves the initial problem, I get into another problem:

	void main() {
		auto A = sequence!"2*n"(0);
		auto B = sequence!"2*n+1"(0);
		auto AB = cprod(A,B);

		auto C = sequence!"100+n"(0);
		auto D = sequence!"200+n"(0);
		auto CD = cprod(C,D);
	}

DMD gives this bizarre error:

Error: function test3.cprod!(Sequence!("2*n",Tuple!(int)),Sequence!("2*n+1",Tuple!(int))).cprod.map!(__funcliteral2).map!(Zip!(Sequence!("n",Tuple!(uint)),Sequence!("100+n",Tuple!(int)),Sequence!("200+n",Tuple!(int)),Repeat!(Sequence!("100+n",Tuple!(int))),Repeat!(Sequence!("200+n",Tuple!(int))))).map is a nested function and cannot be accessed from test3.cprod!(Sequence!("100+n",Tuple!(int)),Sequence!("200+n",Tuple!(int))).cprod

Commenting out either the first three lines (A, B, AB) or the second
three lines (C, D, CD) makes the problem go away.

Looking more carefully at the error message, it appears that dmd is for some strange reason trying to reuse the first instance of cprod when compiling cprod(C,D). This is totally wrong, since they should be completely separate instantiations. Why this is so, I've no idea. :-(


T

-- 
LINUX = Lousy Interface for Nefarious Unix Xenophobes.

On 10/17/2012 02:09 AM, H. S. Teoh wrote:
> On Wed, Oct 17, 2012 at 01:09:09AM +0200, Timon Gehr wrote:
> [...]
>> The following code is free of allocations if the compiler
>> implementation is correct:
>>
>> auto cprod(R1,R2)(R1 A, R2 B) {
>>      return zip(sequence!"n"(cast(size_t)0), A.save, B.save,
>> repeat(A), repeat(B))
>>          .map!(function(a) => chain(
>>                zip(repeat(a[1]), take(a[4].save,a[0])),
>>                zip(take(a[3].save,a[0]+1), repeat(a[2]))
>>          )).joiner;
>> }
>>
>> It also works around the issue. (note that I got rid of some UFCS
>> calls. The reason is that we don't know whether R1 and/or R2 actually
>> have a member named 'take' or 'repeat' that would hijack the function
>> we want to call.)
> [...]
>
> Hmph. I seem to be running into one compiler bug after another. Using
> the above code, which solves the initial problem, I get into another
> problem:
>
> 	void main() {
> 		auto A = sequence!"2*n"(0);
> 		auto B = sequence!"2*n+1"(0);
> 		auto AB = cprod(A,B);
>
> 		auto C = sequence!"100+n"(0);
> 		auto D = sequence!"200+n"(0);
> 		auto CD = cprod(C,D);
> 	}
>
> DMD gives this bizarre error:
>
> Error: function test3.cprod!(Sequence!("2*n",Tuple!(int)),Sequence!("2*n+1",Tuple!(int))).cprod.map!(__funcliteral2).map!(Zip!(Sequence!("n",Tuple!(uint)),Sequence!("100+n",Tuple!(int)),Sequence!("200+n",Tuple!(int)),Repeat!(Sequence!("100+n",Tuple!(int))),Repeat!(Sequence!("200+n",Tuple!(int))))).map is a nested function and cannot be accessed from test3.cprod!(Sequence!("100+n",Tuple!(int)),Sequence!("200+n",Tuple!(int))).cprod
>
> Commenting out either the first three lines (A, B, AB) or the second
> three lines (C, D, CD) makes the problem go away.
>
> Looking more carefully at the error message, it appears that dmd is for
> some strange reason trying to reuse the first instance of cprod when
> compiling cprod(C,D). This is totally wrong, since they should be
> completely separate instantiations. Why this is so, I've no idea. :-(
>
>
> T
>

Looks like http://d.puremagic.com/issues/show_bug.cgi?id=8542
But your test case is somewhat simpler, so it might be useful to add it there.

On Tue, Oct 16, 2012 at 09:47:36PM +0200, jerro wrote:
> >Hmm. There *is* a delegate being passed to map(). Would that cause
> >problems? Theoretically it shouldn't, but as you said, if dmd
> >isn't
> >handling it correctly that could cause problems.
> 
> I'm looking at the disassembly of cprod (http://pastebin.com/ngTax6B8) and there doesn't seem to be a call to _d_allocmemory in it. AFAIK it should be if the memory for the variables that the delegate uses was allocated on the heap?

Filed bug:

	http://d.puremagic.com/issues/show_bug.cgi?id=8832

Whew, what a day! Two compiler bugs, no less, and a whole bunch of Phobos issues. I think I may need to take a break from D for a day or two. :-/


T

-- 
People walk. Computers run.

On Tue, Oct 16, 2012 at 2:54 PM, H. S. Teoh <hsteoh@quickfur.ath.cx> wrote:

> On Tue, Oct 16, 2012 at 12:33:20PM -0700, H. S. Teoh wrote: [...]
> > Another data point: if I move the .joiner call out of cprod() into
> > main(), then there is no problem. Could it be that something in joiner
> > is breaking somehow, when returned from a function?
> [...]
>
> I found a reduced case:
>
>         import std.algorithm;
>         import std.range;
>         import std.stdio;
>
>         auto boo() {
>                 auto C = [2];
>                 return
>                         [1,1]
>                         .map!((a) => C)
>                         .joiner
>                 ;
>         }
>
>         void main() {
>                 auto C = [2];
>                 writeln(
>                         [1,1]
>                         .map!((a) => C)
>                         .joiner
>                 .take(12));
>
>                 writeln("====");
>
>                 writeln(boo().take(12));
>         }
>
> Excuse the odd formatting, I wanted to make sure the [1,1,1].map!(...)
> parts are line-for-line identical between boo() and main().
>
> This example segfaults in the last writeln. Commenting out .joiner makes the segfault go away. Reducing [1,1] to a 1-element array makes the problem go away. Replacing C with [1] makes the problem go away. Removing map!(...) and replacing it with something involving C makes the problem go away. Deleting the .take(12) outputs a whole mass of garbage values and then segfaults.
>
> So it seems like there is some kind of bad interaction between map and joiner. Maybe as jethro said, it's wrong code produced by dmd for the delegate passed to map? It seems to be dependent on the reference to the local variable C, which seems to imply a corrupted (or just out-of-scope?) delegate context.
>
>
> T
>
> --
> The best way to destroy a cause is to defend it poorly.


I'm starting to think maybe I shouldn't have closed my issue I reported awhile back:

http://d.puremagic.com/issues/show_bug.cgi?id=7978

I really need to read how closures are supposed to work.

BA

On Tue, Oct 16, 2012 at 09:05:50PM -0600, Brad Anderson wrote:
> On Tue, Oct 16, 2012 at 2:54 PM, H. S. Teoh <hsteoh@quickfur.ath.cx> wrote:
[...]
> > So it seems like there is some kind of bad interaction between map and joiner. Maybe as jethro said, it's wrong code produced by dmd for the delegate passed to map? It seems to be dependent on the reference to the local variable C, which seems to imply a corrupted (or just out-of-scope?) delegate context.
[...]
> I'm starting to think maybe I shouldn't have closed my issue I reported awhile back:
> 
> http://d.puremagic.com/issues/show_bug.cgi?id=7978
> 
> I really need to read how closures are supposed to work.
[...]

Well, closures are *supposed* to give you access to the context of a function that has gone out of scope -- usually implemented by allocating the local variables referenced by the closure on the heap instead of the stack. D is supposed to do this (TDPL, §5.8.1, p. 154). If dmd fails to implement this, it's a bug.


T

-- 
It won't be covered in the book. The source code has to be useful for something, after all. -- Larry Wall

On 10/16/12 4:28 PM, jerro wrote:
> On Tuesday, 16 October 2012 at 19:31:18 UTC, H. S. Teoh wrote:
>> On Tue, Oct 16, 2012 at 08:44:56PM +0200, monarch_dodra wrote:
>> [...]
>>> No idea either, but I'll volunteer to investigate ;)
>>>
>>> I agree with Jonathan though, sounds like a bug somewhere. There
>>> is no reason for your code to fail.
>>>
>>> I'll post back if I find anything.
>>
>> Another data point: if I move the .joiner call out of cprod() into
>> main(), then there is no problem. Could it be that something in joiner
>> is breaking somehow, when returned from a function?
>>
>>
>> T
>
> I don't know, but if I change the code to this:
>
> auto cprod(R1,R2)(R1 A, R2 B) {
> // This part is exactly the same as in main(), below. So
> // in theory, it should work exactly the same way.
> auto mapper = (typeof(tuple(cast(size_t) 0, A.front, B.front)) a) => chain(
> zip(repeat(a[1]), B.save.take(a[0])),
> zip(A.save.take(a[0]+1), repeat(a[2])));
>
> auto r = zip(sequence!"n"(cast(size_t)0), A.save, B.save)
> .map!mapper()
> .joiner;
>
> // But something goes wrong here: is it because the
> // above composed ranges are stack-allocated temporaries
> // that go out of scope upon return?
> return r;
> }
>
> It works too.

My guess: there's a bug in handling the stack frame with the lambdas involved.

Andrei

Am Tue, 16 Oct 2012 17:28:47 -0700
schrieb "H. S. Teoh" <hsteoh@quickfur.ath.cx>:

> On Tue, Oct 16, 2012 at 09:47:36PM +0200, jerro wrote:
> > >Hmm. There *is* a delegate being passed to map(). Would that cause
> > >problems? Theoretically it shouldn't, but as you said, if dmd
> > >isn't
> > >handling it correctly that could cause problems.
> > 
> > I'm looking at the disassembly of cprod (http://pastebin.com/ngTax6B8) and there doesn't seem to be a call to _d_allocmemory in it. AFAIK it should be if the memory for the variables that the delegate uses was allocated on the heap?
> 
> Filed bug:
> 
> 	http://d.puremagic.com/issues/show_bug.cgi?id=8832
> 
> Whew, what a day! Two compiler bugs, no less, and a whole bunch of Phobos issues. I think I may need to take a break from D for a day or two. :-/
> 
> 
> T
> 

And that's where all the good projects end... :D

-- 
Marco

On Fri, Oct 19, 2012 at 04:24:53AM +0200, Marco Leise wrote:
> Am Tue, 16 Oct 2012 17:28:47 -0700
> schrieb "H. S. Teoh" <hsteoh@quickfur.ath.cx>:
> 
> > On Tue, Oct 16, 2012 at 09:47:36PM +0200, jerro wrote:
> > > >Hmm. There *is* a delegate being passed to map(). Would that cause problems? Theoretically it shouldn't, but as you said, if dmd isn't handling it correctly that could cause problems.
> > > 
> > > I'm looking at the disassembly of cprod (http://pastebin.com/ngTax6B8) and there doesn't seem to be a call to _d_allocmemory in it. AFAIK it should be if the memory for the variables that the delegate uses was allocated on the heap?
> > 
> > Filed bug:
> > 
> > 	http://d.puremagic.com/issues/show_bug.cgi?id=8832
> > 
> > Whew, what a day! Two compiler bugs, no less, and a whole bunch of Phobos issues. I think I may need to take a break from D for a day or two. :-/
[...]
> And that's where all the good projects end... :D
[...]

Actually, I just went back to working on my personal D project for a bit. I was a bit disappointed that what I thought would be a quick side-job (implement cartesianProduct in std.algorithm) turned out to get stymied by compiler bugs and Phobos issues.

I have to say, though, that in spite of all these problems with the current implementation of D, it is still pretty dang powerful, and I would still never go back to C++ again (for my personal projects, anyway). I have managed to implement in ~2 weeks the vector computation part of my geometric computation project (that took a whole lot longer to write in C++ many years ago), and with much cleaner code too. The D implementation has already far exceeded the original implementation, both in terms of functionality, and in terms of code cleanliness.

It's just all the little things that D did right: delegates that simplified the list-processing operator implementation greatly; templates that allowed me to use the same code to both parse and build an expression tree or evaluate it on-the-fly (just by passing an appropriately-crafted subclass to the template); ranges that allow generic code instead of writing 20 variants of what is essentially the same code, one for each incompatible container type, etc.. Functional-style code like non-trivial combinations of map and reduce, which are great for simplifying complex code to just a couple o' lines -- which are very painful to write in C++ and even harder to debug.

So yes, D still has a ways to go, and it does have its warts, but it's heaven compared to C++.


T

-- 
Let's not fight disease by killing the patient. -- Sean 'Shaleh' Perry

On 10/19/12 8:17 AM, H. S. Teoh wrote:
> On Fri, Oct 19, 2012 at 04:24:53AM +0200, Marco Leise wrote:
>> Am Tue, 16 Oct 2012 17:28:47 -0700
>> schrieb "H. S. Teoh"<hsteoh@quickfur.ath.cx>:
>>
>>> On Tue, Oct 16, 2012 at 09:47:36PM +0200, jerro wrote:
>>>>> Hmm. There *is* a delegate being passed to map(). Would that
>>>>> cause problems? Theoretically it shouldn't, but as you said, if
>>>>> dmd isn't handling it correctly that could cause problems.
>>>>
>>>> I'm looking at the disassembly of cprod
>>>> (http://pastebin.com/ngTax6B8) and there doesn't seem to be a call
>>>> to _d_allocmemory in it. AFAIK it should be if the memory for the
>>>> variables that the delegate uses was allocated on the heap?
>>>
>>> Filed bug:
>>>
>>> 	http://d.puremagic.com/issues/show_bug.cgi?id=8832
>>>
>>> Whew, what a day! Two compiler bugs, no less, and a whole bunch of
>>> Phobos issues. I think I may need to take a break from D for a day
>>> or two. :-/
> [...]
>> And that's where all the good projects end... :D
> [...]
>
> Actually, I just went back to working on my personal D project for a
> bit. I was a bit disappointed that what I thought would be a quick
> side-job (implement cartesianProduct in std.algorithm) turned out to get
> stymied by compiler bugs and Phobos issues.

Admittedly cartesianProduct is a nontrivial juxtaposition of quite a few other artifacts. The question here is whether this is just endless churn or real progress. I'm optimistic, but am curious about others' opinion.

[snip]
> So yes, D still has a ways to go, and it does have its warts, but it's
> heaven compared to C++.

One question is how it compares against other languages that foster similar bulk processing, such as C# or Scala.


Andrei