C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Huge C++ Optimization Hole Goto page 1, 2  Next          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Jeff Keasler Guest Posted: Thu Oct 16, 2003 2:19 pm    Post subject: Huge C++ Optimization Hole Hi, I've tried compiling the two code fragments below on the SGI, IBM, Intel, Sun, and Alpha platforms using the vendor compilers, and I also tried g++ on the Intel (686) machine. I compiled all levels of optimization and -S to see the assembly code, and was dismayed at how horribly the inner loop was optimized for the second case, even though they should have resulted in identical optimizations. Why is this a problem to do right for the people who optimize the C++ compilers? It seems that as long as I don't use -g in any of it's forms, this would be very easy to optimize. Thanks, Jeff Keasler ------------------------------------------------------------- void junk(int * const data, int a, int b, int length) { int i, j ; for (i=0; i for (j=0; j data[length*i + j] = 0 ; } -------------------------------------------------------------- class relation { int const length ; int const size ; int * const data ; public: relation(int len, int sz) : length(len), size(sz), data(new int[len*sz]) { } ~relation() { delete [] data ; } inline int &operator() (int srcIdx, int destIdx) const { return data[length*srcIdx + destIdx] ; } } ; void junk(class relation &foo, int a, int b) { int i, j ; /*ie class relation foo(a, b) ; */ for (i=0; i for (j=0; j foo(i, j) = 0 ; } ---------------------------------------------------------------- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Bo Persson Guest Posted: Thu Oct 16, 2003 8:46 pm    Post subject: Re: Huge C++ Optimization Hole "Jeff Keasler" <jeff (AT) svn (DOT) net> skrev i meddelandet news:vorua2n86aau7c (AT) corp (DOT) supernews.com... Quote: Hi, I've tried compiling the two code fragments below on the SGI, IBM, Intel, Sun, and Alpha platforms using the vendor compilers, and I also tried g++ on the Intel (686) machine. I compiled all levels of optimization and -S to see the assembly code, and was dismayed at how horribly the inner loop was optimized for the second case, even though they should have resulted in identical optimizations. Why is this a problem to do right for the people who optimize the C++ compilers? It seems that as long as I don't use -g in any of it's forms, this would be very easy to optimize. Thanks, Jeff Keasler ------------------------------------------------------------- void junk(int * const data, int a, int b, int length) { int i, j ; for (i=0; i for (j=0; j data[length*i + j] = 0 ; } -------------------------------------------------------------- class relation { int const length ; int const size ; int * const data ; public: relation(int len, int sz) : length(len), size(sz), data(new int[len*sz]) { } ~relation() { delete [] data ; } inline int &operator() (int srcIdx, int destIdx) const { return data[length*srcIdx + destIdx] ; } } ; void junk(class relation &foo, int a, int b) { int i, j ; /*ie class relation foo(a, b) ; */ for (i=0; i for (j=0; j foo(i, j) = 0 ; } ---------------------------------------------------------------- This is an aliasing problem. To be able to optimize this, the compiler must prove that the reference returned by foo will never, ever, EVER return a reference to any of i, j, a, or b. In this specific case it would be possible to do so, but obviously the case is not common enough to attract the attention of the compiler writers. I don't blame them. :-) Bo Persson [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Michael Albert Guest Posted: Fri Oct 17, 2003 9:46 am    Post subject: Re: Huge C++ Optimization Hole On Thu, 16 Oct 2003, Bo Persson wrote: Quote: "Jeff Keasler" <jeff (AT) svn (DOT) net> skrev i meddelandet news:vorua2n86aau7c (AT) corp (DOT) supernews.com... void junk(int * const data, int a, int b, int length) { int i, j ; for (i=0; i for (j=0; j data[length*i + j] = 0 ; } -------------------------------------------------------------- class relation { int const length ; int const size ; int * const data ; public: relation(int len, int sz) : length(len), size(sz), data(new int[len*sz]) { } ~relation() { delete [] data ; } inline int &operator() (int srcIdx, int destIdx) const { return data[length*srcIdx + destIdx] ; } } ; void junk(class relation &foo, int a, int b) { int i, j ; /*ie class relation foo(a, b) ; */ for (i=0; i for (j=0; j foo(i, j) = 0 ; } ---------------------------------------------------------------- This is an aliasing problem. To be able to optimize this, the compiler must prove that the reference returned by foo will never, ever, EVER return a reference to any of i, j, a, or b. In this specific case it would be possible to do so, but obviously the case is not common enough to attract the attention of the compiler writers. I don't blame them. Isn't problem with the second version that the compiler can not prove that the foo.data array won't contain foo.length? In both cases, 'i', 'j', 'a', and 'b' are either local on passed in parameters, so the compiler can check that their addresses have never been used. However, in the first example 'length' is also a parameter, while in second example foo.length is somewhere in memory and it can't be easily determined if &foo.length was ever used. I am not an expert on these things. Please feel free to educate me . Best wishes, Mike [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Jeff Keasler Guest Posted: Fri Oct 17, 2003 9:47 am    Post subject: Re: Huge C++ Optimization Hole "Bo Persson" <bop (AT) gmb (DOT) dk> wrote Quote: This is an aliasing problem. To be able to optimize this, the compiler must prove that the reference returned by foo will never, ever, EVER return a reference to any of i, j, a, or b. In this specific case it would be possible to do so, but obviously the case is not common enough to attract the attention of the compiler writers. I don't blame them. :-) Bo Persson Everything is const, so it doesn't matter. It should optimize. The effectiveness of compiling this code fragment is related to the ability to make efficient iterators. Considering the Intel 686 compiler produces 8 instructions for each iteration of the inner loop when it doesn't optimize well (4 memory operations, 1 mul, 1 xor, plus 2 adds) vs. 3 instructions for the other case (1 memory op , 1 add, and one compare) I'd say it makes a huge difference in code performance, and is extremely relevant. -Jeff Keasler [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top lixan Guest Posted: Fri Oct 17, 2003 11:15 am    Post subject: Re: Huge C++ Optimization Hole Quote: This is an aliasing problem. To be able to optimize this, the compiler must prove that the reference returned by foo will never, ever, EVER return a reference to any of i, j, a, or b. You say about function level optimize. Why compiler writers can't use optimization on basic operations level [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Andrea Griffini Guest Posted: Fri Oct 17, 2003 3:04 pm    Post subject: Re: Huge C++ Optimization Hole On 17 Oct 2003 05:47:01 -0400, "Jeff Keasler" <jeff (AT) svn (DOT) net> wrote: Quote: Everything is const, so it doesn't matter. It should optimize. Const-ness of methods or references is *never* an help for the optimizer, as it is legal to cast-away constness. It is just an help for the programmer for understanding what a reference or method is meant to do. In the code there can't however be any aliasing, as i,j,a and b are local variables of which the address was never taken and consequently there is no legal way to obtain such an address. Quote: The effectiveness of compiling this code fragment is related to the ability to make efficient iterators. Considering the Intel 686 compiler produces 8 instructions for each iteration of the inner loop when it doesn't optimize well (4 memory operations, 1 mul, 1 xor, plus 2 adds) vs. 3 instructions for the other case (1 memory op , 1 add, and one compare) I'd say it makes a huge difference in code performance, and is extremely relevant. I've experienced similar problems with an experiment I made some time ago doing a comparision between the code generated by using a 3d-point class and hand-unrolled code that was manipulating coordinates explicitly. Depending on how I was implementing the operations in C++ I was able to get variable code quality, but unfortunately the implementation that was good for one compiler was bad for another. Moreover I was never able to come close to the code efficency of the manually unrolled version. My suspect is that the peephole optimizers are currently tuned for code sequences that are the typical output of a C compiler. HTH Andrea [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Bo Persson Guest Posted: Fri Oct 17, 2003 4:45 pm    Post subject: Re: Huge C++ Optimization Hole "Jeff Keasler" <jeff (AT) svn (DOT) net> wrote Quote: Everything is const, so it doesn't matter. It should optimize. Here the pointer is const, but the int pointed to is not: int * const data ; To optimize this to the max, the compiler must be sure what *data is at every time, so that it cannot *ever* overlap another int. This is the aliasing curse inherited from C! What if some parameter to junk() isn't a relation, but a subclass of foo with another initializer? I don't know if it possibly could, and wouldn't expect compiler writers to spend their time on corner cases like this. There are more important cases to work on. Bo Persson [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Bo Persson Guest Posted: Fri Oct 17, 2003 4:45 pm    Post subject: Re: Huge C++ Optimization Hole "lixan" <lixan (AT) infotrans-logistic (DOT) ru> skrev i meddelandet news:bmo3vs$2m67$1 (AT) berg (DOT) samara.net... Quote: This is an aliasing problem. To be able to optimize this, the compiler must prove that the reference returned by foo will never, ever, EVER return a reference to any of i, j, a, or b. You say about function level optimize. Why compiler writers can't use optimization on basic operations level Compiler writers can optimize on any level they like. The problem here is that the update goes thru the pointer int * const data ; To optimize the expression properly, the compiler must be sure that data[any_index] does not overlap another int in the program. If it ever could, or if the compiler isn't clever enough to determine for certain, it must use safe code which might not be optimal. Bo Persson [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Francis Glassborow Guest Posted: Sat Oct 18, 2003 1:34 pm    Post subject: Re: Huge C++ Optimization Hole In article <i8ivov4s35j3ge7qqa05pm09hg17udhfvf (AT) 4ax (DOT) com>, Andrea Griffini <agriff (AT) tin (DOT) it> writes Quote: On 17 Oct 2003 05:47:01 -0400, "Jeff Keasler" <jeff (AT) svn (DOT) net> wrote: Everything is const, so it doesn't matter. It should optimize. Const-ness of methods or references is *never* an help for the optimizer, as it is legal to cast-away constness. It is just an help for the programmer for understanding what a reference or method is meant to do. I think you are mistaken. It is undefined behaviour to cast away the constness of an object that has been defined as const. You can cast const away from a const reference or pointer but only if the underlying object was not declared as const. -- Francis Glassborow ACCU If you are not using up-to-date virus protection you should not be reading this. Viruses do not just hurt the infected but the whole community. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Jeff Keasler Guest Posted: Sat Oct 18, 2003 1:42 pm    Post subject: Re: Huge C++ Optimization Hole The frustrating thing here is that there's a mutable keyword in C++ that is designed to handle a changing const. When I declare length const in C++, it seems like it should mean const!! There oughta be a law... (or at least a compiler switch to indicate I want to use C++isms without any C baggage where I can). Thanks for your comments, -Jeff "Bo Persson" <bop (AT) gmb (DOT) dk> wrote Quote: "Jeff Keasler" <jeff (AT) svn (DOT) net> wrote Everything is const, so it doesn't matter. It should optimize. Here the pointer is const, but the int pointed to is not: int * const data ; To optimize this to the max, the compiler must be sure what *data is at every time, so that it cannot *ever* overlap another int. This is the aliasing curse inherited from C! What if some parameter to junk() isn't a relation, but a subclass of foo with another initializer? I don't know if it possibly could, and wouldn't expect compiler writers to spend their time on corner cases like this. There are more important cases to work on. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Jeff Keasler Guest Posted: Sat Oct 18, 2003 1:45 pm    Post subject: Re: Huge C++ Optimization Hole "Michael Albert" <albert (AT) rad (DOT) upenn.edu> wrote Quote: Isn't problem with the second version that the compiler can not prove that the foo.data array won't contain foo.length? In both cases, 'i', 'j', 'a', and 'b' are either local on passed in parameters, so the compiler can check that their addresses have never been used. However, in the first example 'length' is also a parameter, while in second example foo.length is somewhere in memory and it can't be easily determined if &foo.length was ever used. I am not an expert on these things. Please feel free to educate me . Hi Mike, Thanks for your comments. In this particular case, length is only set at construction time, and since the member is private, there is not way for a non-method to find it's address (as I have written the class). Furthermore, and no method takes it's address or writes to it other than the constructor, so in affect, it is "safe" in its little cubbyhole where noone has a real chance to find out where it is, so in theory there's no way to have a reference to it. I'm moving this discussion to comp.compilers under the subject "What's the point of C++ mutable in your C++ compiler?" Please head over there if you're interested in seeing how this pans out. Thanks, -Jeff Keasler [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Andrea Griffini Guest Posted: Sat Oct 18, 2003 11:10 pm    Post subject: Re: Huge C++ Optimization Hole On 18 Oct 2003 09:34:03 -0400, Francis Glassborow <francis (AT) robinton (DOT) demon.co.uk> wrote: Quote: In article <i8ivov4s35j3ge7qqa05pm09hg17udhfvf (AT) 4ax (DOT) com>, Andrea Griffini [email]agriff (AT) tin (DOT) it[/email]> writes On 17 Oct 2003 05:47:01 -0400, "Jeff Keasler" <jeff (AT) svn (DOT) net> wrote: Everything is const, so it doesn't matter. It should optimize. Const-ness of methods or references is *never* an help for the optimizer, as it is legal to cast-away constness. It is just an help for the programmer for understanding what a reference or method is meant to do. I think you are mistaken. It is undefined behaviour to cast away the constness of an object that has been defined as const. That's why I said const-ness *of methods or references*. Const objects are a different thing, and those can obviously help the optimizer. Quote: You can cast const away from a const reference or pointer but only if the underlying object was not declared as const. Now I see the problem ... the compiler should have been able to see that for example "data" and "lenght" were not going to change during the loop because they're declared as a const objects. Not considering them const I can see (playing the paranoid part) a potential aliasing problem with "lenght": data is initialized with what ::operator new returns, and writing through an unknown pointer to int can potentially change any int ... Andrea [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Dave Harris Guest Posted: Sat Oct 18, 2003 11:23 pm    Post subject: Re: Huge C++ Optimization Hole [email]albert (AT) rad (DOT) upenn.edu[/email] (Michael Albert) wrote (abridged): Quote: Isn't problem with the second version that the compiler can not prove that the foo.data array won't contain foo.length? Perhaps. In this case the proof is trivial, because foo.length is a const object. This: struct Array { const int length; int *const data; Array() : length(1), data(&length) { } }; won't compile. If we forced it to compile with a const_cast, writing though *data would be undefined behaviour anyway. Similarly, although we could set data to some random address: Array() : length(1), data((int *)0x42424242) { and this could turn out to be an alias for some local variable, indirecting through it would also be undefined behaviour so the optimiser doesn't have to worry about it. Likewise if we got that address by moving off the end of some array. Pointer arithmetic is quite restricted. -- Dave Harris, Nottingham, UK [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Michael Jørgensen Guest Posted: Sun Oct 19, 2003 8:01 am    Post subject: Re: Huge C++ Optimization Hole "Jeff Keasler" <jeff (AT) svn (DOT) net> wrote Quote: The frustrating thing here is that there's a mutable keyword in C++ that is designed to handle a changing const. When I declare length const in C++, it seems like it should mean const!! There oughta be a law... (or at least a compiler switch to indicate I want to use C++isms without any C baggage where I can). Perhaps an "immutable" keybord? -Michael. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Jeff Keasler Guest Posted: Sun Oct 19, 2003 9:40 pm    Post subject: Re: Huge C++ Optimization Hole "Andrea Griffini" <agriff (AT) tin (DOT) it> wrote Quote: Now I see the problem ... the compiler should have been able to see that for example "data" and "lenght" were not going to change during the loop because they're declared as a const objects. Also, the inline fuction is delared as const, meaning that whatever it does, it's guaranteed not to change any members. I thought explicitly tipping off the compiler like this should make a big difference, but it didn't. Quote: Not considering them const I can see (playing the paranoid part) a potential aliasing problem with "lenght": data is initialized with what ::operator new returns, and writing through an unknown pointer to int can potentially change any int ... Andrea I've thought about the new operator also. The length member of the class was created with an integer copy constructor and put into a private part of the class which in some respect should mean it is hidden from the outside world in all possible ways. If compiler writers are not addressing this because of the ::new, we are all in trouble. This means any C++ program that uses new anywhere would not be optimizable!! Thanks, -Jeff [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.