Operation recomputation

[Michel Rouzic]

Hi,

I'd like to know whether an operation which always has the same result
will be recomputed. Here's the context : I in a loop have to compare
many things to foo>>1 in an if statement. In that very if statement I
compare stuff with (foo>>1) about four times, and I'd like to know if
it everytime does the shifting from the original foo value or if it
re-uses the previous result, since the value of foo did not change.

Also I use many times in my loop (bar>>1), same question with it, does
it get calculated over again or not?

I'm asking with >in my example but it can be anything like *, +, -,
/, %, << etc... In case that matters I'm using gcc 3.x/4.x

Thanks in advance

[Barry Schwarz]

On 31 Aug 2006 20:04:02 -0700, "Michel Rouzic" <Mi********@yahoo.fr>
wrote:

>Hi,

I'd like to know whether an operation which always has the same result
will be recomputed. Here's the context : I in a loop have to compare
many things to foo>>1 in an if statement. In that very if statement I
compare stuff with (foo>>1) about four times, and I'd like to know if
it everytime does the shifting from the original foo value or if it
re-uses the previous result, since the value of foo did not change.

Also I use many times in my loop (bar>>1), same question with it, does
it get calculated over again or not?

The answer depends on whether your compiler can recognize the common
sub-expression and the fact that the values have not changed. Some
compilers have options that say optimize for speed or optimize for
space. The language spec does not address the issue.

All in all a quality of implementation issue.
Remove del for email

[Michel Rouzic]

Barry Schwarz wrote:

On 31 Aug 2006 20:04:02 -0700, "Michel Rouzic" <Mi********@yahoo.fr>
wrote:

Hi,

I'd like to know whether an operation which always has the same result
will be recomputed. Here's the context : I in a loop have to compare
many things to foo>>1 in an if statement. In that very if statement I
compare stuff with (foo>>1) about four times, and I'd like to know if
it everytime does the shifting from the original foo value or if it
re-uses the previous result, since the value of foo did not change.

Also I use many times in my loop (bar>>1), same question with it, does
it get calculated over again or not?

The answer depends on whether your compiler can recognize the common
sub-expression and the fact that the values have not changed. Some
compilers have options that say optimize for speed or optimize for
space. The language spec does not address the issue.

All in all a quality of implementation issue.

so, in case of a doubt, I should do the storage of the result myself,
like, make a variable to replace each recurrent operation?

[Nils O. Selåsdal]

Michel Rouzic wrote:

Barry Schwarz wrote:

>On 31 Aug 2006 20:04:02 -0700, "Michel Rouzic" <Mi********@yahoo.fr>
wrote:

>>Hi,

I'd like to know whether an operation which always has the same result
will be recomputed. Here's the context : I in a loop have to compare
many things to foo>>1 in an if statement. In that very if statement I
compare stuff with (foo>>1) about four times, and I'd like to know if
it everytime does the shifting from the original foo value or if it
re-uses the previous result, since the value of foo did not change.

Also I use many times in my loop (bar>>1), same question with it, does
it get calculated over again or not?

The answer depends on whether your compiler can recognize the common
sub-expression and the fact that the values have not changed. Some
compilers have options that say optimize for speed or optimize for
space. The language spec does not address the issue.

All in all a quality of implementation issue.

so, in case of a doubt, I should do the storage of the result myself,
like, make a variable to replace each recurrent operation?

Perhaps. But don't go turning every rock for potential
microoptimizations like this.

[Michel Rouzic]

Nils O. Selåsdal wrote:

Michel Rouzic wrote:

Barry Schwarz wrote:

On 31 Aug 2006 20:04:02 -0700, "Michel Rouzic" <Mi********@yahoo.fr>
wrote:

Hi,

I'd like to know whether an operation which always has the same result
will be recomputed. Here's the context : I in a loop have to compare
many things to foo>>1 in an if statement. In that very if statement I
compare stuff with (foo>>1) about four times, and I'd like to know if
it everytime does the shifting from the original foo value or if it
re-uses the previous result, since the value of foo did not change.

Also I use many times in my loop (bar>>1), same question with it, does
it get calculated over again or not?

The answer depends on whether your compiler can recognize the common
sub-expression and the fact that the values have not changed. Some
compilers have options that say optimize for speed or optimize for
space. The language spec does not address the issue.

