www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Optimizing Immutable and Purity

reply Walter Bright <newshound1 digitalmars.com> writes:
I've been working on improving the optimizer to take advantage of 
immutability and purity.

http://www.reddit.com/r/reddit.com/comments/7l5x4/optimizing_immutable_and_purity/

http://dobbscodetalk.com/index.php?option=com_myblog&;show=Optimizing-Immutable-and-Purity.html&amp;Itemid=29
Dec 22 2008
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Walter Bright:

 http://dobbscodetalk.com/index.php?option=com_myblog&;show=Optimizing-Immutable-and-Purity.html&amp;Itemid=29

Better link: http://dobbscodetalk.com/index.php?option=com_myblog&show=Optimizing-Immutable-and-Purity.html&Itemid=29 (Not read yet). Bye, bearophile
Dec 22 2008
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Tue, 23 Dec 2008 01:10:52 +0300, Walter Bright <newshound1 digitalmars.com>
wrote:

 I've been working on improving the optimizer to take advantage of  
 immutability and purity.

 http://www.reddit.com/r/reddit.com/comments/7l5x4/optimizing_immutable_and_purity/

 http://dobbscodetalk.com/index.php?option=com_myblog&;show=Optimizing-Immutable-and-Purity.html&amp;Itemid=29

Your link is wrong - '&' is replaced with '&amp;' and thus following the link gives the error below:
 You are not authorised to view this resource.
 You need to login.

Here is correct link: http://dobbscodetalk.com/index.php?option=com_myblog&show=Optimizing-Immutable-and-Purity.html&Itemid=29
Dec 22 2008
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Multiplication and pointer operations are both very common operation in C code,
so this code shows well why I don't like them to be represented by the same
symbol. Pascal uses ^ for poinetr operation (and ^ isn't used for the bitwise
operation):

int foo(int* a, int* b)
{   int i = *a * *b;
    int j = *a * *b;
    return i + j;
}


By the very definition of purity, you won't be able to to ever notice the
absent call unless you are willing to place a precise thermal probe on the
processor and notice a drop in the heat produced.<

This sounds a little silly :-]
one rule that is fairly consistent is that fewer instructions execute faster.<

Generally this isn't much true anymore.
On a real program, how much faster is my code going to get, if I maximize use
of pure functions and immutable data? I don't know. I don't have any experience
with it on a large program.<

Maybe some programmer already used to pure functional programming can give you some answer. Is GCC able to perform similar optimizations (some of them, not all of them) when you use the "pure" attribute to functions? See int square (int) __attribute__ ((pure)); in this page: http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html A very readable article, but I don't have much other comments to add on-topic. Bye, bearophile
Dec 22 2008
next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
bearophile wrote:
 one rule that is fairly consistent is that fewer instructions
 execute faster.<

Generally this isn't much true anymore.

It is <g>. Try it.
 On a real program, how much faster is my code going to get, if I
 maximize use of pure functions and immutable data? I don't know. I
 don't have any experience with it on a large program.<

Maybe some programmer already used to pure functional programming can give you some answer.

I doubt it. There isn't any other language with D's mix of imperative and functional such that you can do a reasonable comparative study.
 Is GCC able to perform similar optimizations (some of them, not all
 of them) when you use the "pure" attribute to functions? See  int
 square (int) __attribute__ ((pure));  in this page: 
 http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html

I didn't know gcc had pure functions. It doesn't have immutable data. If it does optimize with it, you can try it and see!
Dec 22 2008
parent reply bearophile <bearophileHUGS lycos.com> writes:
Walter Bright:
 I didn't know gcc had pure functions. It doesn't have immutable data. If 
 it does optimize with it, you can try it and see!

