Re: a question about code optimization

Re: a question about code optimization

[龙海涛]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=GB2312, Size: 1631 bytes --]

John Love-Jensen дµÀ:
> Hi,
> 
> In this particular example, the size() method is inline, so the compiler
> injects it locally into the code, and hence the compiler is aware if size()
> changes some global variable or not.
> 
> If size() were non-inline, it would be a "black box" to the optimizer, so in
> that case your analysis is correct.
> 
> --Eljay

yes, size() function is inline, but consider this situation: we can call
some non-inline functions in inline function,i.e,

void foo_non_inline();

inline int foo_inline() {
	/*...*/
	foo_non_inline();
	/*...*/
}

obviously we are not sure that the global variabls are changed or not in foo_non_inline();

So my questions is:
is gcc *smart* enough that she can determine when to do the optimization?


> 
> On 12/21/07 11:41 PM, "Áúº£ÌÎ" <longhaitao@otsc.com.cn> wrote:
> 
>> ---------code-----------
>> vector<int> a;
>> /*do somthing*/
>> for(int i = 0; i<a.size(); i++) {
>> /* do something*/
>> }
>> --------code end--------
>>
>> my question is:
>> is it possible that the compiler will transform the code to this:
>>
>> int __tmp = a.size();
>> for(int i = 0; i < __tmp; i++) {
>> /*do something*/
>> }
>>
>> i think it is impoossible,because in size() function, the programmer
>> can change some global variables, so the compiler could not do that.
>>
>> if gcc can, could you tell me how?
>>
>> i am sorry in advance because i am not familiar with the code optimization.
>> so i do not know how to search the gcc manual and gcc internal manual to find
>> answer.could anyone tell me how to find this in the manual£¿or at least give
>> some keywords?
> 

Re: a question about code optimization

[John Love-Jensen]

Hi,

> So my questions is:
> is gcc *smart* enough that she can determine when to do the optimization?

Yes.

GCC can do the optimization when the optimizer has sufficient information to
be certain that there are no side effects.

GCC can not do the optimization when there is a black-box routine involved.
Although there may be some aspects outside of the black-box routine that may
be optimized.

There is another compiler, LLVM, that does holistic optimizations.  If I
recall correct, there is an effort to add (or perhaps merely to investigate
adding) holistic optimizations into GCC.

--Eljay

Re: a question about code optimization

[龙海涛]

John Love-Jensen 写道:
> Hi,
> 
>> So my questions is:
>> is gcc *smart* enough that she can determine when to do the optimization?
> 
> Yes.
> 
> GCC can do the optimization when the optimizer has sufficient information to
> be certain that there are no side effects.
> 
> GCC can not do the optimization when there is a black-box routine involved.
> Although there may be some aspects outside of the black-box routine that may
> be optimized.
> 
> There is another compiler, LLVM, that does holistic optimizations.  If I
> recall correct, there is an effort to add (or perhaps merely to investigate
> adding) holistic optimizations into GCC.
thanks for your patient answer :)

another question:

--------code begin----------------
vector<int> a;
...
for(int i = 0; i < a.size(); i++)
{
	/*do something*/
}
-------code end---------------------

i asked that if this can be optimized to this:
----------code begin--------------
vector<int> a;
...
int size = a.size();
for(int i = 0; i < size; i++)
{
	/*do something*/
}
----------code end-----------------

last time we discussed one situation may influence the optimization:

a) in function size() we may change some global variables.

there is another situation:

b) in the /*do something*/ block, we may use a.push_back(...) or some other functions
that can change the size of a. if this happen, of course we can not do the optimization.

so can gcc know what functions may change the size of a?
is gcc smart enough to optimize the code if those functions are not used?

i am sorry because i am not familiar with the optimization term.


> 
> --Eljay
> 

Re: a question about code optimization

[龙海涛]

> another question:
> 
> --------code begin----------------
> vector<int> a;
> ...
> for(int i = 0; i < a.size(); i++)
> {
>     /*do something*/
> }
> -------code end---------------------
> 
> i asked that if this can be optimized to this:
> ----------code begin--------------
> vector<int> a;
> ...
> int size = a.size();
> for(int i = 0; i < size; i++)
> {
>     /*do something*/
> }
> ----------code end-----------------
> 
> last time we discussed one situation may influence the optimization:
> 
> a) in function size() we may change some global variables.
> 
> there is another situation:
> 
> b) in the /*do something*/ block, we may use a.push_back(...) or some 
> other functions
> that can change the size of a. if this happen, of course we can not do 
> the optimization.
> 
> so can gcc know what functions may change the size of a?
> is gcc smart enough to optimize the code if those functions are not used?
well, i think the possible implementations are:

a) we tell the gcc what function may change the size of a vector
b) in the internal of gcc, gcc can find them out

which one is more reasonble? or none of them?

-- Kevin Long

Re: a question about code optimization

[John Love-Jensen]

Hi Kevin Long,

> b) in the /*do something*/ block, we may use a.push_back(...) or some other
> functions
> that can change the size of a. if this happen, of course we can not do the
> optimization.

Correct.

> so can gcc know what functions may change the size of a?

Yes, if GCC has sufficient information to guarantee that the size of a is
not being changed it can perform the LIM optimization and hoist the a.size()
method out of the routine.

Note:  a.size() can be hoisted out because it is an inline function.

> is gcc smart enough to optimize the code if those functions are not used?

Yes.

> i am sorry because i am not familiar with the optimization term.

Move loop invariant optimization.  Or loop invariant motion optimization.
Usually abbreviated LIM.

> a) we tell the gcc what function may change the size of a vector

And most C++ compilers accomplish that at a "veneer" level (versus a
"holistic" level).  By the heavy use of inline functions to expose (and
inject) the innards of the methods into the location, "as if" the body of
the routines were typed in place.

Small inline functions optimize very well, and the optimizer has enough
information to perform LIM optimizations.  Especially for leaf-loops (loops
that do not call any non-inline functions within the loop).

NOTE:  I'm assuming correct code.  Incorrect code (what I tend to call
"pathological code") can cause unexpected behavior.  For example, if the
code violates aliasing rules, all bets are off.

> b) in the internal of gcc, gcc can find them out

That's a holistic optimization.  The kind that the LLVM compiler performs,
or the Java JIT optimizer performs.

> which one is more reasonble? or none of them?

They are both reasonable.

I expect the holistic optimization is tricky to implement, and requires
significant infrastructure to support at the object code and library levels.

Sincerely,
--Eljay

a question about code optimization

[龙海涛]

---------code-----------
vector<int> a;
/*do somthing*/
for(int i = 0; i<a.size(); i++) {
	/* do something*/
}
--------code end--------

my question is:
is it possible that the compiler will transform the code to this:

int __tmp = a.size();
for(int i = 0; i < __tmp; i++) {
	/*do something*/
}

i think it is impoossible,because in size() function, the programmer
can change some global variables, so the compiler could not do that.

if gcc can, could you tell me how?

i am sorry in advance because i am not familiar with the code optimization.
so i do not know how to search the gcc manual and gcc internal manual to find
answer.could anyone tell me how to find this in the manual拢驴or at least give
some keywords?

Re: a question about code optimization

[Christoph Bartoschek]

Am Samstag 22 Dezember 2007 schrieb 龙海涛:
> ---------code-----------
> vector<int> a;
> /*do somthing*/
> for(int i = 0; i<a.size(); i++) {
> 	/* do something*/
> }
> --------code end--------
>
> my question is:
> is it possible that the compiler will transform the code to this:
>
> int __tmp = a.size();
> for(int i = 0; i < __tmp; i++) {
> 	/*do something*/
> }
>
> i think it is impoossible,because in size() function, the programmer
> can change some global variables, so the compiler could not do that.
>
> if gcc can, could you tell me how?
>
> i am sorry in advance because i am not familiar with the code
> optimization. so i do not know how to search the gcc manual and gcc
> internal manual to find answer.could anyone tell me how to find this in
> the manual？or at least give some keywords?

Here the situation is quite simple. Because a is a template the 
vector<int>::size() method is probably included in the header files. This 
means that the compiler can examine or inline the code of the method. If the 
compiler additionally determines that in /*do something*/ the size is not 
changed, then the optimization is quite straigthforward.

Christoph

Re: a question about code optimization

[龙海涛]

> Here the situation is quite simple. Because a is a template the 
> vector<int>::size() method is probably included in the header files. This 
> means that the compiler can examine or inline the code of the method. If the 
> compiler additionally determines that in /*do something*/ the size is not 

i want to know whether Gcc can determines the size is changed or not...

i did some experiment, and the result is not bad.

anyone can give me some theoritical hints?

> changed, then the optimization is quite straigthforward
> 
> Christoph