code optimization- Removing if .. else conditions in for loops

[Kunal]

Hello,

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

As per my reasoning, the logical expression is evaluated but no
conditional branching instructions should be generated. This should
avoid any pipeline stalls.
However, I havent found any document confirming my belief !
Any comments, suggestions or references will be a big help !

Thanks & Regards

[Ben Pfaff]

"Kunal" <ku************ *@gmail.com> writes:

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

The only way you can find out whether this makes a difference is
by measuring. My guess is that it will make no difference with
most compilers.

Note that the evaluation of `a > b' may itself require a branch.
--
int main(void){char p[]="ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwC IxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+= strchr(p,*q++)-p;if(i>=(int)si zeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Keith Thompson]

"Kunal" <ku************ *@gmail.com> writes:

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

As per my reasoning, the logical expression is evaluated but no
conditional branching instructions should be generated. This should
avoid any pipeline stalls.
However, I havent found any document confirming my belief !
Any comments, suggestions or references will be a big help !

You're assuming that the code generated for (a > B) won't involve any
conditional branches.

Any decent compiler is likely to generate similar or identical code
for both forms.

It's usually best to write your code as clearly as possible and let
the compiler worry about micro-optimization. Attempting to do
low-level optimization yourself is likely to make the compiler's job
more difficult.

First rule of optimization: Don't do it.
Second rule of optimization (advanced users only): Don't do it yet.

If you really need to do this kind of micro-optimization, perhaps
because the loop is in a performance-critical part of your program
(because you've measured it), you can probably examine the assembly
language generated by your compiler -- or you can write the code in
assembly language yourself.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Christian Bau]

In article <11************ **********@g14g 2000cwa.googleg roups.com>,
"Kunal" <ku************ *@gmail.com> wrote:

Hello,

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

As per my reasoning, the logical expression is evaluated but no
conditional branching instructions should be generated. This should
avoid any pipeline stalls.

Did you measure how long it takes?

The most important rule of optimisation: Don't optimise until you have
measured it.

(There are several most important rules of optimisation, this is just
one of them. I bet some more will be posted. This one always applies:
Never, ever optimise without measuring. )

[Eric Sosman]

Kunal wrote On 12/05/05 17:02,:

Hello,

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}
Even faster (probably):

c = (a > B) ? 999 : 0;
i = 999;
As per my reasoning, the logical expression is evaluated but no
conditional branching instructions should be generated. This should
avoid any pipeline stalls.
However, I havent found any document confirming my belief !
Any comments, suggestions or references will be a big help !

See Ben Pfaff's response.

--
Er*********@sun .com

[Jordan Abel]

On 2005-12-05, Eric Sosman <er*********@su n.com> wrote:

Kunal wrote On 12/05/05 17:02,:

Hello,

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

Even faster (probably):

c = (a > B) ? 999 : 0;
i = 999;

Though presumably he was doing more in the loop, you're correct.

[Eric Sosman]

Jordan Abel wrote On 12/05/05 18:00,:

On 2005-12-05, Eric Sosman <er*********@su n.com> wrote:

Kunal wrote On 12/05/05 17:02,:

Hello,

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

Even faster (probably):

c = (a > B) ? 999 : 0;
i = 999;

Though presumably he was doing more in the loop, you're correct.

That was the point I was trying to make, indirectly:
It's silly to micro-optimize pseudocode. If the O.P.
responds to my tongue-in-cheek suggestion by showing us
what's actually going on in the loop, we might have some
better ideas about how to optimize it -- or whether it's
even worth the bother.

--
Er*********@sun .com

[Mark McIntyre]

On 5 Dec 2005 14:02:46 -0800, in comp.lang.c , "Kunal"
<ku************ *@gmail.com> wrote:

Hello,

I need help in removing if ..else conditions inside for loops.
Why - have you proved that they're inefficient?
c += (a > B) ; As per my reasoning, the logical expression is evaluated but no
conditional branching instructions should be generated. This should
avoid any pipeline stalls.

This would be /highly/ hardware specific, and depend very very much on
your compiler's efficiency.

As a general rule its a bad idea to try to outsmart your compiler,
until and unless you can prove its inefficient. You may end up simply
making your code slower. A good compiler might realise it could unroll
the loop and discard a whole bunch of the ifs, and your 'improvement'
might prevent that for some reason.

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

[Flash Gordon]

Kunal wrote:

Hello,

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Have you tested the code to see if it is too slow? Have you done
profiling to see where the code is spending its time? Have you made sure
that you are using an efficient algorithm? All these things should come
before spending time on a question like this.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

As per my reasoning, the logical expression is evaluated but no
conditional branching instructions should be generated. This should
avoid any pipeline stalls.
Anything like that is highly specific to the processor, compiler,
specific version of the compiler, the settings of the compiler and the
surrounding code.
However, I havent found any document confirming my belief !
It is very unlikely there is *any* documentation that will tell you
which is faster, since it might depend on a hole host of things.
Any comments, suggestions or references will be a big help !

Rule one of optimisation:
Don't do it.

Write the code to do the right thing in an understandable (to a human)
manner and let the optimiser that is almost certainly part of your
compiler package do its job.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.

[Chris Dollin]

Kunal wrote:

Hello,

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

As per my reasoning, the logical expression is evaluated but no
conditional branching instructions should be generated. This should
avoid any pipeline stalls.

On the ARM, a natural way to compile the if (assuming variables in
registers, which is plausible here) is:

CMP a, B
ADDEQ c, c, #1

Two instructions, no pipeline break. I can't see a compiler generating
better code for your `c += (a > B)` statement, and it would be easy for
it to generate much /worse/ code.

Morals: (a) measure before you consider optimising; (b) straightforward
code plays to the compiler's strengths.

--
Chris "another virtual machine" Dollin
"Certainly the absence of a smiley is not a syntax error or a constraint
violation, and therefore doesn't require a diagnostic." (Richard
Heathfield)