It seems to work: // test1 int bar(int); int foo(int i) { return bar(i) + bar(i); } Asm with no optimization and default CPU, GCC 4.2.1: .file "test1.c" .text .globl _foo .def _foo; .scl 2; .type 32; .endef _foo: pushl %ebp movl %esp, %ebp pushl %ebx subl $4, %esp movl 8(%ebp), %eax movl %eax, (%esp) call _bar movl %eax, %ebx movl 8(%ebp), %eax movl %eax, (%esp) call _bar leal (%ebx,%eax), %eax addl $4, %esp popl %ebx popl %ebp ret .def _bar; .scl 2; .type 32; .endef With -O2: .file "test1.c" .text .p2align 4,,15 .globl _foo .def _foo; .scl 2; .type 32; .endef _foo: pushl %ebp movl %esp, %ebp subl $24, %esp movl %ebx, -8(%ebp) movl 8(%ebp), %ebx movl %esi, -4(%ebp) movl %ebx, (%esp) call _bar movl %ebx, (%esp) movl %eax, %esi call _bar movl -8(%ebp), %ebx addl %esi, %eax movl -4(%ebp), %esi movl %ebp, %esp popl %ebp ret .def _bar; .scl 2; .type 32; .endef // test2 int bar(int) __attribute__ ((pure)); int foo(int i) { return bar(i) + bar(i); } Asm with no optimization: .file "test2.c" .text .globl _foo .def _foo; .scl 2; .type 32; .endef _foo: pushl %ebp movl %esp, %ebp pushl %ebx subl $4, %esp movl 8(%ebp), %eax movl %eax, (%esp) call _bar movl %eax, %ebx movl 8(%ebp), %eax movl %eax, (%esp) call _bar leal (%ebx,%eax), %eax addl $4, %esp popl %ebx popl %ebp ret .def _bar; .scl 2; .type 32; .endef With -O2: .file "test2.c" .text .p2align 4,,15 .globl _foo .def _foo; .scl 2; .type 32; .endef _foo: pushl %ebp movl %esp, %ebp subl $8, %esp movl 8(%ebp), %eax movl %eax, (%esp) call _bar leave addl %eax, %eax ret .def _bar; .scl 2; .type 32; .endef As you can see now there's just one call to bar. Bye, bearophile
Dec 22 2008
parent Walter Bright <newshound1 digitalmars.com> writes:
Bill Baxter wrote:
 On Tue, Dec 23, 2008 at 12:10 PM, bearophile <bearophileHUGS lycos.com> wrote:
 Walter Bright:
 I didn't know gcc had pure functions. It doesn't have immutable data. If
 it does optimize with it, you can try it and see!

[...] As you can see now there's just one call to bar. Bye, bearophile

Does GCC complain if you do something clearly impure inside bar?

I got: error: attributes are not allowed on a function-definition Oh well. It looks like a 25% implemented feature. It also only worked with g++. gcc wouldn't accept it at all. Without some sort of immutability, also, purity cannot be checked anyway.
Dec 22 2008
prev sibling next sibling parent "Bill Baxter" <wbaxter gmail.com> writes:
On Tue, Dec 23, 2008 at 12:10 PM, bearophile <bearophileHUGS lycos.com> wrote:
 Walter Bright:
 I didn't know gcc had pure functions. It doesn't have immutable data. If
 it does optimize with it, you can try it and see!

It seems to work: [...] As you can see now there's just one call to bar. Bye, bearophile

Does GCC complain if you do something clearly impure inside bar? --bb
Dec 22 2008
prev sibling parent "Dave" <Dave_Member pathlink.com> writes:
On a real program, how much faster is my code going to get, if I maximize 
use of pure functions and immutable data? I don't know. I don't have any 
experience with it on a large program.<


I was on a large project not too long ago which used some formal eval questionaires to gauge quality (much of it subjective). Long story short, the overall "quality" rating went up significantly after the only thing that changed was a few passes through the bottlenecks to improve performance in those areas. Say, 2% of the code. Slow areas in any program really bring down the overall user opinion of said program I think. So, since the bottlenecks usually come down to just a few lines of code, the big advantage of the optimizations for immutable and pure to me would be avoiding having to often "drop down" into asm., manually re-writing to "hoist" duplicative code out of tight loops or experimenting with load -> update -> store patterns to get the compiler to spit out the best code. All this can be time-consuming and error-prone so I would think that for some programs your work here would be very valuable, and save quite a bit of development time and cost _if_ the developer took advantage of pure and immutable, consistently, where applicable. Especially in libraries. - Dave
Dec 24 2008
prev sibling parent reply Jerry Quinn <jlquinn optonline.net> writes:
Walter Bright Wrote:

 I've been working on improving the optimizer to take advantage of 
 immutability and purity.
 
 http://www.reddit.com/r/reddit.com/comments/7l5x4/optimizing_immutable_and_purity/
 
 http://dobbscodetalk.com/index.php?option=com_myblog&show=Optimizing-Immutable-and-Purity.html&Itemid=29

This was an interesting read. It would be nice to see a discussion of how const is going to fit in in terms of optimization potential, since you can always cast it away. Jerry
Dec 22 2008
next sibling parent reply "Bill Baxter" <wbaxter gmail.com> writes:
On Tue, Dec 23, 2008 at 11:30 AM, Jerry Quinn <jlquinn optonline.net> wrote:
 Walter Bright Wrote:

 I've been working on improving the optimizer to take advantage of
 immutability and purity.

 http://www.reddit.com/r/reddit.com/comments/7l5x4/optimizing_immutable_and_purity/

 http://dobbscodetalk.com/index.php?option=com_myblog&show=Optimizing-Immutable-and-Purity.html&Itemid=29