All in all a quality of implementation issue.

so, in case of a doubt, I should do the storage of the result myself,
like, make a variable to replace each recurrent operation?

Perhaps. But don't go turning every rock for potential
microoptimizations like this.

in my case it's not a micro optimization (I guess) since for my
(foo>>1) example, I use that 10 times for each pixel I process, and
since I can have up to 6 million pixels to process every second..
that's 60 million shifts a second I can avoid, I presume. Considered
that I'm going to run this code on a 200 MHz ARM920T, it might not be a
micro optimization at all ;-)

[Nils O. Selåsdal]

Michel Rouzic wrote:

Nils O. Selåsdal wrote:

>Michel Rouzic wrote:

>>Barry Schwarz wrote:
On 31 Aug 2006 20:04:02 -0700, "Michel Rouzic" <Mi********@yahoo.fr>
wrote:

Hi,
>
I'd like to know whether an operation which always has the same result
will be recomputed. Here's the context : I in a loop have to compare
many things to foo>>1 in an if statement. In that very if statement I
compare stuff with (foo>>1) about four times, and I'd like to know if
it everytime does the shifting from the original foo value or if it
re-uses the previous result, since the value of foo did not change.
>
Also I use many times in my loop (bar>>1), same question with it, does
it get calculated over again or not?
>
The answer depends on whether your compiler can recognize the common
sub-expression and the fact that the values have not changed. Some
compilers have options that say optimize for speed or optimize for
space. The language spec does not address the issue.

All in all a quality of implementation issue.
so, in case of a doubt, I should do the storage of the result myself,
like, make a variable to replace each recurrent operation?

Perhaps. But don't go turning every rock for potential
microoptimizations like this.

in my case it's not a micro optimization (I guess) since for my
(foo>>1) example, I use that 10 times for each pixel I process, and
since I can have up to 6 million pixels to process every second..
that's 60 million shifts a second I can avoid, I presume. Considered
that I'm going to run this code on a 200 MHz ARM920T, it might not be a
micro optimization at all ;-)

Don't presume.
Profile first, then optimize.

[Michel Rouzic]

Nils O. Selåsdal wrote:

Michel Rouzic wrote:

Nils O. Selåsdal wrote:

Michel Rouzic wrote:
Barry Schwarz wrote:
On 31 Aug 2006 20:04:02 -0700, "Michel Rouzic" <Mi********@yahoo.fr>
wrote:

Hi,

I'd like to know whether an operation which always has the same result
will be recomputed. Here's the context : I in a loop have to compare
many things to foo>>1 in an if statement. In that very if statementI
compare stuff with (foo>>1) about four times, and I'd like to know if
it everytime does the shifting from the original foo value or if it
re-uses the previous result, since the value of foo did not change.

Also I use many times in my loop (bar>>1), same question with it, does
it get calculated over again or not?

The answer depends on whether your compiler can recognize the common
sub-expression and the fact that the values have not changed. Some
compilers have options that say optimize for speed or optimize for
space. The language spec does not address the issue.

All in all a quality of implementation issue.
so, in case of a doubt, I should do the storage of the result myself,
like, make a variable to replace each recurrent operation?
Perhaps. But don't go turning every rock for potential
microoptimizations like this.

in my case it's not a micro optimization (I guess) since for my
(foo>>1) example, I use that 10 times for each pixel I process, and
since I can have up to 6 million pixels to process every second..
that's 60 million shifts a second I can avoid, I presume. Considered
that I'm going to run this code on a 200 MHz ARM920T, it might not be a
micro optimization at all ;-)

Don't presume.
Profile first, then optimize.

Profile? What does it mean?

[Michael Mair]

Michel Rouzic schrieb:

Nils O. Selåsdal wrote:

>>Michel Rouzic wrote:

>>>Nils O. Selåsdal wrote:

Michel Rouzic wrote:

>Barry Schwarz wrote:
>
>>On 31 Aug 2006 20:04:02 -0700, "Michel Rouzic" <Mi********@yahoo.fr>
>>wrote:
>>
>>
>>>Hi,
>>>
>>>I'd like to know whether an operation which always has the same result
>>>will be recomputed. Here's the context : I in a loop have to compare
>>>many things to foo>>1 in an if statement. In that very if statement I
>>>compare stuff with (foo>>1) about four times, and I'd like to know if
>>>it everytime does the shifting from the original foo value or if it
>>>re-uses the previous result, since the value of foo did not change.
>>>
>>>Also I use many times in my loop (bar>>1), same question with it, does
>>>it get calculated over again or not?
>>>
>>
>>The answer depends on whether your compiler can recognize the common
>>sub-expression and the fact that the values have not changed. Some
>>compilers have options that say optimize for speed or optimize for
>>space. The language spec does not address the issue.
>>
>>All in all a quality of implementation issue.
>
>so, in case of a doubt, I should do the storage of the result myself,
>like, make a variable to replace each recurrent operation?

Perhaps. But don't go turning every rock for potential
microoptimizations like this.

in my case it's not a micro optimization (I guess) since for my
(foo>>1) example, I use that 10 times for each pixel I process, and
since I can have up to 6 million pixels to process every second..
that's 60 million shifts a second I can avoid, I presume. Considered
that I'm going to run this code on a 200 MHz ARM920T, it might not be a
micro optimization at all ;-)

Don't presume.
Profile first, then optimize.

Profile? What does it mean?

Measure where you spend how much time (and sometimes memory);
the programmes helping you there are profilers.
Often, you find that -- surprisingly -- your programme spends
much time in a piece of code you never thought of optimizing
or that some "optimization" you thought up makes performance
worse because the compiler no longer recognizes optimisable
patterns and in turn does not perform other optimisations any
longer.

Note on your example: I'd go for the temporary variable -- it
is easier and less compile time consuming to find all uses
of "temp", measure whether replacement by foo>>1 would overall
improve the code or whether using a register for temp may be
better than find out that foo>>1 is used more than once, where
it is used with the same value of foo and that it is the
largest such subexpression that is worth replacing.
However, this is not something I measured for each and every
system, so my advice may be exactly the wrong way for you.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Bill Pursell]

Michel Rouzic wrote:

Barry Schwarz wrote:

On 31 Aug 2006 20:04:02 -0700, "Michel Rouzic" <Mi********@yahoo.fr>
wrote:

>I'd like to know whether an operation which always has the same result
>will be recomputed.

The answer depends on whether your compiler can recognize the common
sub-expression and the fact that the values have not changed. Some
compilers have options that say optimize for speed or optimize for
space. The language spec does not address the issue.

so, in case of a doubt, I should do the storage of the result myself,
like, make a variable to replace each recurrent operation?

If you really must know, look at the output of the compiler
and check to see what it's doing. (ie disassemble the executable.)

[Michel Rouzic]

Michael Mair wrote:

Michel Rouzic schrieb:

Nils O. Selåsdal wrote:

>Michel Rouzic wrote:

Nils O. Selåsdal wrote:

Michel Rouzic wrote:

Barry Schwarz wrote:

>On 31 Aug 2006 20:04:02 -0700, "Michel Rouzic" <Mi********@yahoo.fr>
>wrote:
>
>
>>Hi,
>>
>>I'd like to know whether an operation which always has the same result
>>will be recomputed. Here's the context : I in a loop have to compare
>>many things to foo>>1 in an if statement. In that very if statement I
>>compare stuff with (foo>>1) about four times, and I'd like to knowif
>>it everytime does the shifting from the original foo value or if it
>>re-uses the previous result, since the value of foo did not change.
>>
>>Also I use many times in my loop (bar>>1), same question with it, does
>>it get calculated over again or not?
>>
>
>The answer depends on whether your compiler can recognize the common
>sub-expression and the fact that the values have not changed. Some
>compilers have options that say optimize for speed or optimize for
>space. The language spec does not address the issue.
>
>All in all a quality of implementation issue.

so, in case of a doubt, I should do the storage of the result myself,
like, make a variable to replace each recurrent operation?

Perhaps. But don't go turning every rock for potential
microoptimizations like this.

in my case it's not a micro optimization (I guess) since for my
(foo>>1) example, I use that 10 times for each pixel I process, and
since I can have up to 6 million pixels to process every second..
that's 60 million shifts a second I can avoid, I presume. Considered
that I'm going to run this code on a 200 MHz ARM920T, it might not be a
micro optimization at all ;-)

