www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - More pure optimizations

reply bearophile <bearophileHUGS lycos.com> writes:
This bost is born from the following comment:

http://www.reddit.com/r/programming/comments/8piiy/upcoming_luajit_2xs_performance_comparable_to_c/c0a12gb

If I compile code like the following with D2, with no inlining:

import std.c.stdio: printf;

pure int bar(int x) { return x * 2; }

int foo() {
    int x;
    for (int i; i < 100; i++)
        x += bar(10);
    return x;
}

void main() {
    printf("%d\n", foo());
}

bar() is pure, so the compiler can compute it only once before the loop.

But currently DMD compiles foo() as:

L0:		push	EAX
		push	EBX
		xor	EBX,EBX
		push	ESI
		xor	ESI,ESI
L7:		mov	EAX,0Ah
		call	near ptr _D5temp23barFNaiZi
		add	ESI,EAX
		inc	EBX
		cmp	EBX,064h
		jb	L7
		mov	EAX,ESI
		pop	ESI
		pop	EBX
		pop	ECX
		ret

Once that optimization is in place, the reading access to associative arrays
too can be marked as "pure" so the in the following code h["bar"] is seen as a
loop invariant, and computed only once before the loop:

import std.c.stdio: printf;

int foo(int[string] h) {
    int x;
    for (int i; i < 100; i++)
        x += h["bar"];
    return x;
}

void main() {
    printf("%d\n", foo(["bar": 42]));
}

It seems the LuaJIT2 is already able to do such things.

I'd like to have pure optimizations in LDC D1 too :-)

I guess it's not easy for the compiler to have some heuristics that allows it
to infer that a function like:
int bar(int x) { return x * 2; }
is pure even if it's not marked as pure.

-------------

Talking about compiler optimizations, here I have shown an usage example of the
new escape analysis the last Java is able to do, with good results:

http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.learn&article_id=16762

Bye,
bearophile
Jun 03 2009
next sibling parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
bearophile escribió:

 Once that optimization is in place, the reading access to associative arrays
too can be marked as "pure" so the in the following code h["bar"] is seen as a
loop invariant, and computed only once before the loop:
 
 import std.c.stdio: printf;
 
 int foo(int[string] h) {
     int x;
     for (int i; i < 100; i++)
         x += h["bar"];
     return x;
 }
 
 void main() {
     printf("%d\n", foo(["bar": 42]));
 }


What if a different thread modifies h in between the loop?
Jun 03 2009
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Ary Borenszweig:

 What if a different thread modifies h in between the loop?


Oh, that's why in Clojure (almost) all collections are functional :-)

Bye,
bearophile
Jun 03 2009
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Ary Borenszweig:

 What if a different thread modifies h in between the loop?


"h" associative array as a thread-local?

Bye,
bearophile
Jun 03 2009
parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
bearophile escribió:

 Ary Borenszweig:

 What if a different thread modifies h in between the loop?


 
 "h" associative array as a thread-local?


but from the method's signature:

int foo(int[string] h)

you can't tell that h is thread-local or not. Is that what you mean?
Jun 03 2009
parent Brad Roberts <braddr puremagic.com> writes:
Ary Borenszweig wrote:

 bearophile escribió:

 Ary Borenszweig:

 What if a different thread modifies h in between the loop?


 "h" associative array as a thread-local?


 
 but from the method's signature:
 
 int foo(int[string] h)
 
 you can't tell that h is thread-local or not. Is that what you mean?


In D2, with shared vs non-shared memory becoming explicit, non-shared const
parameters can become legal pure parameters.  Since non-const can implicitly
convert to const, as long as the assoc array is non-shared and the key is
non-shared, then ... all the pieces fall into place to allow assoc array's
opIndex to have a pure version.

Whee,
Brad
Jun 03 2009
prev sibling next sibling parent Brad Roberts <braddr puremagic.com> writes:
On Wed, 3 Jun 2009, bearophile wrote:


 If I compile code like the following with D2, with no inlining:
 
 import std.c.stdio: printf;
 
 pure int bar(int x) { return x * 2; }
 
 int foo() {
     int x;
     for (int i; i < 100; i++)
         x += bar(10);
     return x;
 }
 
 void main() {
     printf("%d\n", foo());
 }
 
 bar() is pure, so the compiler can compute it only once before the loop.
 
 But currently DMD compiles foo() as:
 
 L0:		push	EAX
 		push	EBX
 		xor	EBX,EBX
 		push	ESI
 		xor	ESI,ESI
 L7:		mov	EAX,0Ah
 		call	near ptr _D5temp23barFNaiZi
 		add	ESI,EAX
 		inc	EBX
 		cmp	EBX,064h
 		jb	L7
 		mov	EAX,ESI
 		pop	ESI
 		pop	EBX
 		pop	ECX
 		ret
 
 Once that optimization is in place, the reading access to associative arrays
too can be marked as "pure" so the in the following code h["bar"] is seen as a
loop invariant, and computed only once before the loop:


Hrm.. Walter, I thought D2's optimizer had already grown the ability to 
take advantage of pure.  Does it not do loop hoisting yet?

On a related note, I started this past weekend playing with automatic 
detection / proof of pureness in the d2 codebase.  It's a long way from 
complete, but could allow the optimizer to find pure by implementation 
rather than pure by definition cases to play with.  The same code can be 
used to validate the pure attribute and warn or error on violations.

Once I get it a semi-useful state, I'll toss a patch into a bug report so 
others can see it.  Right now it's too embrionic to share. :(

Later,
Brad
Jun 03 2009
prev sibling parent Brad Roberts <braddr puremagic.com> writes:
Brad Roberts wrote:

 On a related note, I started this past weekend playing with automatic 
 detection / proof of pureness in the d2 codebase.  It's a long way from 
 complete, but could allow the optimizer to find pure by implementation 
 rather than pure by definition cases to play with.  The same code can be 
 used to validate the pure attribute and warn or error on violations.
 
 Once I get it a semi-useful state, I'll toss a patch into a bug report so 
 others can see it.  Right now it's too embrionic to share. :(
 
 Later,
 Brad


As I feared.. within an hour of posting this I realized a fatal flaw in my
design.  I've some ideas for how to do what I want, but I need to think more.

Sigh,
Brad
Jun 03 2009