This was an interesting read. It would be nice to see a discussion of how const is going to fit in in terms of optimization potential, since you can always cast it away.

It's basically useless for optimizations I think. Even if the view of the data you have is const, someone else might have a non-const view of the same data. So for instance, if you call any function, your "const" data could have been changed via non-const global pointers to the same data. --bb
Dec 22 2008
next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Bill Baxter wrote:
 On Tue, Dec 23, 2008 at 11:30 AM, Jerry Quinn <jlquinn optonline.net>
 wrote:
 This was an interesting read.  It would be nice to see a discussion
 of how const is going to fit in in terms of optimization potential,
 since you can always cast it away.

It's basically useless for optimizations I think. Even if the view of the data you have is const, someone else might have a non-const view of the same data. So for instance, if you call any function, your "const" data could have been changed via non-const global pointers to the same data.

Right. It's useless. Casting away const and immutable also puts one into undefined behavior territory.
Dec 22 2008
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Bill Baxter wrote:
 On Tue, Dec 23, 2008 at 11:30 AM, Jerry Quinn <jlquinn optonline.net> wrote:
 Walter Bright Wrote:

 I've been working on improving the optimizer to take advantage of
 immutability and purity.

 http://www.reddit.com/r/reddit.com/comments/7l5x4/optimizing_immutable_and_purity/

 http://dobbscodetalk.com/index.php?option=com_myblog&show=Optimizing-Immutable-and-Purity.html&Itemid=29


It's basically useless for optimizations I think. Even if the view of the data you have is const, someone else might have a non-const view of the same data. So for instance, if you call any function, your "const" data could have been changed via non-const global pointers to the same data. --bb

Const is still useful because inside a function you know for sure that another thread can't modify the data. Andrei
Dec 23 2008
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Andrei Alexandrescu wrote:
 Bill Baxter wrote:
 On Tue, Dec 23, 2008 at 11:30 AM, Jerry Quinn <jlquinn optonline.net> 
 wrote:
 This was an interesting read.  It would be nice to see a discussion 
 of how const is going to fit in in terms of optimization potential, 
 since you can always cast it away.

It's basically useless for optimizations I think. Even if the view of the data you have is const, someone else might have a non-const view of the same data. So for instance, if you call any function, your "const" data could have been changed via non-const global pointers to the same data. --bb

Const is still useful because inside a function you know for sure that another thread can't modify the data.

I think you meant immutable.
Dec 23 2008
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Bill Baxter wrote:
 On Tue, Dec 23, 2008 at 11:30 AM, Jerry Quinn <jlquinn optonline.net> 
 wrote:
 This was an interesting read.  It would be nice to see a discussion 
 of how const is going to fit in in terms of optimization potential, 
 since you can always cast it away.

It's basically useless for optimizations I think. Even if the view of the data you have is const, someone else might have a non-const view of the same data. So for instance, if you call any function, your "const" data could have been changed via non-const global pointers to the same data. --bb

Const is still useful because inside a function you know for sure that another thread can't modify the data.

I think you meant immutable.

I meant const. Andrei
Dec 23 2008
next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Andrei Alexandrescu wrote:
 Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Bill Baxter wrote:
 On Tue, Dec 23, 2008 at 11:30 AM, Jerry Quinn 
 <jlquinn optonline.net> wrote:
 This was an interesting read.  It would be nice to see a discussion 
 of how const is going to fit in in terms of optimization potential, 
 since you can always cast it away.

It's basically useless for optimizations I think. Even if the view of the data you have is const, someone else might have a non-const view of the same data. So for instance, if you call any function, your "const" data could have been changed via non-const global pointers to the same data. --bb

Const is still useful because inside a function you know for sure that another thread can't modify the data.

I think you meant immutable.

I meant const.

In the future, of course, "shared const" means another thread can modify it, but "const" means it cannot. Is that what you meant?
Dec 23 2008
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Bill Baxter wrote:
 On Tue, Dec 23, 2008 at 11:30 AM, Jerry Quinn 
 <jlquinn optonline.net> wrote:
 This was an interesting read.  It would be nice to see a 
 discussion of how const is going to fit in in terms of 
 optimization potential, since you can always cast it away.

It's basically useless for optimizations I think. Even if the view of the data you have is const, someone else might have a non-const view of the same data. So for instance, if you call any function, your "const" data could have been changed via non-const global pointers to the same data. --bb

Const is still useful because inside a function you know for sure that another thread can't modify the data.

