break statement in a for loop

[a.mil@chello.nl]

I am programming for code-speed, not for ansi or other nice-guy stuff
and I encountered the following problem:

When I have a for loop like this:

b=b0;
for (a=0,i=0;i<100; i++,b--) {
if (b%i) continue;
a=1;
}

I want to break out of the loop -fast- after a==1. When I put a break
after it like in

b=b0;
for (a=0,i=0;i<100; i++,b--) {
if (b%i) continue;
a=1;
break;
}

the former fast loop turns into a horribly (factor 100 or so...) slow
one, so better to use no break at all in my opinion.

Does anyone know exactly -why- the break statement makes the loop so
slow??
Isn't it just an extra "jmp" in assembler equivalent code? I compared
both assembled outputs with and without the break statement, but they
really look quite different.. ?! I optimize with -O3 using gcc.

[klaushuotari@gmail.com]

Re: break statement in a for loop

On 28 huhti, 22:15, a...@chello.nl wrote:

I am programming for code-speed, not for ansi or other nice-guy stuff
and I encountered the following problem:
>
When I have a for loop like this:
>
b=b0;
for (a=0,i=0;i<100; i++,b--) {
if (b%i) continue;
a=1;
>
}
>
I want to break out of the loop -fast- after a==1. When I put a break
after it like in
>
b=b0;
for (a=0,i=0;i<100; i++,b--) {
if (b%i) continue;
a=1;
break;
>
}
>
the former fast loop turns into a horribly (factor 100 or so...) slow
one, so better to use no break at all in my opinion.
>
Does anyone know exactly -why- the break statement makes the loop so
slow??
Isn't it just an extra "jmp" in assembler equivalent code? I compared
both assembled outputs with and without the break statement, but they
really look quite different.. ?! I optimize with -O3 using gcc.

Break statement should not inherently make branching that much slower,
while in practice it usually does.

I guess it's implementation dependent, for example in x86 it's not a
big deal.
Just make concise and clear code, and it will turn out exactly nice in
machine code level. If the compiler is intelligent enough, it should
catch this situation and make appropriate code for it. No worries.

[Richard Heathfield]

Re: break statement in a for loop

a.mil@chello.nl said:

I am programming for code-speed, not for ansi or other nice-guy stuff
and I encountered the following problem:
>
When I have a for loop like this:
>
b=b0;
for (a=0,i=0;i<100; i++,b--) {
if (b%i) continue;
a=1;
}

This should be really fast, since you get a divide by zero error on the
very first time through the loop.

It is easier to make a correct program fast than to make a fast program
correct. Start off, then, by seeking correctness.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999

http://www.cpax.org.uk

email: rjh at the above domain, - www.

[Malcolm McLean]

Re: break statement in a for loop


<a.mil@chello.n lwrote in message
news:1177787740 .942970.285880@ e65g2000hsc.goo glegroups.com.. .

>I am programming for code-speed, not for ansi or other nice-guy stuff
and I encountered the following problem:
>
When I have a for loop like this:
>
b=b0;
for (a=0,i=0;i<100; i++,b--) {
if (b%i) continue;
a=1;
}
>
I want to break out of the loop -fast- after a==1. When I put a break
after it like in
>
b=b0;
for (a=0,i=0;i<100; i++,b--) {
if (b%i) continue;
a=1;
break;
}
>
the former fast loop turns into a horribly (factor 100 or so...) slow
one, so better to use no break at all in my opinion.
>
Does anyone know exactly -why- the break statement makes the loop so
slow??
Isn't it just an extra "jmp" in assembler equivalent code? I compared
both assembled outputs with and without the break statement, but they
really look quite different.. ?! I optimize with -O3 using gcc.
>

I think there must be some mistake elsewhere.
If the loop execution has changed by a factor of 100 then either you are not
measuring the same thing, or the compiler has optimised the loop away in
one case but not the other. An example would be if you used the value of i
later in the function but ignored a. In one case the compiler can optimise
to i = 100, in the other case it probably isn't clever enough to do it
without running through the loop.
Someone will probably point out, correctly, that a conforming compiler can
compile the break to something horribly slow. The standard makes no
guarantees on efficiency. Whilst this might account for a factor of two or
three, I cannot see how it would account for 100.
--
Free games and programming goodies.

