performance question

Hello,

Given the following code:

times = getTimes()
for (i = 0; i < times / 2; i++){
// do something
}

Will the times / 2 expression be a likely optimization so that the
division is not repeated? Granted this is not part of the C++
standard, but it is important to have a sense for performance reasons.

Cheers,
Ivan Novick
http://www.mycppquiz.com

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Dec 10, 6:39 am, "novicki...@gmail.com" <novicki...@gmail.com>
wrote:
> Hello,
>
> Given the following code:
>
> times = getTimes()
> for (i = 0; i < times / 2; i++){
> // do something
>
> }
>
> Will the times / 2 expression be a likely optimization so that the
> division is not repeated?

Yes, if the compiler can prove that times is not modified in the loop.
If it doesn't appear, that's a very simple way of proving it.

Sebastian


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

novickivan@gmail.com wrote:
> Hello,
>
> Given the following code:
>
> times = getTimes()
> for (i = 0; i < times / 2; i++){
> // do something
> }
>

Shouldn't that be
for(int i=0, e=getTimes()/2; i!=e; ++i)
or at least
for(int i=0, e=times/2; i!=e; ++i)
.... ?
In which case the optimizing question is moot.

> Will the times / 2 expression be a likely optimization so that the
> division is not repeated? Granted this is not part of the C++
> standard, but it is important to have a sense for performance reasons.
>

If times is not modified I would write the code as I've stated above. If
times is modified inside the loop, then no compiler will optimize the
division away (or so I hope).

br,
Martin

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

novickivan@gmail.com wrote:
> Given the following code:
>
> times = getTimes()
> for (i = 0; i < times / 2; i++){
> // do something
> }
>
> Will the times / 2 expression be a likely optimization so that the
> division is not repeated?

Well, I can't tell that "do something" doesn't modify it. Neither do I know
its definition or where else it is used. Further, and that is bad
style, 'i' is not declared in the loop.

So, how about this loop instead:

int const times = getTimes();
for(int i=0; i!=times/2; ++i)
...

However, even there I would suggest this style instead:

for(int i=0, time=getTimes()/2; i!=times; ++i)
...

Note that this works when using iterators, too, and that it doesn't rely on
the compiler to figure out that 'some_container.end()' never changes
throughout the loop.

> Granted this is not part of the C++ standard, but it is important
> to have a sense for performance reasons.

Measure it.

Uli

--
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Dec 10, 6:39 am, "novicki...@gmail.com" <novicki...@gmail.com>
wrote:
> Hello,
>
> Given the following code:
>
> times = getTimes()
> for (i = 0; i < times / 2; i++){
> // do something
>
> }
>
> Will the times / 2 expression be a likely optimization so that the
> division is not repeated? Granted this is not part of the C++
> standard, but it is important to have a sense for performance reasons.

My feeling is: if times is modified inside {} block, likely no. If
not, likely yes. (That is, yes if compiler can conclude that "times"
doesn't change throughout.)

That said... There's a huge change that particular optimization is a
micro-one and the way code is written won't matter (e.g. by moving
that division out of for). Modern C/C++ compilers will optimize hell
out your code and micro optimizations programmer might try to make are
not only a waste of time, but can even be detrimental. E.g. see recent
performance discussion on this very group:

http://groups.google.com/group/comp....29c714f364996b

Please abstain from any performance questions in your quiz ;-).

Goran.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 10.12.2009 7:39, novickivan@gmail.com wrote:
> Will the times / 2 expression be a likely optimization so that the
> division is not repeated? Granted this is not part of the C++
> standard, but it is important to have a sense for performance reasons.

It can be optimized in case if 'times' variable has 'const' specifier.

Taras Shevchuk

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Dec 10, 6:39 am, "novicki...@gmail.com" <novicki...@gmail.com>
wrote:
> Hello,
>
> Given the following code:
>
> times = getTimes()
> for (i = 0; i < times / 2; i++){
> // do something
>
> }
>
> Will the times / 2 expression be a likely optimization so that the
> division is not repeated? Granted this is not part of the C++
> standard, but it is important to have a sense for performance reasons.

The effect is likely to be zero. If 'times' is not modified inside the
loop, then the compiler will probably notice that the value of
'times / 2' is not affected by the loop body and arrange that the
computation is done only once.
And even if the compiler does not perform that optimisation, a single
integer division (especially by a power of 2) is not likely to be a
performance bottleneck.

>
> Cheers,
> Ivan Novickhttp://www.mycppquiz.com
>
Bart v Ingen Schenau


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

CornedBee <wasti.redl@gmx.net> wrote in news:97c8ec5a-c6ac-4c9f-899a-
682e71267889@g12g2000yqa.googlegroups.com:

>
> Yes, if the compiler can prove that times is not modified in the loop.
> If it doesn't appear, that's a very simple way of proving it.
>

Not even close.

There are plenty of ways times can be modified
inside the loop without appearing there.

Almost any function call or data
access could modify times, if its address were
taken (by pointer or reference) before the loop.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

novickivan@gmail.com wrote:

> Given the following code:
>
> times = getTimes()
> for (i = 0; i < times / 2; i++){
> // do something
> }
>
> Will the times / 2 expression be a likely optimization so that the
> division is not repeated? Granted this is not part of the C++
> standard, but it is important to have a sense for performance reasons.
>

I suggest trying it with your favorite C++ compiler and look at the
assembler output. This will definitively answer it. As for the Digital Mars
compiler,

----------------------------------
extern void foo();
extern int getTimes();

int main(void)
{
int times = getTimes();
for (int i = 0; i < times / 2; i++){
foo();
}
return 0;
}
----------------------------------
_main:
sub ESP,0Ch
push EBX
xor EBX,EBX
push ESI
call near ptr _getTimes
test EAX,EAX
mov 010h[ESP],EAX
jns L15
inc EAX
L15: sar EAX,1
cmp EAX,EBX
jle L32
mov ECX,010h[ESP]
test ECX,ECX
jns L24
inc ECX
L24: sar ECX,1
mov ESI,ECX
L28: call near ptr _foo
inc EBX
cmp ESI,EBX
jg L28
L32: pop ESI
xor EAX,EAX
pop EBX
add ESP,0Ch
ret
----------------------------------

So yes, it is loop invariant and moved out of the loop body.

===========================================
Walter Bright
Digital Mars
http://www.digitalmars.com
Free C, C++, Javascript, D programming language compilers

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]