I think you meant immutable.

I meant const.

In the future, of course, "shared const" means another thread can modify it, but "const" means it cannot. Is that what you meant?

Here's an example: int foo(const int*); void bar() { int a = 5; foo(&a); // can assume a is unmodified? } There are two issues here. One is that the const guarantees that foo does not legally change a, so it is useful for an optimization (e.g. assume that a == 5 after the call to foo). The second issue is that compilers often assume that a function call may change the stack of the caller in an arbitrary way. I think it is safe to lift that assumption for D programs and consider a functions' automatic variables as private to the function. Andrei
Dec 24 2008
next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Andrei Alexandrescu wrote:
 Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Const is still useful because inside a function you know for sure 
 that another thread can't modify the data.

I think you meant immutable.

I meant const.

In the future, of course, "shared const" means another thread can modify it, but "const" means it cannot. Is that what you meant?

Here's an example: int foo(const int*); void bar() { int a = 5; foo(&a); // can assume a is unmodified? } There are two issues here. One is that the const guarantees that foo does not legally change a, so it is useful for an optimization (e.g. assume that a == 5 after the call to foo). The second issue is that compilers often assume that a function call may change the stack of the caller in an arbitrary way. I think it is safe to lift that assumption for D programs and consider a functions' automatic variables as private to the function.

I see what you mean, now. I thought you were talking about inside foo(). You're right that as far as bar() goes, foo() will not change a. C and C++ optimizers assume that for locals which never have their address taken, function calls will not change them. This assumption must be valid otherwise locals could never be assigned to registers. If the address is taken, it must be assumed that calling a function will modify them.
Dec 24 2008
prev sibling parent reply Jason House <jason.james.house gmail.com> writes:
Andrei Alexandrescu Wrote:

 Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Bill Baxter wrote:
 On Tue, Dec 23, 2008 at 11:30 AM, Jerry Quinn 
 <jlquinn optonline.net> wrote:
 This was an interesting read.  It would be nice to see a 
 discussion of how const is going to fit in in terms of 
 optimization potential, since you can always cast it away.

It's basically useless for optimizations I think. Even if the view of the data you have is const, someone else might have a non-const view of the same data. So for instance, if you call any function, your "const" data could have been changed via non-const global pointers to the same data. --bb

Const is still useful because inside a function you know for sure that another thread can't modify the data.

I think you meant immutable.

I meant const.

In the future, of course, "shared const" means another thread can modify it, but "const" means it cannot. Is that what you meant?

Here's an example: int foo(const int*); void bar() { int a = 5; foo(&a); // can assume a is unmodified? } There are two issues here. One is that the const guarantees that foo does not legally change a, so it is useful for an optimization (e.g. assume that a == 5 after the call to foo). The second issue is that compilers often assume that a function call may change the stack of the caller in an arbitrary way. I think it is safe to lift that assumption for D programs and consider a functions' automatic variables as private to the function. Andrei

You have to be extremely careful with this kind of thing. If any calls are made with a mutable &a before the call to foo, that optimization can no longer be performed. Also, if a's type changes and used a custom constructor, then that optimization is unreliable for anything other than taking the object's address. If a mutable reference is leaked, all function calls become suspect...
Dec 24 2008
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Jason House wrote:
 Andrei Alexandrescu Wrote:
 
 Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Bill Baxter wrote:
 On Tue, Dec 23, 2008 at 11:30 AM, Jerry Quinn 
 <jlquinn optonline.net> wrote:
 This was an interesting read.  It would be nice to see a 
 discussion of how const is going to fit in in terms of 
 optimization potential, since you can always cast it away.

Even if the view of the data you have is const, someone else might have a non-const view of the same data. So for instance, if you call any function, your "const" data could have been changed via non-const global pointers to the same data. --bb

that another thread can't modify the data.



In the future, of course, "shared const" means another thread can modify it, but "const" means it cannot. Is that what you meant?