http://www.personal.leeds.ac.uk/~bgy1mm

[christian.bau]

Re: break statement in a for loop

a...@chello.nl wrote:

I am programming for code-speed, not for ansi or other nice-guy stuff

I don't know _what_ you are programming for, but you flunked your
maths test _and_ your programming test, didn't you? (And that's me
being a nice guy, you shouldn't meet me in non-ansi mode).

When I have a for loop like this:
>
b=b0;
for (a=0,i=0;i<100; i++,b--) {
if (b%i) continue;
a=1;
}

As others mentioned, undefined behavior (most likely a crash)
immediately when you calculate b % 0 in the first iteration. If you
started the loop with i = 1, then a would be set to 1 immediately,
making the whole loop rather pointless.

Now assuming that you intended to do something sensible, like starting
the loop with i = 2: Note that (b % i) != 0 is exactly the same as ((b
+ i) % i) != 0. Inside the loop, i is increased and b decreased in
each iteration, whereas b + i remains constant. So it seems that you
are just checking whether a certain number has a factor less than 100.
You can do that significantly faster by checking divisibility by prime
numbers up to 100; in practice a hardcoded

a = (b % 2 && b % 3 && b % 5 && b % 7 && b % 11 ... && b % 97) ? 0 :
1;

would be faster by a factor ten again on many implementations .

[a.mil@chello.nl]

Re: break statement in a for loop

Ok, this was a bad fast example, I admit.
Therefore below another example that shows the point.


int main()
{
unsigned long i,j,k,l,n;

for (l=0;l<10000000 ;l++) {
j=0;
k=10;
n=231;

for (i=1;n>3;j+=8,k +=j,n-=2) {
if (k%n) continue;
i=0;
break;
}
}
return 0;
}


Run this without the break statement and with the break statement and
look at execution time. On my 1.5GHz P4 it takes 1.3s and 13.9s
respectively (!). My store on the factor 100 incorporates a lot more
code.

[Richard Heathfield]

Re: break statement in a for loop

a.mil@chello.nl said:

Ok, this was a bad fast example, I admit.
Therefore below another example that shows the point.
>
>
int main()
{
unsigned long i,j,k,l,n;
>
for (l=0;l<10000000 ;l++) {
j=0;
k=10;
n=231;
>
for (i=1;n>3;j+=8,k +=j,n-=2) {
if (k%n) continue;
i=0;
break;
}
}
return 0;
}
>
>
Run this without the break statement and with the break statement and
look at execution time. On my 1.5GHz P4 it takes 1.3s and 13.9s
respectively (!). My store on the factor 100 incorporates a lot more
code.

The same result can be achieved much more quickly:

int main(void)
{
return 0;
}

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999

http://www.cpax.org.uk

email: rjh at the above domain, - www.

[a.mil@chello.nl]

Re: break statement in a for loop

It's not my objective to show you the full code; it's about the issue
of execution speed and "break".


Richard Heathfield schreef:

a.mil@chello.nl said:
>

Ok, this was a bad fast example, I admit.
Therefore below another example that shows the point.


int main()
{
unsigned long i,j,k,l,n;

for (l=0;l<10000000 ;l++) {
j=0;
k=10;
n=231;

for (i=1;n>3;j+=8,k +=j,n-=2) {
if (k%n) continue;
i=0;
break;
}
}
return 0;
}


Run this without the break statement and with the break statement and
look at execution time. On my 1.5GHz P4 it takes 1.3s and 13.9s
respectively (!). My store on the factor 100 incorporates a lot more
code.

>
The same result can be achieved much more quickly:
>
int main(void)
{
return 0;
}
>
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999

http://www.cpax.org.uk

email: rjh at the above domain, - www.

[Richard Heathfield]

Re: break statement in a for loop

a.mil@chello.nl said:

It's not my objective to show you the full code; it's about the issue
of execution speed and "break".

But break isn't the problem. The problem is a poorly-constructed
algorithm, which involves you performing many unnecessary calculations.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999

http://www.cpax.org.uk

email: rjh at the above domain, - www.

[Default User]

Re: break statement in a for loop - TPA

a.mil@chello.nl wrote:

It's not my objective to show you the full code; it's about the issue
of execution speed and "break".

Please don't top-post. Your replies belong following or interspersed
with properly trimmed quotes. See the majority of other posts in the
newsgroup, or:
<http://www.caliburn.nl/topposting.html >

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

Re: break statement in a for loop

a.mil@chello.nl wrote:

Ok, this was a bad fast example, I admit.
Therefore below another example that shows the point.
>
>
int main()
{
unsigned long i,j,k,l,n;
>
for (l=0;l<10000000 ;l++) {
j=0;
k=10;
n=231;
>
for (i=1;n>3;j+=8,k +=j,n-=2) {
if (k%n) continue;
i=0;
break;
}
}
return 0;
}
>
>
Run this without the break statement and with the break statement and
look at execution time. On my 1.5GHz P4 it takes 1.3s and 13.9s
respectively (!). My store on the factor 100 incorporates a lot more
code.

On my system, without the "break", it takes 0.001 seconds (according
to "time"). That's because without the break, the compiler realises
your program does nothing and your for loop is useless, so it removes
it altogether. How about an actual demonstration (a program that does
something useful, such as printing the result of your calculation,
whatever it is you're trying to calculate)?

[Malcolm McLean]

Re: break statement in a for loop


<a.mil@chello.n lwrote in message
news:1177832094 .386456.165570@ c35g2000hsg.goo glegroups.com.. .

It's not my objective to show you the full code; it's about the issue
of execution speed and "break".
>
>

It is perfectly reasonable to post a compileable snippet showing the
problem, but here we don't have enough to work on. It is hard to optimise a
function that doesn't actully do anything.
--
Free games and programming goodies.

http://www.personal.leeds.ac.uk/~bgy1mm

[CBFalconer]

Re: break statement in a for loop

Malcolm McLean wrote:

<a.mil@chello.n lwrote in message
>

>It's not my objective to show you the full code; it's about the
>issue of execution speed and "break".

It is perfectly reasonable to post a compileable snippet showing
the problem, but here we don't have enough to work on. It is hard
to optimise a function that doesn't actully do anything.

Besides which, the loop does different things with the break
inserted.

--
<http://www.cs.auckland .ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfoc us.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
<http://kadaitcha.cx/vista/dogsbreakfast/index.html>
cbfalconer at maineline dot net



--
Posted via a free Usenet account from http://www.teranews.com

[Richard Tobin]

Re: break statement in a for loop

In article <1177830701.665 430.153460@l77g 2000hsb.googleg roups.com>,
<a.mil@chello.n lwrote:

>Run this without the break statement and with the break statement and
>look at execution time. On my 1.5GHz P4 it takes 1.3s and 13.9s
>respectively (!).

I get a similar result with GCC on a PPC Mac. It appears to just be
an optimisation effect: without the break the compiler can determine
enough about the inner for loop to optimise it away completely; with
the break it can't.

It's easy to construct artificial examples of this kind, but they are
rare in real programs, because if the compiler can optimise away a
loop, then the programmer probably won't write it in the first place.

-- Richard
--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[christian.bau]

Re: break statement in a for loop

On Apr 29, 8:34 am, a...@chello.nl wrote:

It's not my objective to show you the full code; it's about the issue
of execution speed and "break".

Your first example was pure nonsense invoking undefined behavior at
the first step.

Your second example was a completely useless piece of code, where huge
portions of the code could be optimised away. All that you have been
testing is the capability of the compiler to detect nonsense code and
remove it. It seems your break statement affected the compilers
capability of detecting nonsense code. This might be of importance to
you, it is of no importance to those 99.9999 percent of programmers
who actually write more sensible code in the first place.