Don't presume.
Profile first, then optimize.

Profile? What does it mean?

Measure where you spend how much time (and sometimes memory);
the programmes helping you there are profilers.
Often, you find that -- surprisingly -- your programme spends
much time in a piece of code you never thought of optimizing
or that some "optimization" you thought up makes performance
worse because the compiler no longer recognizes optimisable
patterns and in turn does not perform other optimisations any
longer.

Note on your example: I'd go for the temporary variable -- it
is easier and less compile time consuming to find all uses
of "temp", measure whether replacement by foo>>1 would overall
improve the code or whether using a register for temp may be
better than find out that foo>>1 is used more than once, where
it is used with the same value of foo and that it is the
largest such subexpression that is worth replacing.
However, this is not something I measured for each and every
system, so my advice may be exactly the wrong way for you.

OK, thanks for the advice. I looked into gprof (I wish I knew about it
earlier on) and so I could benchmark the difference, and it appears
that the difference is pretty small, if even significant.

And using gprof also pointed out that some other functions that I
didn't suspect to be that hungry actually needed some optimization.

[Barry Schwarz]

On 31 Aug 2006 23:28:04 -0700, "Bill Pursell" <bi**********@gmail.com>
wrote:

>Michel Rouzic wrote:

>Barry Schwarz wrote:

On 31 Aug 2006 20:04:02 -0700, "Michel Rouzic" <Mi********@yahoo.fr>
wrote:

>I'd like to know whether an operation which always has the same result
will be recomputed.

The answer depends on whether your compiler can recognize the common
sub-expression and the fact that the values have not changed. Some
compilers have options that say optimize for speed or optimize for
space. The language spec does not address the issue.

so, in case of a doubt, I should do the storage of the result myself,
like, make a variable to replace each recurrent operation?

If you really must know, look at the output of the compiler
and check to see what it's doing. (ie disassemble the executable.)

Or, if your compiler supports the option, output the assembler code
directly in a "more readable" format.
Remove del for email

[Ark]

Michel Rouzic wrote:

Michael Mair wrote:

>Michel Rouzic schrieb:

>>Nils O. Selåsdal wrote:

Michel Rouzic wrote:

Nils O. Selåsdal wrote:
>
>Michel Rouzic wrote:
>>
>>Barry Schwarz wrote:
>>>
>>>On 31 Aug 2006 20:04:02 -0700, "Michel Rouzic" <Mi********@yahoo.fr>
>>>wrote:
>>>>
>>>>
>>>>Hi,
>>>>>
>>>>I'd like to know whether an operation which always has the sameresult
>>>>will be recomputed. Here's the context : I in a loop have to compare
>>>>many things to foo>>1 in an if statement. In that very if statement I
>>>>compare stuff with (foo>>1) about four times, and I'd like to know if
>>>>it everytime does the shifting from the original foo value or if it
>>>>re-uses the previous result, since the value of foo did not change.
>>>>>
>>>>Also I use many times in my loop (bar>>1), same question with it, does
>>>>it get calculated over again or not?
>>>>>
>>>The answer depends on whether your compiler can recognize the common
>>>sub-expression and the fact that the values have not changed. Some
>>>compilers have options that say optimize for speed or optimize for
>>>space. The language spec does not address the issue.
>>>>
>>>All in all a quality of implementation issue.
>>so, in case of a doubt, I should do the storage of the result myself,
>>like, make a variable to replace each recurrent operation?
>Perhaps. But don't go turning every rock for potential
>microoptimizations like this.
in my case it's not a micro optimization (I guess) since for my
(foo>>1) example, I use that 10 times for each pixel I process, and
since I can have up to 6 million pixels to process every second..
that's 60 million shifts a second I can avoid, I presume. Considered
that I'm going to run this code on a 200 MHz ARM920T, it might not be a
micro optimization at all ;-)
Don't presume.
Profile first, then optimize.

Profile? What does it mean?

Measure where you spend how much time (and sometimes memory);
the programmes helping you there are profilers.
Often, you find that -- surprisingly -- your programme spends
much time in a piece of code you never thought of optimizing
or that some "optimization" you thought up makes performance
worse because the compiler no longer recognizes optimisable
patterns and in turn does not perform other optimisations any
longer.