int foo(const int*); void bar() { int a = 5; foo(&a); // can assume a is unmodified? } There are two issues here. One is that the const guarantees that foo does not legally change a, so it is useful for an optimization (e.g. assume that a == 5 after the call to foo). The second issue is that compilers often assume that a function call may change the stack of the caller in an arbitrary way. I think it is safe to lift that assumption for D programs and consider a functions' automatic variables as private to the function. Andrei

You have to be extremely careful with this kind of thing. If any calls are made with a mutable &a before the call to foo, that optimization can no longer be performed. Also, if a's type changes and used a custom constructor, then that optimization is unreliable for anything other than taking the object's address. If a mutable reference is leaked, all function calls become suspect...

Care goes without saying. Andrei
Dec 24 2008
parent Jason House <jason.james.house gmail.com> writes:
Andrei Alexandrescu wrote:

 Jason House wrote:
 Andrei Alexandrescu Wrote:
 There are two issues here. One is that the const guarantees that foo
 does not legally change a, so it is useful for an optimization (e.g.
 assume that a == 5 after the call to foo). The second issue is that
 compilers often assume that a function call may change the stack of the
 caller in an arbitrary way. I think it is safe to lift that assumption
 for D programs and consider a functions' automatic variables as private
 to the function.


 Andrei

You have to be extremely careful with this kind of thing. If any calls are made with a mutable &a before the call to foo, that optimization can no longer be performed. Also, if a's type changes and used a custom constructor, then that optimization is unreliable for anything other than taking the object's address. If a mutable reference is leaked, all function calls become suspect...

Care goes without saying. Andrei

The underlying question the optimizer must answer when doing this kind of optimization is "are there any other mutable references"? My whole set of caveats above is all about answering that question. Once upon a time, I had convinced myself that a complete const system would address that. Maybe when it's time to come back and do a complete solution to scope delegates and escape analysis, this kind of thing could be explored further.
Dec 28 2008
prev sibling next sibling parent KennyTM~ <kennytm gmail.com> writes:
Andrei Alexandrescu wrote:
 Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Bill Baxter wrote:
 On Tue, Dec 23, 2008 at 11:30 AM, Jerry Quinn 
 <jlquinn optonline.net> wrote:
 This was an interesting read.  It would be nice to see a discussion 
 of how const is going to fit in in terms of optimization potential, 
 since you can always cast it away.

It's basically useless for optimizations I think. Even if the view of the data you have is const, someone else might have a non-const view of the same data. So for instance, if you call any function, your "const" data could have been changed via non-const global pointers to the same data. --bb

Const is still useful because inside a function you know for sure that another thread can't modify the data.

I think you meant immutable.

I meant const. Andrei

I think const means readonly in C# which means a huge glass wall is put in front of you so only you can't mess with the variable?
Dec 24 2008
prev sibling parent reply Jason House <jason.james.house gmail.com> writes:
Andrei Alexandrescu Wrote:

 Walter Bright wrote:
 Andrei Alexandrescu wrote: 
 Const is still useful because inside a function you know for sure that 
 another thread can't modify the data.

I think you meant immutable.

I meant const. Andrei

At least for the current D2, your statement is very wrong. For function calls, const is merely a promise by the callee to not modify the data or call non-const member functions. Any data can be passed into the function. That means that mutable references can exist through other threads, global variables, or through other input parameters. Const data can change at any time. Even if we jump forward to a D2 where only shared const can be modified by other threads, the guarantees are not much better. Every impure function call can modify the data. That includes const member functions of const data! I've complained about that last bit many times. The bottom line is that const gives no guarantees.
Dec 24 2008
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Jason House wrote:
 Andrei Alexandrescu Wrote:
 
 Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Const is still useful because inside a function you know for
 sure that another thread can't modify the data.


Andrei

At least for the current D2, your statement is very wrong.

Yah.
 For
 function calls, const is merely a promise by the callee to not modify
 the data or call non-const member functions. Any data can be passed
 into the function. That means that mutable references can exist
 through other threads, global variables, or through other input
 parameters. Const data can change at any time.

In D2, threads will be effectively memory-isolated. Walter, Bartosz, and I are convinced that this is a very solid model to start with. Sharing among threads will be explicit by means of a "shared" type constructor. Everything else will be unshared. This is in contrast with the C, C++, and Java model in which all threads share memory indiscriminately (and it's up to the programmer to painstakingly ensure that no undue sharing is happening and that all sharing is properly synchronized). I think that model will go the way of the dinosaur. For const, this means that const data can be assumed to be modified through aliases in the current thread, but not in other threads. So if the compiler proves no aliasing for a code region, const is as good as immutable.
 Even if we jump forward to a D2 where only shared const can be
 modified by other threads, the guarantees are not much better. Every
 impure function call can modify the data. That includes const member
 functions of const data! I've complained about that last bit many
 times.
 
 The bottom line is that const gives no guarantees.

See the example in my other post. Andrei
Dec 24 2008
prev sibling parent "Jarrett Billingsley" <jarrett.billingsley gmail.com> writes:
On Tue, Dec 23, 2008 at 3:23 PM, Walter Bright
<newshound1 digitalmars.com> wrote:
 I think you meant immutable.

Are there going to be docs on this "immutable" soon? It's been around for two months now..
Dec 23 2008