Walter Bright:
> There's no reason to suspect. Just obj2asm the output and see.
> Furthermore, better results will come from:
> int b() {
> k -= 1;
> return a(k, b(), x1, x2, x3, x4);
> };
> instead of using the delegate.
I don't fully understand what's happening, maybe I am doing something wrong, so
I just report what I have seen.
--------------------
With DMD 1.036 this code works up to N=25, usign almost 1.6 GB of RAM (and I
think a running time of just 6.4 seconds is very little, try to do this with
any dynamic language, so I was impressed by D1):
// code #1
import std.c.stdio: printf;
int a(int k, lazy int x1, lazy int x2, lazy int x3, lazy int x4, lazy int x5) {
int delegate() b;
b = {
k -= 1;
return a(k, b(), x1, x2, x3, x4);
};
return k <= 0 ? x4 + x5 : b();
}
void main() {
printf("%d\n", a(24, 1, -1, -1, 1, 0));
}
--------------------
While on DMD 1.036 the following code:
// code #2
import std.c.stdio: printf;
int a(int k, lazy int x1, lazy int x2, lazy int x3, lazy int x4, lazy int x5) {
int b() {
k -= 1;
return a(k, b(), x1, x2, x3, x4);
}
return k <= 0 ? x4 + x5 : b();
}
void main() {
printf("%d\n", a(24, 1, -1, -1, 1, 0));
}
Outputs at compile time:
man_or_boy2.d(6): delegate man_or_boy2.a.b.__dgliteral1 is a nested function
and cannot be accessed from a
man_or_boy2.d(6): delegate man_or_boy2.a.b.__dgliteral2 is a nested function
and cannot be accessed from a
man_or_boy2.d(6): delegate man_or_boy2.a.b.__dgliteral3 is a nested function
and cannot be accessed from a
man_or_boy2.d(6): delegate man_or_boy2.a.b.__dgliteral4 is a nested function
and cannot be accessed from a
man_or_boy2.d(6): delegate man_or_boy2.a.b.__dgliteral5 is a nested function
and cannot be accessed from a
But this code works on the codepad site, that uses DMD v.1.026 (I think with
Tangobos), up to N=21 (then the site goes into timeout for safety):
http://codepad.org/8GtKswm8
------------------------------
DMD v2.021 outputs the same errors with code #2.
------------------------------
DMD is able to run code #1 and the following #3:
// code #3
import std.c.stdio: printf;
int a(scope int k, lazy int x1, lazy int x2, lazy int x3, lazy int x4, lazy int
x5) {
scope int delegate() b;
b = {
k -= 1;
return a(k, b(), x1, x2, x3, x4);
};
return k <= 0 ? x4 + x5 : b();
}
void main() {
printf("%d\n", a(22, 1, -1, -1, 1, 0));
}
All the following compilations are done with and N=20 and:
dmd -O -release -inline -L/STACK:1700000000 man_or_boy.d
dmd -O -release -inline -L/STACK:1700000000 man_or_boy2.d
Note: in D2 the code #1 and code #3 seem to use the same amount of RAM and time
to run, 2.46 s and about 94MB RAM (N=20).
The same code #1 in DMD 1.036 runs in about 0.16 s and I am not able to know
how much RAM it uses (N=20).
------------------------------
ASM of code #1 compiled with DMD 1.036:
_D10man_or_boy1aFiLiLiLiLiLiZi comdat
assume CS:_D10man_or_boy1aFiLiLiLiLiLiZi
sub ESP,0Ch
push EBX
mov dword ptr 8[ESP],0
mov dword ptr 0Ch[ESP],0
lea EAX,0Ch[ESP]
mov ECX,offset
FLAT:_D10man_or_boy1aFiLiLiLiLiLiZi12__dgliteral1MFZi
mov 8[ESP],EAX
mov 0Ch[ESP],ECX
cmp dword ptr 03Ch[ESP],0
jg L56
mov EAX,01Ch[ESP]
mov EDX,020h[ESP]
mov EBX,01Ch[ESP]
call EDX
push EAX
sub ESP,4
mov EAX,01Ch[ESP]
mov EDX,020h[ESP]
mov EBX,01Ch[ESP]
call EDX
mov ECX,EAX
add ESP,4
pop EAX
add EAX,ECX
jmp short L62
L56: mov EAX,8[ESP]
mov EDX,ECX
mov EBX,8[ESP]
call EDX
L62: pop EBX
add ESP,0Ch
ret 02Ch
------------------------------
ASM of code #1 compiled with DMD 2.021:
assume CS:_D10man_or_boy1aFiLiLiLiLiLiZi
L0: sub ESP,0Ch
push EBX
push ESI
push EDI
push 030h
call near ptr __d_allocmemory
mov ESI,EAX
mov dword ptr [ESI],0
mov EAX,048h[ESP]
mov 4[ESI],EAX
mov EDX,044h[ESP]
mov EAX,040h[ESP]
mov 010h[ESI],EAX
mov 014h[ESI],EDX
mov EDX,03Ch[ESP]
mov EAX,038h[ESP]
mov 018h[ESI],EAX
mov 01Ch[ESI],EDX
mov EDX,034h[ESP]
mov EAX,030h[ESP]
mov 020h[ESI],EAX
mov 024h[ESI],EDX
mov EDX,02Ch[ESP]
mov EAX,028h[ESP]
mov 028h[ESI],EAX
mov 02Ch[ESI],EDX
mov dword ptr 8[ESI],0
mov dword ptr 0Ch[ESI],0
mov EBX,ESI
mov ECX,offset
FLAT:_D10man_or_boy1aFiLiLiLiLiLiZi12__dgliteral1MFZi
mov 8[ESI],EBX
mov 0Ch[ESI],ECX
add ESP,4
cmp dword ptr 4[ESI],0
jg L9F
mov EAX,028h[ESI]
mov EDX,02Ch[ESI]
mov EDI,028h[ESI]
call EDX
push EAX
sub ESP,4
mov EAX,024h[ESP]
mov EDX,028h[ESP]
mov EDI,024h[ESP]
call EDX
mov ECX,EAX
add ESP,4
pop EAX
add EAX,ECX
jmp short LA4
L9F: mov EAX,8[ESI]
call ECX
LA4: pop EDI
pop ESI
pop EBX
add ESP,0Ch
ret 02Ch
_D10man_or_boy1aFiLiLiLiLiLiZi ends
------------------------------
ASM of code #3 compiled with DMD 2.021:
_D11man_or_boy31aFMiLiLiLiLiLiZi comdat
assume CS:_D11man_or_boy31aFMiLiLiLiLiLiZi
L0: sub ESP,0Ch
push EBX
push ESI
push EDI
push 030h
call near ptr __d_allocmemory
mov ESI,EAX
mov dword ptr [ESI],0
mov EAX,048h[ESP]
mov 4[ESI],EAX
mov EDX,044h[ESP]
mov EAX,040h[ESP]
mov 010h[ESI],EAX
mov 014h[ESI],EDX
mov EDX,03Ch[ESP]
mov EAX,038h[ESP]
mov 018h[ESI],EAX
mov 01Ch[ESI],EDX
mov EDX,034h[ESP]
mov EAX,030h[ESP]
mov 020h[ESI],EAX
mov 024h[ESI],EDX
mov EDX,02Ch[ESP]
mov EAX,028h[ESP]
mov 028h[ESI],EAX
mov 02Ch[ESI],EDX
mov dword ptr 8[ESI],0
mov dword ptr 0Ch[ESI],0
mov EBX,ESI
mov ECX,offset
FLAT:_D11man_or_boy31aFMiLiLiLiLiLiZi12__dgliteral1MFZi
mov 8[ESI],EBX
mov 0Ch[ESI],ECX
add ESP,4
cmp dword ptr 4[ESI],0
jg L9F
mov EAX,028h[ESI]
mov EDX,02Ch[ESI]
mov EDI,028h[ESI]
call EDX
push EAX
sub ESP,4
mov EAX,024h[ESP]
mov EDX,028h[ESP]
mov EDI,024h[ESP]
call EDX
mov ECX,EAX
add ESP,4
pop EAX
add EAX,ECX
jmp short LA4
L9F: mov EAX,8[ESI]
call ECX
LA4: pop EDI
pop ESI
pop EBX
add ESP,0Ch
ret 02Ch
_D11man_or_boy31aFMiLiLiLiLiLiZi ends
------------------------------
Bye,
bearophile
