Scope storage class

bearophile bearophileHUGS at lycos.com
Wed Nov 26 14:02:54 PST 2008


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


More information about the Digitalmars-d-announce mailing list