Note on your example: I'd go for the temporary variable -- it
is easier and less compile time consuming to find all uses
of "temp", measure whether replacement by foo>>1 would overall
improve the code or whether using a register for temp may be
better than find out that foo>>1 is used more than once, where
it is used with the same value of foo and that it is the
largest such subexpression that is worth replacing.
However, this is not something I measured for each and every
system, so my advice may be exactly the wrong way for you.

OK, thanks for the advice. I looked into gprof (I wish I knew about it
earlier on) and so I could benchmark the difference, and it appears
that the difference is pretty small, if even significant.

And using gprof also pointed out that some other functions that I
didn't suspect to be that hungry actually needed some optimization.

When doing THIS sort of optimization, you should understand that it
depends both on the quality of the compiler and on the underlying
machine instruction set. If, e.g., your machine employs a barrel
shifter, a shift *may* be free, and
#define half(foo) ((foo)>>1)
will do great.
For instance, on ARM processors in ARM mode, shift is free for additions
and array indexing but is not free for multiplications.

[CBFalconer]

Michel Rouzic wrote:

Michael Mair wrote:

.... snip ...

>
OK, thanks for the advice. I looked into gprof (I wish I knew about
it earlier on) and so I could benchmark the difference, and it
appears that the difference is pretty small, if even significant.

And using gprof also pointed out that some other functions that I
didn't suspect to be that hungry actually needed some optimization.

That's what it's for.

Please snip quoted material not germane to your reply as I have.

--
Some informative links:
news:news.announce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

[Michel Rouzic]

Barry Schwarz wrote:

On 31 Aug 2006 23:28:04 -0700, "Bill Pursell" <bi**********@gmail.com>
wrote:

Michel Rouzic wrote:

Barry Schwarz wrote:
On 31 Aug 2006 20:04:02 -0700, "Michel Rouzic" <Mi********@yahoo.fr>
wrote:

>I'd like to know whether an operation which always has the same result
>will be recomputed.

The answer depends on whether your compiler can recognize the common
sub-expression and the fact that the values have not changed. Some
compilers have options that say optimize for speed or optimize for
space. The language spec does not address the issue.

so, in case of a doubt, I should do the storage of the result myself,
like, make a variable to replace each recurrent operation?

If you really must know, look at the output of the compiler
and check to see what it's doing. (ie disassemble the executable.)

Or, if your compiler supports the option, output the assembler code
directly in a "more readable" format.

yeah you mean for example with gcc -S, right?

[Flash Gordon]

Michel Rouzic wrote:

Barry Schwarz wrote:

>On 31 Aug 2006 23:28:04 -0700, "Bill Pursell" <bi**********@gmail.com>
wrote:

>>Michel Rouzic wrote:
Barry Schwarz wrote:
On 31 Aug 2006 20:04:02 -0700, "Michel Rouzic" <Mi********@yahoo.fr>
wrote:
>I'd like to know whether an operation which always has the same result
>will be recomputed.
The answer depends on whether your compiler can recognize the common
sub-expression and the fact that the values have not changed. Some
compilers have options that say optimize for speed or optimize for
space. The language spec does not address the issue.
so, in case of a doubt, I should do the storage of the result myself,
like, make a variable to replace each recurrent operation?
If you really must know, look at the output of the compiler
and check to see what it's doing. (ie disassemble the executable.)

Or, if your compiler supports the option, output the assembler code
directly in a "more readable" format.

yeah you mean for example with gcc -S, right?

Something of the sort. However, you should also tell the compiler to
optimise and, probably, to compiler C code with a decent level of
warnings rather than GNUC. So something more along the lines of:
gcc -A -O3 -ansi -pedantic -Wall
Probably adding options to tell it to use instructions that were only
added on the earliest version of the processor you want to support as
well (the Pentium added a number of instructions at least one of which
is probably useful!). MMX, SSE and other stuff can also improve
efficiency *if* the only systems to run your code have them.

For more detailed advice on gcc, including which options are likely to
improve performance (for any given measure of performance) on particular
architectures one of the GNU group would be the best place to ask.
--
Flash Gordon